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:
| // 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.
| // 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:
| // 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:
| // 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.
