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:

Estruturas Condicionais

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:

Busca binária

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 ver o código

Clique aqui para conferir a solução em vídeo feita pelo NepsAcademy