Programando melhor: Exercícios 1 (Parte I)
Agora é a hora da diversão!!!
Bem pessoal, como prometido, chegou hoje a primeira bateria de exercícios do nosso curso “Programando melhor”, para você que deseja se tornar um melhor programador/competidor. Além disso, venho compartilhar com vocês a enorme vantagem nesse tipo de competição de quem domina bem a matemática (em competições também), pois hoje tive mais uma aula do Programa de Iniciação Científica OBMEP 2007 e fiquei ainda mais amando essa matéria (o que me faz gostar cada vez mais de programação pesada!). Mas vamos pôr a mão na massa!
Problema 1: The 3n+1 Problem (O problema do 3n+1)
UVa ID (código no site da Universidad de Valadollid): 100 ; Nível: Fácil
Considere o seguinte algoritmo para gerar uma sequência de números. Comece com um inteiro n. Se n é par, divida por 2. Se n é ímpar, multipique por 3 e some 1. Repita esse processo com o novo valor de n, terminando quando n = 1. Por exemplo, a seguinte sequência de números será gerada a partir de n = 22.
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
É conjecturado (mas ainda não provado) que esse algoritmo terminará em n=1 para qualquer inteiro n. Ainda, a conjectura assegura para todos os inteiros até 1 milhão.
Para uma entrada n, o tamanho do ciclo de n é o número de números gerados, incluindo o 1. No exemplo acima, o tamanho do ciclo de 22 é 16. Dados qualquer dois números i e j, você deve determinar o maior tamanho do ciclo dentre todos os inteirosdf entre i e j, incluindo ambos os extremos.
Entrada
A entrada consistirá numa série de pares de inteiros i e j, um par de inteiros por linha. Todos os inteiros serão menores do que 1 milhão e maiores que 0.
Saída
Para cada par de inteiros i e j, coloque i e j na mesma ordem que eles apareceram na entrada e então o maior tamanho de ciclo para todos os inteiros entre e incluindo i e j. Esses três números devem estar separados por um espaço, com todos os três números em uma linha e com uma linha de saída para cada linha de entrada.
Exemplo de entrada/saída
Entrada -> 1 10 ; Saída -> 1 10 20
Entrada -> 100 200 ; Saída -> 100 200 125
Entrada -> 201 210; Saída ->201 210 89
Entrada -> 900 1000 ; Saída -> 900 1000 174
Problema 2: The Trip (A Viagem)
UVa ID: 10137 ; Nível: Fácil
Um grupo de estudantes são membros de um clube que viaja anualmente para diferente locais. Os destinos deles no passado incluem Indianapolis, Phoenix, Nashville, Philadelphia, San Jose e Atlanta. Essa primavera eles estão planejando uma viagem para Eindhoven.
O grupo concorda a princípio compartilhar as despesas igualmente, mas não é prático compartilhar cada despesa no momento em que ela ocorre. Então indivíduos no grupo pagam por certas coisas, como refeições, hotéis, táxi e passagens aéreas. Depois da viagem, as despesas de cada estudante são contadas e o dinheiro é trocado para que o custo líquido para cada um seja o mesmo, para cada centavo. No passado, esse dinheiro trocado foi tedioso e consumiu muito tempo. Seu trabalho é computar, de uma lista de despesas, a quantia mínima de dinheiro que deve trocar de mãos em virtude de igualar (com diferença máxima de 1 centavo) todos os custos dos estudantes.
Entrada
A entrada padrão irá conter a informação para diversas viagens. Cada viagem consiste de uma linha contendo um inteiro positivo n, o qual representa o número de estudantes na viagem. Isso é seguido por n linhas de entrada, cada uma contendo a quantia gasta pelo estudante em dólares e centavos. Não há mais do que 100 estudantes e os estudantes não irão gastar mais do que $10.000,00 cada. Uma linha contendo 0 segue a informação da última viagem.
Saída
Para cada viagem, forneça uma linha de saída informando a quantia total de dinheiro, em dólares e centavos, que deve ser trocada para igualar os custos dos estudantes.
Exemplo de entrada
3
10.00
20.00
30.00
4
15.00
15.01
3.00
3.01
Exemplo de saída (correspondente à entrada acima)
$10.00
$11.99
Bem pessoal, agora mesmo irei colocar a Parte II desses exercícios, com mais um do nível Fácil e outro do nível Médio, ok? Fiquem à vontade para perguntar e, com certeza, dar dicas para a resolução dos problemas. Soluções completas dos problemas não serão aceitas em comentários, pois (após discutir com algumas pessoas) seria algo que tiraria a “graça” dos problemas propostos, porém qualquer dica a respeito é bem-vinda! Além disso, eu mesmo irei postar as minhas dicas quando eu pegar esses problemas pra valer (amanhã), blz?
Posts interessantes:
- Programando melhor: Exercícios 1 (Parte II)
- Programando melhor: Aula 1 – Começando
- Cursos grátis na Internet – MIT
- Top Coder Marathon Matches
- Olimpíadas do Conhecimento
Helton de Melo Duarte
“A sabedoria é a coisa principal: adquire, pois, a sabedoria; sim, com tudo o que possuis adquire o entendimento. Estima-a e ela te exaltará; se a abraçares, ela te honrará. Ela dará à tua cabeça uma grinalda de graça; e uma coroa de glória te entregará.” (Provérbios 4.7-9)
