Comentário por Bia Cunha
Para ver o caderno de tarefas da Segunda Fase da Programação Nível 2 da OBI 2017, clique aqui.
Dario e Xerxes
Conhecimento prévio necessário:
A fim obter a resposta, precisamos saber quem ganhou a cada partida, contando em duas variáveis, d e x. O contador de maior valor representa o vencedor. Existem várias formas de saber quem ganhou, como checar cada possibilidade com vários if’s. Porém, observe que se x é uma unidade maior que d, Darios ganha (d=1 e x=2, por exemplo). Para incluir o caso em que 4 ganha de 0, podemos dizer que sempre que d+1 dividido por 5 tem resto igual a x. Com um raciocínio parecido, temos que sempre que d+2 dividido por 5 tem resto igual a x, d ganha. Essas duas condições cobrem todos os casos em que D ganha. Segue código para melhor entendimento.
https://gist.github.com/biacunha/66c9b5533c2baa944464c48d7e10241e
Frete
Conhecimento prévio necessário:
- Menor caminho (Aula 10)
Como é ilustrado na questão, as cidades podem ser representadas como vértices de um grafo, e as “entregas diretas” como arestas. Sendo o custo para transportar uma encomenda entre duas cidades vizinhas o peso de cada aresta, a resposta pode ser obtida com um algoritmo de menor caminho, como o algoritmo de Floyd-Warshall, de complexidade O(n³). Segue o código para melhor entendimento.
https://gist.github.com/e53e631411952ea2099720545aa73634.git
https://gist.github.com/biacunha/d98edab302865ea2273b681d8b0323db
https://gist.github.com/biacunha/e53e631411952ea2099720545aa73634#file-frete-cpp
Mapa
Conhecimento prévio necessário:
- Flood Fill (Aula 9)
Há apenas uma rota entre as posições inicial e final de Hermione. Podemos então localizar a posição marcada com o ‘o’ e fazer uma DFS a partir daí para saber qual a última marcada com um ‘H’ a qual conseguimos chegar. Segue código.
https://gist.github.com/biacunha/db0f2f4e0246600563d974e3cc54ef51
Cortando papel
Conhecimento prévio necessário:
- Vector e pair (Aula 10)
A solução mais ingênua para essa questão é testar todas as alturas possíveis em que se pode cortar o papel, subindo a linha de corte. Essa ideia não passaria no tempo, pois a complexidade é O(H), e H tem valor máximo 10^9. Porém, não é necessário checar todas as alturas, pois quantidade de pedaços só muda quando passamos do topo de alguns retângulos específicos. Perceba que se a cortarmos a figura próximo à base, ela será dividida em dois:
Esse é o menor número de pedaços que conseguimos com um corte. Se cortarmos logo acima do retângulo 9 (sendo o primeiro numerado 1), o menor, o número de pedaços aumenta para três.
Porém, não há diferença entre cortar acima dos retângulos 2 e 13 ou cortar acima do 3, ambos resultam em seis pedaços.
Isso porque o 2 e o 13, assim como o 9 e o 11, são vales: um retângulo ou série de retângulos adjacentes com menor altura que ambos os seus vizinhos. Se a linha de corte for subindo pela imagem, toda a vez que passar por um vale, a quantidade de pedaços aumenta em 1, pois o que era um só pedaço agora está separado pelo vale.
Observe que quando a linha passa de um pico, ou seja, um retângulo ou série de retângulos adjacentes com maior altura que ambos os seus vizinhos, a quantidade de pedaços diminui em um:
A quantidade de pedaços de papel só muda quando a linha de corte passa por picos ou vales.
Para obter a melhor resposta, podemos primeiro salvar as alturas lidas na entrada h em um vetor, chamado aqui de retangulos. Sabendo que retângulos adjacentes de mesma altura fazem parte do mesmo pico ou vale, vamos salvar apenas os que não são iguais ao último adicionado (if(h != retangulos.back()) retangulos.push_back(h);). Também por praticidade, adicionamos um elemento 0 no começo e no final do vetor. Assim, podemos comparar a primeira e a última altura h com os elementos anteriores e seguintes sem problemas.
Os retângulos que nos interessam são os picos e vales. Criamos um vetor pv que guarda os retângulos com essas características. Cada elemento terá um par de inteiros formado pela altura do retângulo e 1 ou -1, assinalando se ele é pico ou vale respectivamente.
Então, criamos uma variável qtd, que guarda a quantidade de pedaços de papel. Em seguida, passamos por cada pv em ordem crescente de altura (basta ordenar pelo primeiro elemento antes de percorrer), atualizando qtd de acordo com os picos e vales encontrados (qtd+=retangulos[i].second). Para conseguir a resposta, basta ter uma variável maior que guarda o maior valor de qtd até então (maior=max(maior, qtd)).
https://gist.github.com/biacunha/e53e631411952ea2099720545aa73634