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

Comentário por Rogério Júnior

Para ver o caderno de tarefas da primeira fase da Programação Nível 2 da OBI 2015, clique aqui.

Cobra Coral

Note que as cores da coral falsa consistem da repetição de uma sequência de três cores: BVP. Desse modo, em um intervalo de quatro cores, teremos a sequência mostrada anteriormente completa e ainda sobrará uma cor, ou seja, repetiremos a primeira cor. Deste modo, a sequência dada na entrada somente representará uma cobra coral falsa se o primeiro e o último número forem iguais. Por isso, basta que leiamos os quatro números e os salvemos nas variáveis a, b, c e d. Feito isso, se o primeiro e o último números (a e d) forem iguais, a coral será falsa e deveremos imprimir uma linha com o caractere 'F' ("if(a==d) printf("F\n");"). Caso contrário, a sequência representará uma coral verdadeira e demos imprimir uma única linha com o caractere 'V' ("else printf("V\n");"). Segue o código comentado.

Quebra-Cabeça

Cada peça contêm três informações: o número do lado direito, o número do lado esquerdo e o caractere no meio. Desse modo, posso representar o quebra-cabeças como um vetor de pares de nome lista, onde cada par terá um caractere como primeiro elemento e um inteiro como segundo elemento. Desse modo, o o índice de uma posição do vetor será o número esquerdo da peça que ele representa, o primeiro elemento do para será o caractere do meio da peça e o seu segundo elemento  será o número direito da peça. Para usarmos um par, usaremos o objeto já implementado do C++ pair. Se você não o conhece ou não sabe utilizá-lo, clique aqui para ver a aula do Curso Noic sobre estruturas do C++.

Desse modo, ler o quebra cabeça consiste em, para cada peça da entrada, lermos o valores de e, c e d de cada peça (número esquerdo, caractere e número direito, respectivamente) e adicionarmos essa peça a lista, salvando, na posição e do vetor, o par (c, d) ("lista[e]=make_pair(c, d);").

Agora precisamos montar o quebra-cabeça. Vamos salvar na variável prox, o número da esquerda da próxima peça que irei imprimir. Assim, ele deve começar com o valor zero e a montagem deve parar quando seu valor for 1, pois ele é o número da direita da última peça. Assim, criaremos um while que irá se repetir enquanto prox for diferente de 1. Em cada repetição do loop, devemos imprimir o caractere da peça cujo número esquerdo é prox. Para isso, devo acessar a posição prox de lista e imprimir o elemento que guarda este caractere do meio, que é o primeiro ("printf("%c", lista[prox].first);"). Feito isso, devo salvar que a próxima peça a ser impressa será a indicada pelo número direito da peça atual. Por isso, prox deve receber o valor do segundo membro (que guarda o número da direita da peça) da peça que acabamos de imprimir (aquela que atualmente está na posição prox) ("prox=lista[prox].second;").

Quando o loop terminar, basta imprimir a quebra de linha. Segue o código comentado:

Família Real

A família pode ser representada como um grafo direcionado, onde os vértices são os familiares e uma aresta de v para u indica que v é o pai de u. Como são n vértices e n-1 arestas em um grafo conexo, então o grafo será uma árvore. Se você não conhece ou não sabe implementar um grafo, clique aqui para ver a aula introdutória do Curso Noic sobre grafos . Vamos salvar o grafo como uma lista de adjacência, em um vetor de vectors de int de nome lista. Vamos declarar os vetores geracao e qtd, que guardarão, respectivamente, a geração, o nível de cada familiar e a quantidade de descendentes em cada geração. O inteiro h irá guardar a quantidade de gerações. Agora vamos percorrer o grafo com uma DFS para preenchermos esses vetores com os dados corretos. Se você não conhece ou não sabe utilizar uma DFS, clique aqui para ver a aula do Curso Noic sobre Flood Fill.

