OBI 2018 – Fase 2 – Programação Nível Júnior
Para conferir a prova na íntegra, clique aqui
Para ver todos os materiais incrível produzidos pela equipe NOIC para a OBI, veja a página de informática.
Copa
Comentário escrito por Enzo Dantas
Conhecimento prévio necessário:
A ideia é a seguinte, seja $$a, b$$ as posições dos jogadores Mestre Kung e Mestre Lu:
- Dois jogadores vão se encontrar na final se, um deles estiver entre $$[1, 8]$$ e outro estiver entre $$[9, 16]$$, pois senão, eles vão ter se encontrado antes. Portanto, se isso for verdade, vamos retornar “final” no nosso código e parar o algoritmo.
- Agora, se os dois estiverem entre $$[9, 16]$$, vamos fazer $$a = a-8$$ e $$b = b-8$$, e então, os dois jogadores vão estar entre $$[1, 8]$$. Veja que isso não vai mudar a resposta do problema, pois a estrutura do torneio para $$[1, 8]$$ é a mesma para $$[9, 16]$$. (A partir daqui, as ideias são análogas).
- Dois jogadores vão se encontrar na semifinal se, um deles estiver entre $$[1, 4]$$ e outro estiver entre $$[5, 8]$$, então, se isso for verdade, vamos retornar “semifinal” no nosso código e parar o algoritmo.
- Se os dois estiverem entre $$[5, 8]$$, vamos fazer $$a = a-4$$ e $$b = b-4$$, e então, os dois jogadores vão estar entre $$[1, 4]$$.
- Dois jogadores vão se encontrar nas quartas de final se, um deles estiver entre $$[1, 2]$$ e outro estiver entre $$[3, 4]$$, então, se isso for verdade, vamos retornar “quartas” no nosso código e parar o algoritmo.
- Se os dois estiverem entre $$[3,4]$$, vamos fazer $$a = a-2$$ e $$b = b-2$$, e então, os dois jogadores vão estar entre $$[1, 2]$$.
- Daí, basta retornar oitavas.
Por exemplo, no sample $$5, 8$$, veja que eles não vão se encontrar na final, e ambos estão entre $$[1, 8]$$. Além disso, eles não vão se encontrar na semifinal, e eles estão entre $$[5, 8]$$, logo vamos olhar o par $$1, 4$$. Então, sabemos que eles vão se encontrar nas quartas.
Clique aqui para conferir o código
Clique aqui para conferir a solução em vídeo feita pelo NepsAcademy
Pesos
Comentário escrito por Estela Baron
Conhecimento prévio necessário:
Observe que, para subir um peso grande, é necessário já ter um peso menor (ou nenhum) cuja a diferença seja menor ou igual a 8. Portanto, podemos adotar a seguinte estratégia: vamos fazer uma série de operações para subir o maior peso, pois depois subiremos o segundo maior, o terceiro maior e assim por diante. Isso somente é possível em razão de o número de viagens não ter nenhuma restrição.
Para subir o maior peso, caso ele seja maior que 8, é necessário que tenha uma caixa mais leve (se fosse mais pesada, o atual peso não seria o maior – estamos só considerando movimentar os pesos menores que o maior). A diferença é no máximo 8, ou seja, a segunda caixa mais pesada pode ter uma diferença de no máximo oito unidades. Assim, podemos ordenar os valores em ordem crescente ( podemos até incluir o 0 para representar o elevador vazio) e verificar se a diferença entre dois termos adjacentes não ultrapassa 8. Caso ultrapasse, a resposta é ‘N’, senão é ‘S’.
Clique aqui para conferir o código
Clique aqui para conferir a solução em vídeo feita pelo NepsAcademy
Cápsulas
Comentário escrito por Caique Paiva
Conhecimento prévio necessário:
Seja $$f(p)$$ a quantidade de moedas que ganhamos até o dia $$p$$. Veja que
$$f(p) \ge f(p-1)$$
Pois, se até o dia $$p-1$$ ganhamos $$k$$ moedas, então, no dia $$p$$, como é impossível de perder moedas no problema, continuamos com pelo menos $$k$$ moedas. Então, $$f$$ é crescente. Agora, veja que
$$f(p) = \sum_{i = 1}^n \lfloor \frac{n}{c_i} \rfloor$$
Pois, no dia $$c_i, 2c_i, 3c_i, \cdots xc_i$$ ganhamos uma moeda em cada dia, isso até $$xc_i \le n \rightarrow x \le \frac{n}{c_i}$$, e o $$x$$ máximo que isso é verdade é o $$\lfloor \frac{n}{c_i} \rfloor$$, então, basta aplicar isso para todas as moedas e somar todas as respostas, que conseguimos $$f(p)$$.
Portanto, queremos achar o menor $$p$$ tal que $$f(p) \ge F$$, e além disso, sabemos como calcular $$f(p)$$ em $$O(n)$$ e que $$f$$ é crescente, então, vamos fazer uma busca binária!! Faça $$l = 0, r = 10^{18}$$, então, vamos fazer o seguinte loop:
- Enquanto $$l < r$$, seja $$mid = \frac{l+r}{2}$$, logo, se $$f(mid) \ge F$$, então, façamos $$r = mid$$, pois sabemos que $$f(x) \ge f(mid) \ge F \forall x > mid$$. Se não, faça $$l = mid +1$$, pois sabemos que $$F > f(mid) \ge f(x) \forall x < mid$$.
Daí, basta retornar $$l$$.
Clique aqui para conferir a solução em vídeo feita pelo NepsAcademy