Comentário por Rogério Júnior
Para ver o caderno de tarefas da primeira fase da Programação Nível 1 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; | |
| } |
Linhas Cruzadas
Este problema é apenas uma versão da clássica contagem do número de inversões de um vetor. Para que possamos explicar o algoritmo com conteúdo do site, usaremos o algoritmo do Merge Sort para contarmos esse número de inversões. Para ver o algoritmo, sua explicação e implementação, veja a aula do Curso Noic de ordenação e procure pelo tópico Merge Sort para entender o algoritmo de ordenação, olhando posteriormente o último código da aula e sua prévia explicação para entender como usá-lo para contar o número de inversões em um vetor.
Como o algoritmo está explicado na aula, basta que vejamos como usar a contagem de inversões em um vetor para resolver o problema. Vamos usar um array de inteiros de nome vetor para guardarmos os pares de pregos ligados por uma linha. Desse modo os índices do vetor representarão os pregos na vertical, e o inteiro salvo em cada posição, os pregos na horizontal. Desse modo, se os pregos i (na vertical) e j (na horizontal) estiverem ligados, então vetor[i]=j.
Vamos observar agora quantas linhas cruzam a linha que liga o prego i ao prego j. Suponha que a linha que liga os pregos a (na vertical) e b (na horizontal) cruza a linha que liga i e j. Se a>i então b<j, pois se a>i e b>j, a linha que liga a e b estaria completamente acima da que liga i e j. De maneira análoga, se a<i, então b>j, pois se a<i e b<j, então a linha que liga a e b estaria completamente abaixo da que liga i e j. Desse modo, a linha que liga i e j cruza a linha que liga a e b se, e somente se, a>i e b<j, ou a<i e b>j. Vamos olhar o que isso significa em vetor. Sabemos que i e a são posições de vetor, enquanto que j e b são elementos salvos nessas posições, respectivamente. Se a<i, então o elemento b (que está salvo na posição a) vem antes do elemento j (que está salvo na posição i). Se as linhas se cruzam, então b>j, logo, para procurarmos todos as linhas que cruzam a linha (i, j) que atendem à condição a<i e b>j, devo procurar todos os elementos do vetor que vêm antes da posição i e que são maiores que o elemento nela salvo (j). A outra condição (a>i e b<j) pode ser analisada de maneira análoga, e se resume a procurar todos os elementos que vêm após a posição i e que são maiores que o elemento nela salvo (j). Logo, cada cruzamento entre linhas é representado por um par (v, u) em vetor, de modo que v<u e vetor[v]>vetor[u], ou seja, uma inversão no vetor. Por isso, encontrar o número de cruzamentos entre as linha é o mesmo que encontrar o número de inversões em vetor.
Basta agora que eu leia os valores de n e dos elementos de vetor (que já é dado de graça na entrada, pois o i-ésimo número representa o prego na horizontal que se liga com o prego vertical i). Feito isso, basta eu imprimir o número de inversões em vetor usando o algoritmo de Merge Sort, que é exatamente o código mostrado na aula de ordenação, apenas com o cuidado de declarar a Merge Sort como long long int, para que não corramos o risco de o número de inversões .superar o valor máximo de um int. 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
| // Linhas Cruzadas - F1PJ - OBI 2015 | |
| // Rogério Júnior | |
| // Complexidade: O(n*log(n)) | |
| #include <cstdio> // scanf e printf | |
| #define MAXN 100100 // defino o limite de n | |
| typedef long long int lli; // defino o tipo lli como long long int | |
| int n, vetor[MAXN], aux[MAXN]; // declaro as variáveis e vetores que vamos usar | |
| lli merge_sort(int ini, int fim){ // declaro a função merge_sort, que agora retorna um int | |
| if(ini==fim) return 0; // se o intervalo tiver um único elemento, ele não tem inversões | |
| // caso o contrário, declaro a variável invers, que começa com a soma das inversões das duas metades | |
| lli invers=merge_sort(ini, (ini+fim)/2) + merge_sort((ini+fim)/2+1, fim); // observe que chamei a recursão e ordenei as metades | |
| int tam=0, j=(ini+fim)/2+1; // declaro tam e j, como feito no código anterior do merge_sort | |
| for(int i=ini; i<=(ini+fim)/2; i++){ // para cada posição da metade da esquerda | |
| while(j<=fim && vetor[j]<vetor[i]){ // procuro os elementos da metade da direita menores que i | |
| // os adiciono ao vetor aux | |
| aux[tam]=vetor[j]; | |
| tam++; | |
| j++; // passo para o próximo elemento | |
| invers+=(ini+fim)/2-i+1; // e adicino o número de inversões em metades diferentes com o elemento j | |
| } | |
| // adiciono o elemento i | |
| aux[tam]=vetor[i]; | |
| tam++; | |
| } | |
| // adiciono o resto dos elementosda segunda metade | |
| while(j<=fim){ | |
| aux[tam]=vetor[j]; | |
| tam++; | |
| j++; | |
| } | |
| for(int i=ini; i<=fim; i++) vetor[i]=aux[i-ini]; // e troco os valores do vetor original pelos ordenados | |
| return invers; // retorno o número de inversões calculado | |
| } | |
| int main(){ | |
| scanf("%d", &n); // leio o valor de n | |
| for(int i=1; i<=n; i++) scanf("%d", &vetor[i]); // leio os valores do vetor | |
| printf("%lld\n", merge_sort(1, n)); // imprimo a quantidade de inversões do vetor | |
| 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 usar 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; | |
| } |
Arquivos
A ideia deste problema é um algoritmo guloso, que tenta sempre juntar o menor e o maior arquivo disponíveis em uma mesma pasta. Para isso, vamos salvar o número de arquivos na variável n, o número de pastas em resp (que começará com o valor zero) e os tamanhos de cada arquivo em um vetor de inteiros de nome file, indexados de 1 a n. Assim, o valor salvo em file[i] será o tamanho do i-ésimo arquivo. Agora precisamos ordenar o vetor pelo tamanho de seus elementos e, para isso, usaremos a função sort, da biblioteca algorithm, com o comando "sort(file+1, file+n+1);". Se você não conhece o sort ou não sabe como ele funciona, clique aqui para ver a aula do Curso Noic sobre ordenação.
Agora, vamos percorrer o vetor, tentando juntar o menor e o maior arquivo disponíveis. Para isso, vamos declarar a variável menor, que será a posição do menor arquivo que ainda não foi guardado em uma pasta (começando, portanto, com valor 1). Agora, vamos percorrer file do maior arquivo para o menor, colocando-os em pastas. Para isso, vamos usar um for que fará a variável maior percorrer os valores de n até menor (pois lembre-se que este é a posição do menor valor disponível). Em cada repetição do for, irei criar uma nova pasta, ou seja, adicionarei uma unidade ao valor de resp. Feito isso, irei verificar se o menor arquivo cabe nessa pasta em que acabei de colocar o maior, ou seja, se a soma de seus tamanhos não ultrapassa b. Se for possível, coloco o menor na pasta, ou seja, farei o novo menor arquivo disponível receber o sucessor do atual, aumentando uma unidade no valor de menor ("if(file[maior]+file[menor]<=b) menor++;").
Após percorrermos todo o vetor, basta imprimir o valor salvo em resp, seguido da quebra de linha. 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
| // Arquivos - F1P1 - OBI 2015 | |
| // Rogério Júnior | |
| // Complexidade: O(n*log(n)) | |
| #include <cstdio> // scanf e printf | |
| #include <algorithm> // sort | |
| using namespace std; | |
| #define MAXN 100100 // defino o valor máximo de n | |
| int n, b, resp, file[MAXN]; // variáveis que vou usar | |
| int main(){ | |
| scanf("%d %d", &n, &b); // leio os valores de "n" e "b" | |
| for(int i=1; i<=n; i++) scanf("%d", &file[i]); // leio os tamanhos dos arquivos | |
| sort(file+1, file+n+1); // ordeno o vetor pelo tamanho dos arquivos | |
| int menor=1;; // inicializo menor e maior com os valores 1 e n, respectivamente | |
| // enquanto houver arquivo disponível | |
| for(int maior=n; maior>=menor; maior--){ | |
| // aumento o valor de resp, pois o maior arquivo será guardado em uma nova pasta | |
| resp++; | |
| // se couberem dois (o maior e o menor), coloco o menor na mesma pasta | |
| // e digo que o novo menor elemento será o seguinte em "file" | |
| if(file[menor]+file[maior]<=b) menor++; | |
| } | |
| printf("%d\n", resp); // por fim, imprimo a resposta seguida de quebra de linha | |
| 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.