OBI 2023 - Fase 2 - Turno B - Programação Nível 1

Se você quiser se preparar para a OBI, não deixe de conferir o Roteiro de estudos de informática, e também a página de informática do NOIC, com todos os nossos materiais.

Para conferir a prova na integra, entre no site da OBI.

Brincadeiras de Roda

Comentário escrito por Enzo Dantas

Conhecimento prévio necessário:

• Congruências

Imagine um círculo com 5 pessoas. Se o professor bate palma 5 vezes, percebemos que todas as pessoas dão uma volta completa e continuam no mesmo lugar, e percebemos que isso também vale para qualquer número múltiplo de 5. Sendo assim, em um círculo com $n$ pessoas, vamos nos importar apenas com a quantidade de palmas $P$ módulo $n$. É fácil ver que uma pessoa qualquer que começa na posição $x$ vai terminar aproximadamente na posição $(x+P) (mod$ $n)$. Trabalhando com casos pequenos chegamos na fórmula exata $(x+P-1) (mod P) + 1$, e essa é a solução em $O(1)$.

Além disso, os limites pequenos do problema permitem uma solução ainda mais direta: simular cada palma do professor. Se a posição atual é igual a $n$, então a posição depois da palma é 1. Caso contrário apenas adicionamos 1 à posição. Complexidade: O(P).

Clique aqui para conferir o código (Solução 1)

Clique aqui para conferir o código (Solução 2)

Startup

Comentário escrito por João Pedro Castro

Conhecimento prévio necessário:

• Árvores

Podemos visualizar a hierarquia dessa empresa como um grafo, onde os vértices (funcionários) tem outros vértices se ligando à ele (os subordinados). Além da estrutura do grafo, para cada funcionário vamos guardar seu chefe, salário, e a quantidade de subordinados com os quais ele está insatisfeito. Também é necessário guardar a quantidade de funcionários insatisfeitos no total, chamaremos esse valor de $f$.

Após montar o grafo (feito com as arestas sendo: $\text{chefe} \rightarrow \text{subordinado}$), receber o chefe de cada um e o salário, para preencher a quantidade de insatisfações basta percorrer o grafo começando do vértice 1 e aumentando o valor de $insatisfacoes[vertice]$ em uma unidade toda vez que $salario[subordinado] > salario[vertice]$, quando isso acontecer, também aumente $f$ em 1 caso $insatisfacoes[vertice] = 0$, já que o estado do $vertice$ vai mudar de satisfeito para insatisfeito.

Para todo funcionário $i$ atualizado a ideia é checar se o "estado" (satisfeito ou insatisfeito) de seu chefe e dele mesmo (em relação ao seus subordinados) foram alterados, já que eles são os únicos com os quais isso pode ter acontecido. E isso pode ser feito com uma série de estruturas condicionais, que se resumem à:

• (chefe insatisfeito antes com o funcionário) e (chefe satisfeito agora)
• (chefe satisfeito antes com o funcionário) e (chefe insatisfeito agora)

Agora, para achar o valor de $f$ (a resposta) atualizado, é só seguir o seguinte algoritimo:

• Se $i \neq 1 ~\&~ salario[i] \geq salario[chefe[i]] ~\&~ novoSalario > salario[chefe[i]]$
  • $insatisfacoes[chefe[i]]++$
  • Se $insatisfacoes[chefe[i]] = 1$ (novo chefe insatisfeito):
    • $f++$
• Se não se: $salario[i] > salario[chefe[i]] ~\&~ salario[chefe[i]] \geq novoSalario$
  • $insatisfacoes[chefe[i]]--$
  • Se $insatisfacoes[chefe[i]] = 0$ (chefe satisfeito de novo):
    • $f--$
• Para cada subordinado $u$ de $i$:
  • Se $salario[i] \geq salario[u] ~\&~ salario[u] > novoSalario$:
    • $insatisfacoes[i]++$
    • Se $insatisfacoes[i] = 1$ (novo chefe insatisfeito):
      • $f++$
  • Se não se: $salario[u] > salario[i] ~\&~ novoSalario \geq salario[u]$:
    • $insatisfacoes[i]--$
    • Se $insatisfacoes[i] = 0$ (chefe satisfeito de novo):
      • $f--$
• $salario[i] = novoSalario$
• $imprimir~f$

Assim você também garante que os valores de $insatisfacoes$ e $f$ sempre permanecem atualizados. Segue a solução em C++:

Clique aqui para ver o código

Corridas

Escrito por Caique Paiva

Conhecimentos Prévios Necessários:

• Básico de Geometria

A principal ideia desse problema é que a solução vai ser um retângulo. Para perceber isso, basta ver que, se temos uma solução ótima, podemos ir "dobrando" a cerca para que ela vire um retângulo. Vamos ver um exemplo para ficar mais claro:

Na primeira figura, temos um caminho que é solução do problema, e então, a ideia é pegar essas pontas que não são um retângulo, e dobrar elas para se tornar um retângulo, e isso não muda o tamanho da cerca, logo podemos fazer isso. Então, fazemos isso até que a figura não tem mais nenhuma ponta.

Agora, dado que a figura é um retângulo, qual é o retângulo que é solução? É o retângulo que abrange a figura toda, ou seja, se olharmos os pontos como coordenadas da forma $(x, y)$, precisamos que o ponto com o menor $x$ do caminho esteja no retângulo, o com maior $x$ também esteja, o com menor $y$ também esteja, e o com maior $y$ também esteja, e veja que essa condição também é suficiente para construir o retângulo. Dito isso, seja $maxx, minx, maxy, miny$ o maior x, menor x, maior y e menor y, então, o perímetro desse retângulo $2*(maxx-minx+2+maxy-miny+2)$.

Com todas essas conclusões, como vamos fazer nossa resposta? Vamos simular o caminho feito no problema (Se estamos no ponto $(x, y)$ e temos que subir $k$ casas, fazemos $(x, y+k)$, e análogos) e vamos salvando qual é o maior x, o menor x, o maior y e o menor y, e no final, calcular a resposta com o que foi dito no paragrafo passado.

Clique aqui para ver o código