Comentário NOIC OBI 2015 - Fase 2 - Programação Nível Júnior

Comentário por Rogério Júnior

Para ver o caderno de tarefas da segunda fase da Programação Nível Júnior da OBI 2015, clique aqui.

Impedido!

Conhecimento prévio necessário:

1. Entrada e saída (Aula 1 do Curso Noic)
2. Estruturas condicionais (Aula 2 do Curso Noic)

O enunciado do problema é bem simples e a tarefa é bem direta:

Dadas as posições desses três jogadores, no momento exato do lançamento, haverá impedimento se e somente se a seguinte condição for verdadeira:

(R >50) e (L < R) e (R > D)

A regra parece estranha, não é mesmo? Mas a gente nem precisa entender a lógica dela. O seu programa deve apenas determinar, dadas as três posições L; R e D, se há ou não impedimento, implementando exatamente a condição acima

Inicialmente, vamos declarar e salvar os valores de l, r e d, que estarão nessa ordem na entrada. Feito isso, vamos usar um if para verificarmos se a condição do enunciado foi atendida ("if(r>50 && l<r &&  r>d)"). Se o jogador estiver impedido, imprimimos uma única linha com o caractere 'S' ("printf("S\n");"). Se ela não for, imprimo o caractere 'N' ("else printf("N\n");"). Segue o código para melhor entendimento:

Torre

Conhecimento prévio necessário:

1. Vetores e matrizes (Aula 3 do Curso Noic)

A tarefa é clara: devemos encontrar o peso de cada uma das casas do tabuleiro para então descobrirmos qual delas tem o maior. Uma abordagem ingênua para o problema seria, para cada casa, somar, uma a uma, todas as casas da linha e da coluna em que nos encontramos. Tal cálculo, entretanto, tem complexidade O(n), pois cada linha ou coluna tem, no máximo, n casas. Para calcularmos o peso de todas as casas, deveríamos realizar essa operação n² vezes (pois são n² casas), o que daria uma complexidade final de n² * O(n) = O(n³).

Infelizmente, o valor de n vai até 1000, o que é muito grande para uma complexidade dessas e o programa acabaria levando TLE (Tempo Limite Excedido). Note, porém, que recalculamos várias vezes a soma de uma mesma linha, o que é uma tremenda perda de tempo, já que poderíamos calcular a soma de cada linha apenas uma vez u usá-la sempre que fosse necessária. Para isso, vamos salvar o tabuleiro em uma matriz de inteiros de nome tab  dimensões 1010 x 1010. Nela, a casa tab[i][j] guarda o valor da casa do tabuleiro da linha i e coluna j. Além disso vamos declarar dois vetores de inteiros com 1010 posições cada: o linha e o coluna. Desse modo, linha[i] irá guardar a soma de todos os elementos da linha i enquanto que coluna[j] irá guardar a soma de todos os elementos da coluna j.

Vamos agora preencher os valores de linha e coluna. Declaremos eles como globais (fora da main) para que todos os seus valores comecem zerados. Agora, vamos percorrer todas as linhas da matriz, somando cada elemento de cada uma delas na posição dessa linha do vetor linha. Vamos fazer um for que percorrerá todas as linhas ("for(int i=1; i<=n; i++)"). Agora, para cada linha i, vamos fazer um for que percorre todos os seus elementos e soma seu valor em linha[i] ("for(int j=1; j<=n; j++) linha[i]+=tab[i][j];"). Feito isso, teremos salvo a soma de todas as linhas. Agora, basta fazermos o mesmo com as colunas, com o comando: ("for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) coluna[i]+=tab[j][i];").

Agora que já temos todas as somas salvas, podemos calcular o peso de cada casa em O(1) e descobrir qual delas é a maior de maneira rápida. Vamos declarar uma variável resp que começa com valor -INF, onde INF é um número bem grande (eu geralmente uso 0x3f3f3f3f, pois ele pode ser multiplicado por 2 sem que ocorra overflow e ser usado na função memset). Feito isso, vamos percorrer todo o tabuleiro, olhando o peso de cada casa. Se o peso for maior que resp, atualizamos o valor de resp para o peso calculado, pois ele é o maior já encontrado. Isso pode ser feito fazendo resp receber o máximo entre o peso e resp. Após percorrermos todo o tabuleiro, basta imprimirmos o valor salvo em resp.

Mas como calcular o peso de uma casa? Suponha que estamos na casa (i,j). Seu peso será a soma de toda a linha i e de toda a coluna j. Porém, o valor da casa (i,j) está tanto na soma da linha como na soma da coluna, logo estamos contando-o duas vezes. Deste modo, temos que subtrair duas vezes seu valor da soma da linha i com a coluna j, para que ele não seja contado. O valor da casa (i,j) está salvo em tab[i][j], a soma da linha i está em linha[i] e a da coluna j está em coluna[j]. Assim, o peso da casa (i,j) é linha[i]+coluna[j]-2*tab[i][j]. Segue o código para melhor entendimento:

Código

Conhecimento prévio necessário:

1. Vetores e matrizes (Aula 3 do Curso Noic)

Neste problema, a abordagem mais ingênua funciona. Se ele pede todas as vezes em que o padrão "100" aparece na sequência, vamos olhar todas as suas posições e ver se ela é o começo de um padrão "100" (ou seja, se ela é um "1" e as duas posições seguintes são "0"). Primeiramente, vamos ler a sequência e guardá-la em um vetor de inteiros de 10100 posições e nome seq. Vamos guardar uma variável resp que começa com valor igual a 0. Depois, usaremos um for para percorrermos toda a sequência ("for(int i=1; i<=n-2; i++)"). Note que só vamos até o n-2 pois não há como um padrão de 3 números (100) começar quando faltam menos de três números para que a sequência acabe. Agora, para cada posição i vamos verificar se existe um padrão "100" que começa exatamente nela, ou seja, veremos se n[i]=1, n[i+1]=0 e n[i+2]=0. Caso isso ocorra, encontramos mais um padrão 100 e adicionamos uma unidade ao valor de resp ("if(n[i]==1 && n[i+1]==0 && n[i+2]==0) resp++;"). Feito isso, basta imprimirmos o valor de resp. Segue o código para melhor entendimento:

Se você ainda tiver alguma dúvida em algum dos problemas, vá para a página inicial do Curso Noic de Informática e preencha o formulário para nos enviar sua dúvida.