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:

Estruturas Condicionais

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:

Matriz

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:

Busca em grafo

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:

Introdução a Programação Dinâmica

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