A DFS que faremos não precisará marcar os vértices já visitados, visto que nunca chegaremos ao mesmo vértice duas vezes, por o grafo ser uma árvore. Ao invés disso, ela irá receber, também como parâmetro, o nível l, ou seja, a geração em que o vértice está, para marcá-la em geracao e depois adicionar uma unidade em qtd[l]. Além disso, se ela chegar em uma geração mais alta que a maior já encontrada, devemos atualizar o número de gerações h para l. Depois, para cada um dos filhos do vértice, chamo a DFS para eles e aumento o nível em uma unidade.

Depois que todo o grafo for percorrido, basta criarmos o vetor presenca, que irá salvar quantos membros de cada geração da família foram para a festa. Para preenchê-lo, basta lermos os números dos m presentes e adicionar uma unidade na presença da geração de cada um deles. Depois de lermos toda a entrada, basta usarmos um for para, em cada geração i, imprimimos o percentual de presença, que será uma double representada pela fórmula 100.00*presenca[i]/qtd[i]. Nao podemos esquecer que a precisão deve ser de duas casas decimais, logo devemos usar o comando "printf("%.2lf  ", 100.00*presenca[i]/qtd[i]);". Veja que é muito importante usarmos 100.00 ao invés de 100 pois, para o C++, a divisão de dois inteiros (presenca[i]/qtd[i]) retorna outro inteiro, mas a presença de uma double (100.00) transforma toda a expressão em uma double. No fim da saída, basta imprimir a quebra de linha. Segue o código comentado:

Caixinha de Palitos

Este problema simples de contagem foi provavelmente o problema mais difícil da prova por se tratar de um algoritmo menos conhecido que os das outras questões. Primeiramente, vamos declarar a variável resp (de valor inicial 0) como long long int, pois a resposta pode superar o valor de um int. A ideia é bem simples: vamos usar um for para simular todas as possíveis quantidades de palitos que o primeiro amigo pode receber (1 a m). Feito isso, veremos qual a menor e a maior quantidade que o segundo amigo pode pegar sem que o que sobre (parte do terceiro amigo) seja maior que m. No fim do for, basta adicionar a resp a quantidade de números compreendidos entre a menor e a maior quantidade que o segundo amigo pode pegar.

Observe agora como implementar a ideia. Na i-ésima repetição do for, vamos declarar o int resto, que será o valor que ainda resta ser dividido entre os dois amigos restantes, após o primeiro amigo ter ficado com i palitos. Se esse valor for maior que o dobro de m, então esta quantidade não pode ser dividida entre dois amigos e não devemos fazer nada nesta repetição do loop ("if(resto>2*m) continue;"). Caso contrário vamos declarar os inteiros menor e maior, que são a menor e a maior quantidade de palitos que o segundo amigo pode pegar. Se o segundo amigo pegar menos que resto-m palitos, então o terceiro teria que pegar mais que m para que todos os palitos fosse divididos, o que não é permitido, logo menor >= resto-m. Porém, m pode ser maior ou igual a resto e, nesse caso, devemos nos lembrar que cada amigo deve receber no mínimo um palito, logo resto >=1. Como essas são as únicas restrições e queremos minimizar o valor de menor, ele receberá o maior valor dentre 1 e resto-m, pois não pode ser inferior a nenhum desses dois ("menor=max(1, resto-m);"). O maior número de palitos que o segundo amigo pode pegar é menor ou igual que m, logo maior<=m. Porém, devemos nos lembrar que ele não pode pegar todos os palitos que restam (pois o terceiro amigo deve receber pelo menos um palito), logo maior<=(resto-1). Como essas são as duas únicas restrições e queremos maximizar o valor de maior, ele receberá o menor valor dentre m e resto-1, pois não pode superar nenhum desses dois ("maior=min(m, resto-1);"). Agora, basta adicionarmos a resp  quantidade de valores entre menor e maior, inclusive, que serão exatamente todas as maneiras de o segundo amigo receber palitos, já determinando a quantidade do terceiro ("resp+=maior-menor+1;").

Após o fim deste for, basta imprimirmos o valor de resp, seguido da quebra de linha. Segue o código comentado:

Banco Inteligente

