Aconteceu em 21 de Março de 2018 o segundo treino da disciplina TAP - Tópicos Avançados de Programação. O placar final do treino pode ser visto na imagem abaixo.
A prova foi composta por 13 problemas. Os níveis dos problemas e as respectivas técnicas que podem ser usadas para resolve-los é apresentado na tabela abaixo.
| Problema | Dificuldade | Técnica relacionada |
|---|---|---|
| A - Elf Time | 1 | ad hoc |
| B - Christmas Lights | 1 | bitmask |
| C - Large Presents | 2 | ordenação |
| D - Indecision of Reindeers | 1 | ad hoc |
| E - Senha Fixa | 1 | implementação |
| F - Array Hash | 1 | string |
| G - Máquina de Café | 2 | ad hoc |
| H - Event | 1 | matemática |
| I - Tribol | 2 | ad hoc |
| J - Arrumando as Tarefas | 2 | ordenação |
| K - Sub-prime | 2 | ad hoc |
| L - Fazendo Pandorgas | 1 | matemática |
| M - Média 2 | 1 | matemática |
A - Elf Time
Resolva este problema: URI
Dados três números inteiros N (quantidade de minutos que faltam para o fim do expediente do Ed), A e B (quantidades de minutos necessários para fabricar, respectivamente, o primeiro e o segundo presente), o exercício pede para verificar se é possível que Ed consiga fabricá-los antes que acabe o seu expediente, ou seja, A + B ≤ N .
Um exemplo de implementação segue abaixo:
B - Christmas Lights
Resolva este problema: URI
Devemos nos atentar a duas informações importantes fornecidas. A primeira consiste na quantidade máxima de lâmpadas em um grupo (50). Já a segunda está presente na seguinte frase: [...] decidiu pensar neles efetivamente como números e escreveu as representações decimais desses binários [...]. Ou seja, ela irá fornecer N números decimais representando a quantidade de lâmpadas em cada grupo, números estes que terão valores entre 0 e 250, inclusive. Definido um tipo de dado que suporte tais valores, basta contar a quantidade de 1’s consecutivos em cada valor e, para isso, podemos utilizar bitwise operations.
Um exemplo de implementação segue abaixo:
C - Large Presents
Resolva este problema: URI
Bruninho é um rapaz experto (não quer ganhar cuecas e meias de presente) ☺, irá escolher, dentre os N presentes, os K que tenham os maiores volumes. O que pode causar um pouco de confusão neste problema é como o mesmo pede para listar, na saída, os K presentes selecionados. Tais presentes devem ser listados em ordem crescente levando em consideração os seus respectivos ID's, ou seja, basicamente basta ordenar os presentes pelo critério do maior volume, depois selecionar os K primeiros (maiores volumes) e ordená-los pelo critério do menor ID. Agora só imprimir estes ID's.
Dois exemplos de implementação (primeiro em C e o segundo em C++11) seguem abaixo:
D - Indecision of Reindeers
Resolva este problema: URI
Este problema pode ser resolvido simulando a pilha de bolas de neve, no entanto existe outra forma mais simples de resolve-lo. Seja S o total de bolas, como cada Rena irá retirar uma bola por vez do topo da pilha e existem 9 Renas, então cada uma delas irá retirar no final das contas, pelo menos, S/9 bolas. A quantidade de bolas que sobrará, depois que cada uma retirar S/9 bolas, será menor que 9. Logo, precisamos saber apenas o valor do resto da divisão de S por 9, este valor representará uma Rena (nomes[S % 9], onde nomes[] é um vetor com os nomes das Renas fornecido). OBS: S % 9 nos dará a próxima Rena que irá retirar uma bola, mas o problema pede a última Rena que retirou uma bola. Para descobri-lá podemos fazer ((S-1)+9) % 9 ou basta deslocar o uma posição do vetor com os nomes para a direita.
Um exemplo de implementação segue abaixo:
E - Senha Fixa
Resolva este problema: URI
Um exemplo de implementação segue abaixo:
F - Array Hash
Resolva este problema: URI
O problema informa como cada caractere deve ser computado, basta percorrer cada linha e ir computando a soma dos valores de cada caractere.
Um exemplo de implementação segue abaixo:
G - Máquina de Café
Resolva este problema: URI
A chave deste problema está em perceber que basta colocar a máquina de café em cada andar e computar o custo total de subidas/decidas de escada para o andar em que a mesma foi colocada. Suponha que no:
1ª andar: cada um dos A2 e A3 funcionários gastarão, respectivamente, 2 e 4 minutos. Portanto, um total de 2·A2 + 4·A3 minutos serão necessários;
2ª andar: cada um dos A1 e A3 funcionários gastarão 2 minutos. Logo, um total de 2·A1 + 2·A3 minutos serão necessários;
3ª andar: cada um dos A1 e A2 funcionários gastarão, respectivamente, 4 e 2 minutos. Assim, um total de 4·A1 + 2·A2 minutos serão necessários;
A resposta será o menor tempo necessário das três opções citadas acima.
Um exemplo de implementação segue abaixo:
H - Event
Resolva este problema: URI
O problema em si não tem segredo, basta multiplicar X por M, no entanto, devemos observar que tal multiplicação precisa ser salva em um tipo de dado que suporte valores superiores a 232-1 ☺.
Um exemplo de implementação segue abaixo:
I - Tribol
Resolva este problema: URI
Olhando para as regras do jogo podemos montar uma matriz M para armazenar as pontuações possíveis. Formalmente, seja uma matriz M[ X ][ Y ] = w de forma que X, Y ∈ {'R', 'G', 'B'}, X ≠ Y e w ∈ {1, 2}. Por exemplo, M[ 'R' ][ 'G' ] = 2, uma vez que o time 'R' marca um gol no time 'G' e como está a esquerda do seu adversário a pontuação será o dobro. Mapeado as pontuações, basta computar os saldos de gols dos times e imprimir uma das possíveis repostas (trempate, empate ou time com o maior saldo de gols) seguindo os critérios estabelecidos no enunciado.
Um exemplo de implementação segue abaixo:
J - Arrumando as Tarefas
Resolva este problema: URI
Você tem um único computador para realizar algumas tarefas. O lucro de uma tarefa é dado por v e a mesma deve ser terminada em até t horas a partir do início do seu turno. O problema então pede para que você minimize a quantidade de dinheiro desperdiçada. Ou seja, o ideal seria conseguir terminar todas as tarefas, formalmente seja S a soma de todos os lucros das tarefas e R a soma dos lucros de um subconjunto de tarefas que conseguistes executar, desta forma, o objetivo é minimizar S-R. Este problema pode ser resolvido de forma gulosa: parece uma boa ideia executar primeiramente as tarefas que dão o maior lucro possível. Se duas tarefas dão o mesmo lucro o melhor é executar a que termina primeiro. Portanto, basta ordenar as tarefas pelo critério do maior lucro e no caso de empate ordene pelo critério da tarefa que termina primeiro. Para cada tarefa, começando com a que tenha o maior lucro, verifique o primeiro momento em que ela pode ser executada. Marque esse horário como utilizado para que outra tarefa não utilize esse horário e contabilize seu lucro, siga para a próxima tarefa. Repita o processo até que tenha verificado todas as tarefas.
Um exemplo de implementação segue abaixo:
K - Sub-prime
Resolva este problema: URI
Devo, não nego, pago quando puder! O exercício pede para verificar se os bancos irão conseguir pagar suas dívidas utilizando apenas as suas reservas monetárias e seus créditos. Para resolver este problema basta computar o saldo de cada banco, se um banco X deve um valor z para um outro banco Y, então saldo[ X ] -= z e , por conseguinte, saldo[ Y ] += z uma vez que o banco Y irá receber tal quantia. Se no final das transações nenhum banco estiver com saldo negativo foi possível evitar a crise, caso contrário não foi possível.
Um exemplo de implementação segue abaixo:
L - Fazendo Pandorgas
Resolva este problema: URI
Um exemplo de implementação segue abaixo:
M - Média 2
Resolva este problema: URI
Um exemplo de implementação segue abaixo: