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:
https://gist.github.com/rogerioagjr/1c760aeb1fde244b5ec3
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.
https://gist.github.com/rogerioagjr/a8ff895cad23a7ca7843
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:
https://gist.github.com/rogerioagjr/c8ddcbd38d450d25e17f
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:
https://gist.github.com/rogerioagjr/6f570b92623f796ba16b
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.