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.