OBI 2018 - Fase 2 - Programação Nível 1

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.

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

Campeonato

Comentário escrito por Vitor Veiga

Conhecimento prévio necessário:

No problema é dada a diposição de 16 jogadores em um campeonato, e queremos saber quando dois desses jogadores irão se enfrentar, sabendo que ganham todos os jogos até o combate.

A estratégia para a resolução do problema será utilizar uma ideia de busca binária, onde realizaremos "cortes" na disposição dos jogadores até achar quando os jogadores vão se enfrentar por meio do número de cortes realizados. Só achamos o corte ideal quando ele dividir as posições dos jogadores, uma para a direita e outra para a esquerda.

Note que, caso um dos jogadores estiver em uma posição até 8 e o outro em uma maior que 8, com certeza eles se enfrentarão na final. Esse é o primeiro "corte" que fazemos. Depois, se essa condição não for válida, os dois jogadores estão ou para a direita ou para a esquerda da posição 8, então escolhemos um lado e repetimos a checagem para uma nova posição central. O máximo de cortes que fazemos são 4, que indica que os jogadores se enfrentariam nas oitavas de final.

Estratégia aplicada no quarto caso teste:

Clique aqui para conferir o código

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

Relógios

Comentário escrito por Estela Baron

Conhecimento prévio necessário:

Nesse problema, queremos descobrir o menor caminho ou se não é possível chegar a outra ponta. Se não houvesse os relógios quebrados, ou seja, se todas as posições fossem -1, poderíamos utilizar uma $bfs()$ ou calcular direto. Porém, o fato dos relógios quebrados existirem transforma o problema em um de grafo com as arestas com pesos, pois o tempo percorrido entre uma casa e um outra pode ser maior que 1. Para isso, vamos implementar uma função $dijkstra()$ na matriz - que representa os relógios - mas com alguns detalhes:

se o relógio adjacente estiver normal, ou seja $-1$ , basta adicionar $+ 1$ ao tempo e inserir o novo par de coordenadas na fila de prioridade.
se o relógio atual estiver quebrado e o adjacente também, só podemos adicionar o adjacente na fila se o tempo de espera entre os dois for no máximo 1 - se o tempo no relógio adjacente for maior que o atual, basta subtrair o atual do vizinho, caso contrário, temos que adicionar $k$ à diferença $relogio \; vizinho - relogio \; atual$ .
se o relógio atual estiver normal e o vizinho não, basta adicionar a posição vizinha à fila com a diferença entre o resto do tempo decorrido atual por $k$ e o tempo no relógio adjacente ( da mesma forma que o caso de cima).

Observe que podemos só utilizar um vetor de visitados para não visitar uma posição repetida ( não precisar guardar um vetor de tempos mínimos, pois os limites são pequenos - basta verificar se a posição já foi visitada na hora de analisar ou de adicionar na fila).

Se, durante a execução da função, a posição for igual à posição do canto inferior direito ( se for indexada a partir do zero , é igual a $l-1$ e a $c-1$ ), basta retornar a resposta. Caso contrário, basta retornar $-1$ ao final da função.

Clique aqui para conferir o código

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