Este problema é uma pequena variação de um conhecido problema de Programação Dinâmica chamado Coin Change, ou Troco de Moedas, em tradução livre. Se você não conhece Programação Dinâmica ou não sabe como usá-la, clique aqui para ver a aula do Curso Noic sobre esse assunto. Por ser mais intuitiva e simples de implementar, usaremos uma abordagem no estilo Top-Down, em que o estado da DP será determinado por dois parâmetros: int resta, que é o valor que ainda resta ser atingido usando as cédulas e o int tipo, que é quais tipos de notas ainda posso usar para alcançar o valor desejado (todas a partir de tipo).

A recursão é bem simples e muito similar à feita para resolver o problema Troco, da segunda fase da P1 de 2013, com solução do Noic aqui. Já que queremos calcular o número de maneiras de conseguirmos tal valor, este resultado pode ser bem grande e é melhor que a função recursiva retorne um long long int. A função terá o nome dp e a tabela de DP terá o nome tab e começará com todos os estados ainda não calculados com valor igual a -1 (isso será feito com um memset). Como em qualquer recursão, começaremos pelos casos de base. Se o valor que ainda resta ser alcançado é zero, então existe uma única maneira de o atingirmos: não escolhendo nenhuma nota, logo devemos retornar 1 ("if(!resta) return 1LL;"). Se este valor a ser alcançado é negativo ("if(resta<0)"), nunca conseguiremos juntá-lo usando notas, pois todas têm valores positivos. Além disso, se já tivermos olhado todas os seis tipos de notas ("if(tipo>6)"), então não há mais notas que possamos usar e por isso não conseguiremos juntar o valor desejado. Em qualquer um dos dois casos anteriores, não há maneiras de juntarmos o valor desejado, logo a função deve retornar 0 ("return 0LL;"). Além disso, se o estado atual da DP já tiver sido calculado anteriormente, devemos retornar o valor que temos salvo para ele na tabela de DP ("if(tab[resta][tipo]>=0) return tab[resta][tipo];").

Se a função não retornar nos casos base, deveremos utilizar recursão para encontrarmos seu valor. Sejam notas e valor os vetores onde estão salvos a quantidade e o valor de cada um dos seis tipos de cédulas diferentes. No atual estado da DP, podemos colocar qualquer quantidade notas do tipo tipo que não ultrapasse a quantidade de notas[tipo] (inclusive nenhuma). Por isso, para calcularmos o valor da função, vamos declarar uma long long int de nome total, que começará com zero e receberá a soma das maneiras de alcançarmos a quantia necessária usando cada uma das possíveis quantidades de cédulas, do tipo que estamos olhando, que temos à disposição. Para isso, usaremos um for para percorrer todas as possíveis quantidades, fazendo um inteiro i variar de 0 a notas[tipo]. Desse modo, a quantidade de maneiras de conseguirmos juntar o valor resta usando i cédulas de valor valor[tipo] (sem usar tipos anteriores) é a quantidade de maneias de juntarmos o que falta (resta-i*valor[tipo]) usando somente notas que vêm após o tipo atual, ou seja, a partir de tipo+1. Ora! Esse é exatamente o valor de dp(resta-i*valor[tipo], tipo+1). Note ainda que se o valor das i  notas do tipo atual ultrapassarem a quantia que resta juntar, podemos parar o for, pois não será possível juntar a quantia e qualquer quantidade de notas maior que i também ultrapassará o valor desejado ("if(resta<i*valor[tipo]) break;"). Após  o for, basta que a função retorne o valor de total, salvando este resultado em tab[resta][tipo], para evitar recálculo futuro. Note que, nos casos base, usei "LL" após os valores a serem retornados, para que o fossem na forma de inteiro 64-bit, que é o tipo da função (long long).

Implementada a a função dp, basta lermos o valor s desejado, as quantidades disponíveis de cada nota, usarmos um memset para marcarmos todas as posições de tab com -1 (ainda não calculada) e imprimirmos a quantidade de maneiras de juntarmos valor s usando as todas cédulas disponíveis a partir do primeiro tipo, chamando a função dp(n, 1). Segue o código comentado:

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.