Comentário por Rogério Júnior
Para ver o caderno de tarefas da primeira fase da Programação Nível Júnior da OBI 2015, clique aqui.
Móbile
Vamos ler os quatro inteiros da entrada e salvá-los nos inteiros a, b, c e d, respectivamente. A questão deixa claro que o móbile somente estará equilibrado se:
- a=b+c+d
- b+c=d
- b=c
Na linguagem C++, essas condições são escritas da seguinte forma:
- a==b+c+d
- b+c==d
- b==c
Agora basta usarmos um if para checarmos se as três condições foram atendidas simultaneamente, imprimindo uma linha com o caractere 'S', caso isso ocorra, com o comando "if(a==b+c+d && b+c==d && b==c) printf("S\n");". Caso contrário, devo imprimir uma linha com o caractere 'N', usando o comando "else printf("N\n");". Se você não conhece o if e else ou seu operadores lógicos, clique aqui para ver a aula do Curso Noic sobre esse assunto. Segue o código comentado:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Móbile - F1PJ - OBI 2015 | |
| // Rogério Júnior | |
| // Complexidade: O(1) | |
| #include <cstdio> // scanf e printf | |
| int main(){ | |
| // declaro e leio os valores de "a", "b", "c" e "d" | |
| int a, b, c, d; | |
| scanf("%d %d %d %d", &a, &b, &c, &d); | |
| // se as condições do problema forem atendidas, imprima o caractere 'S' | |
| if(a==b+c+d && b+c==d && b==c) printf("S\n"); | |
| // caso contrário, imprima uma linha com o caractere 'N' | |
| else printf("N\n"); | |
| return 0; | |
| } |
Fita Colorida
A primeira coisa a ser feita é ler a fita e salvá-la em um vetor de int, de nome fita, por exemplo. Se você não sabe o que é um vetor, clique aqui para ver a aula do Curso Noic sobre esse assunto. Vamos pensar da seguinte maneira: para cada posição da fita, calcularemos a distância até o zero mais próximo da esquerda (e a salvaremos no vetor esq), depois até o zero mais próximo da direita (e a salvaremos no vetor dir), e usaremos a menor entre as duas. Calcular o mais próximo à esquerda é simples: percorro o vetor fita da esquerda para a direita com um for. Em cada posição i, se o tom nela for zero, então a distância é zero ("if(fita[i]==0) esq[i]=0;"), pois sem nenhum movimento chego no tom zero (que é ele mesmo). Caso contrário, a distância até o zero mais próximo à esquerda será a distância que a casa à esquerda está desse zero, mais um ("else esq[i]=esq[i-1]+1;"). Ou seja, vejo quantos movimentos teria que fazer para ir do zero à casa à esquerda e depois adiciono 1 (pois ainda estaria a uma posição de distância). Feito isso, calculo as distâncias para o zero à direita de maneira análoga, mas agora tenho que percorrer o vetor da direita para a esquerda.
Observe que a ordem em que percorro o vetor é muito importante. Quando procuro o zero mais próximo à esquerda, preciso já ter calculado o vizinho esquerdo da posição que estou olhando, para acessá-lo no caso em que a resposta é ele mais um. A maneira de sempre ter calculado o vizinho à esquerda é percorrer o vetor da esquerda para a direita. Por esse motivo, quando procuro o vizinho da direita, tenho que percorrê-lo da direita para a esquerda.
Agora basta imprimir os tons. Para cada posição, a menor distância para um zero é a menor dentre a distância para o zero mais próximo à esquerda e o mais próximo à direita. Entretanto, não basta imprimí-la. Se ela for maior que 9, devo imprimir 9, ou seja, devo imprimir o menor entre 9 e a distância calculada. Segue o código comentado:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Fita Colorida - F1PJ - OBI 2015 | |
| // Rogério Júnior | |
| // Complexidade: O(n) | |
| #include <cstdio> // scanf e printf | |
| #include <algorithm> // min | |
| using namespace std; // algorithm | |
| #define MAXN 10100 | |
| #define INF 999999999 | |
| int n, fita[MAXN], esq[MAXN], dir[MAXN]; // variaveis e vetores | |
| int main(){ | |
| scanf("%d", &n); // leio o valor de n | |
| for(int i=1; i<=n; i++) scanf("%d", &fita[i]); // leio os tons da fita | |
| // infinito todas as distâncias | |
| for(int i=0; i<=n+1; i++) esq[i]=dir[i]=INF; | |
| // olho a distância de um zero à esquerda | |
| for(int i=1; i<=n; i++){ | |
| // se o tom for zero, é zero | |
| if(fita[i]==0) esq[i]=0; | |
| // se não, é a distância do tom à esquerda mais 1 | |
| else esq[i]=esq[i-1]+1; | |
| } | |
| // de maneira análoga, olho a distância de um zero à direita | |
| for(int i=n; i>0; i--){ | |
| if(fita[i]==0) dir[i]=0; | |
| else dir[i]=dir[i+1]+1; | |
| } | |
| // e imprimo, para cada casa, a menor entre a distância de um zero à esquerda e um à direita | |
| // mas se 9 for menor que essa distância, imprima 9 | |
| for(int i=1; i<=n; i++) printf("%d ", min(9, min(esq[i], dir[i]))); | |
| // e imprimo a quebra de linha | |
| printf("\n"); | |
| return 0; | |
| } |
Prêmio do Milhão
Vamos ler o número de dias e salvar no inteiro n. Iremos também declarar os inteiros qtd e dia, que guardarão, respectivamente, quantos acessos a página já teve e o dia em que ela obteve 1 milhão. Todos serão declarados como globais para que já comecem com o valor zero. Feito isso, usaremos um for de 1 a n, para lermos o número de acessos de cada um dos n dias. A cada repetição do for, iremos declarar o inteiro acessos para nele salvarmos a quantidade de acessos que a página teve no dia i. Feito isso, se o valor salvo em dia for diferente de zero, então a página já obteve 1 milhão de acessos e a resposta já está salva nessa variável, ou seja, não precisamos fazer mais nada e usamos o comando "continue;". Caso contrário, os comandos do for irão seguir, e devo adicionar o valor lido à quantidade total de acessos ("qtd+=acessos;"). Agora, se esse total de acessos superar 1 milhão, então encontrei o dia em que a página obteve 1 milhão de acessos, e devo salvá-lo na variável dia ("dia=i;").
é muito importante que usemos o comando continue ao invés de break quando não quisermos mais fazer nada, pois se pararmos o loop, a entrada não será completamente lida, mas OBI exige que ela seja. Ao final da leitura da entrada, basta imprimir uma única linha com o valor salvo na variável dia ("printf("%d\n", dia);"). Segue o código comentado:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Prêmio do Milhão - F1PJ - OBI 2015 | |
| // Rogério Júnior | |
| // Complexidade: O(n) | |
| #include <cstdio> // scanf e printf | |
| int n, qtd, dia; // declaro as variáveis "n", "qtd" e "dia" | |
| int main(){ | |
| scanf("%d", &n); // leio o número de dias | |
| for(int i=1; i<=n; i++){ // para cada dia | |
| // declaro e leio o número de acessos | |
| int acessos; | |
| scanf("%d", &acessos); | |
| // se a página já alcançou 1 milhão, nao faço nada, dou continue | |
| if(dia!=0) continue; | |
| // caso contrário | |
| qtd+=acessos; // adiciono os acessos do dia ao número total de acessos | |
| // e se o total ultrapassar 1 milhão, salvo o dia atual em "dia" | |
| if(qtd>=1000000) dia=i; | |
| } | |
| // após ler a entrada, imprimo a resposta, salva em "dia" | |
| printf("%d\n", dia); | |
| return 0; | |
| } |
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.