OBI 2017 – Fase 3 – Programação Nível Junior
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 nossos materiais.
Para conferir a prova na íntegra, clique aqui.
Zip
Comentário escrito por Vitor Veiga
Conhecimento prévio necessário:
O problema nos dá quatro valores de cartas. As duas primeiras são de Lia e as duas últimas são de Carolina. Queremos saber quem vai ganhar o jogo, ou se haverá empate, seguindo as seguintes regras para calcular a pontuação de cada uma:
Se $$C1 = C2$$, $$Pontuacao = 2 * (C1+C2)$$;
Se $$C1 + 1 = C2$$, $$Pontuacao = 3 * (C1+C2)$$;
Caso contrário, $$Pontuacao = C1 + C2$$.
Assim, a estratégia será ler a entrada, calcular a pontuação de cada uma das meninas por meio das regras e analisar quem fez mais pontos. Se elas realizarem a mesma pontuação, retornamos empate.
Clique aqui para conferir o código
Gomoku
Comentário escrito por Estela Baron
Conhecimento prévio necessário:
Nesse problema, o limite já vem estabelecido e é bem pequeno. Isso nos permite verificar, para toda casa, se ela faz parte de uma coluna, linha ou diagonal vencedora. Para isso, podemos analisar quatro casos:
- se a casa atual é a primeira (esquerda para a direita) de uma linha vencedora: basta ir adicionando +1 no estado que corresponde ao eixo y e vendo se as quatro casas são iguais à atual.
- se a casa atual é a primeira (cima para baixo) de uma coluna: basta ir adicionando +1 no estado que corresponde ao eixo x e vendo se as quatro casas são iguais à atual.
Cuidado para não acessar posições que não existem, por exemplo: $$m[4][16]$$. Só precisa analisar a posição se for diferente de zero. Outra coisa é que, desse jeito, conseguimos percorrer todas as linhas e colunas possíveis.
Para as diagonais, temos que analisar dois casos:
- quando é do lado superior da direita para o lado inferior esquerdo: temos que ir adicionando +1 ao x e -1 ao y e ver se as quatro casas são iguais à atual.
- quando é do lado superior esquerdo para o lado inferior direito: temos que ir adicionado +1 ao x e +1 ao y e ver se as quatro casas são iguais à atual.
Iniciamos a resposta como $$0$$. Se as cinco posições, em algum caso, forem iguais, mudamos a resposta para a cor da pedra, 1 ou 2. Por fim, imprimimos a resposta.
Clique aqui para conferir o código
Visita entre Cidades
Comentário escrito por Enzo Dantas
Conhecimento prévio necessário:
Primeiramente, “os pares de cidades ligados diretamente por uma estrada são escolhidos de forma que sempre é possível ir de qualquer cidade para qualquer outra cidade por um, e somente um, caminho” significa que o grafo dado é uma árvore. Assim, o problema pede a distância entre dois vértices de uma árvore.
Isso pode ser achado usando uma DFS ou BFS: inicializamos a distância do vértice inicial A como 0 ($$dist[A] = 0$$). Quando estamos em um vértice u, dizemos que $$dist[v] = dist[u] + w$$, sendo $$w$$ o peso da aresta $$u \rightarrow v$$.
A resposta do problema é a distância do vértice final $$B$$, ou seja, $$dist[B]$$.
Clique aqui para conferir o código
Bits
Comentário escrito por Arthur Lobo
Conhecimento prévio necessário:
O problema nos pede para calcular quantas bitstrings (sequências com 0 e 1) existem com no máximo $$K$$ 1’s consecutivos. Problemas de contar quantos de uma coisa existem tem uma boa chance de serem resolvidos usando $$DP$$, e é o caso desse.
A $$DP$$ usada para resolver esse problema será $$dp_{i,j} = $$ quantidade de bitstrings válidas de tamanho $$i$$ com $$j$$ 1’s consecutivos no final dela. O caso base da $$DP$$ será:
- $$dp_{0,0} = 1$$
- $$dp_{0,x} = 0$$, para $$1 \le x \le K$$
Normalmente nós tentamos fazer a transição calculando $$dp_{i,j}$$ quanto estamos em $$i,j$$, que é chamado de $$DP push$$, mas para esse problema fica mais simples se considerarmos que já sabemos $$dp_{i,j}$$ quando estamos em $$i,j$$, e então atualizamos o valor das próximas $$dp_{i+1,x}$$ baseado em $$dp_{i,j}$$. Isso é chamado de $$DP pull$$.
Basta pensar como o valor de $$dp_{i,j}$$ influencia no valor das próximas $$DP$$. Inicialmente sabemos os valores de $$dp_{0,x}$$ e os valores de todas as outras $$dp$$ começam sendo 0. Vamos usar $$dp_{0,x}$$ para calcular $$dp_{1,x}$$, depois usar o de $$dp_{1,x}$$ para o de $$dp_{2,x}$$, e assim até o final (para $$0\le x \le K$$).
Quando estamos em $$i,j$$, com $$1 \le i \le N$$ e $$0 \le j \le K$$, vamos fazer as seguintes transições:
- Colocamos $$0$$ na posição $$i+1$$, então a bitstring de tamanho $$i+1$$ vai terminar com $$0$$ zeros $$\Rightarrow$$ $$dp_{i+1,0}+= dp_{i,j}$$.
- Colocamos $$1$$ na posição $$i+1$$, então a bitstring de tamanho $$i+1$$ vai terminar com $$j+1$$ uns $$\Rightarrow$$ $$dp_{i+1,j+1}+= dp_{i,j}$$. Nesse caso é preciso tomar cuidado quando $$j = K$$.
No final a nossa resposta vai ser a quantidade de bitstrings com qualquer valor entre $$0$$ e $$K$$ uns no final, então ela vai ser $$dp_{N,0}+ dp_{N,1} + … + dp_{N,K}$$. Agora basta colocar um módulo $$10^9+7$$ em tudo.
Clique aqui para conferir o código