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

Ônibus

Comentário escrito por Estela Baron

Conhecimento prévio necessário:

Busca em Grafos

Nesse problema, temos um conjunto de cidades e várias linhas de ônibus, ou seja, temos a representação de um grafo - os vértices são as cidades e as arestas são as linhas. Além disso, como todas as cidades estão conectadas em uma mesma componente e tem exatamente $N-1$ linhas, podemos dizer que esse grafo é uma árvore. Esse último fato não é muito importante para resolver esse problema, mas pode ser útil para outros.

Observe que o enunciado nos pede a distância entre dois pontos. Uma propriedade interessante de uma árvore (um tipo de grafo) é que existe exatamente um caminho entre dois vértices. Assim, podemos realizar uma busca - no caso a bfs- para encontrar a distância entre as duas cidades. Com esse algoritmo, encontramos o menor percurso, o qual coincide com o caminho que estamos procurando.

Vamos recapitular como funciona esse algoritmo:

iniciamos com uma fila com os vértices a serem analisados, enquanto a fila não estiver vazia, pegamos o primeiro da fila
vemos todos os vizinhos dele, se eles já tiverem sido visitados, pulamos para os outros
caso contrário, definimos a distância do vizinho como sendo a distância da cidade atual + 1 e adicionamos o novo vértice na fila
quando todos os vértices adjacentes tiverem sido visitados, tiramos o vértice atual da fila e continuamos até não restar mais nenhum

Ao final, teremos calculado a distância de todas as cidades para o vértice $A$ . Com isso, basta imprimir a distância de $B$ .

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