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)
fevereiro 14th, 2009 at 12:46
réee
massa helton, vo ficar passando aqui agora pra fazer esses exercicios
é legal começar com esses mais faceis que ae anima o cara… fiz o primeiro em pascal ja que eu ainda nao sei C direito, depois eu comparo minha resposta com a q vc postar
vou ver se eu faço o segundo depois
falou!
fevereiro 14th, 2009 at 16:02
[...] Programando melhor: Exercícios 1 (Parte I) [...]
fevereiro 14th, 2009 at 16:06
[...] Programando melhor: Exercícios 1 (Parte I) [...]
fevereiro 17th, 2009 at 9:39
[...] Programando melhor: Exercícios 1 (Parte I) [...]
fevereiro 20th, 2009 at 21:08
[...] Programando melhor: Exercícios 1 (Parte I) [...]
março 4th, 2009 at 11:26
/* CÓDIGO FINAL DO PROBLEMA 3N+1 (RECEBEU “ACCEPTED” NO UVA ONLINE JUDGE */
#include
int vetor[1000000]; /* Vetor que guarda o que já foi calculado */
int sequence (int n)
{
int qtd = 1; /* Contar o valor da sequência */
int num = n; /* Para alterar esse valor, jah q o n é necessário no fim */
/* Esse teste é para ver se jah foi calculado o valor solicitado */
if (vetor[n-1] != -1)
{
return (vetor[n-1]);
}
else /* Se ainda não calculou, então calcula */
{
while (num != 1)
{
if (num % 2) /* Se for ímpar entra no if */
{
num = 3*num + 1;
}
else
{
num = num/2;
}
qtd += 1;
}
/* Coloca o valor calculado no vetor, para da próx vez ñ precisar */
vetor[n-1] = qtd;
return (qtd);
}
}
int main()
{
int i, j; /* O par de inteiros que limitarão a sequência pesquisada */
int max; /* Tamanho máximo do ciclo entre i e j */
int count; /* Contador para o loop for */
int aux; /* Variável auxiliar para não precisar chamar a função
duas vezes */
int x, y; /* Auxiliares para ficar na ordem crescente */
/* Coloca -1 em todos os elementos do vetor, pois é um nº inválido */
for (count=0; count < 1000000; count++)
{
vetor[count] = -1;
}
/* Ler as variáveis de entrada */
/* O scanf retorna quantas variáveis foram lidas, por isso esse teste */
while (scanf (“%d %d”, &i, &j) == 2)
{
max = 0;
aux = 0;
/* Para deixar o for em ordem crescente */
if (i <= j)
{
x = i;
y = j;
}
else
{
x = j;
y = i;
}
for (count = x; count max)
{
max = aux;
}
}
/* Saída de dados */
printf (“%d %d %d\n”, i, j, max);
}
return (0);
}
março 4th, 2009 at 11:28
Olha pessoal, tah aih o primeiro problema feito por mim no UVa Online judge. Eu não iria colocar o código, pq tira a graça do problema, mas como foi o primeiro proposto aí eu coloquei pra vcs terem uma noção de como ler entrada e como colocar a saída e tal…
Valeu e boa sorte!
março 6th, 2009 at 14:19
Olá Seguinte outra dúvida.
Agora que vi seu código.
Seguinte, eu fiz, em C++ e utiliza container do tipo set isso é um problema ?
E no seu código não peguei a idéia ali. É que o seu main não chama em nenhum momento sua função sequence, e tem esse for [for (count = x; count max)] que não manjei.
Podes da uma luz para clariar as idéias.
Valeu
Diego
março 6th, 2009 at 15:20
Putz sem querer abusar mas é o seguinte,
Submeti o meu código no site UVa Online Judge. Blz.
Para saber se foi ou não aprovado é só clicar no menu esquerdo My Submissions e no lado esquerdo na coluna Verdict tem que ta alguma coisa diferente de Wrong answer.
Depois que envio o código não da para mudar, editar apagar esses lance ?
Valeu
Desculpa a enchessão.
Falows
março 7th, 2009 at 17:17
Opa!
Valeu Diego, pelas observações.
É pq quando fui colar o código aqui ele deve ter dado uns problemas. Não sei pq, quando coloco o for do jeito certo e posto o comentário ele dá erro e coloca exatamente como tá nesse antes…vou tentar ver e posto certo, ok?
Valeu por ver isso!
março 7th, 2009 at 17:24
Sobre o outro comentário, Diego, você poderá enviar novamente o código do problema, tentando novamente conseguir “Accepted” (não é somente ser diferente de “Wrong Answer”, pq o seu código ainda pode tá lento ou coisas do tipo…é necessário receber “Accepted”, ok?).
O que vc já enviou não há como mudar, contudo poderá enviar outro, devido a eles fazerem estatísticas de acerto/erro da sua conta.
Valeu.
Qualquer dúvida perguntem!
março 9th, 2009 at 15:40
[...] Leia mais >> [...]
março 27th, 2009 at 22:02
[...] colocados comentários com dicas para os problemas “The Trip”, em Exercícios 1 (Parte I) e “Jolly Jumpers”, na Aula 2, pois foram resolvidos por mim no site do UVa Online Judge [...]
março 27th, 2009 at 22:25
Bem pessoal,
Venho agora dar dicas sobre o outro problema dessa lista, o “The Trip”, ok? Nesse caso e nos próximos não irei colocar o código completo, serão apenas dicas para a resolução:
* Considere o valor dos gastos como o total de centavos, pois trabalhar com números “float” ou “double” é bem perigoso, são tipos que arredondam muito os valores (por exemplo, o valor 0 poderá ser na verdade 0.00000000003525 em um ponto flutuante, deu pra perceber os problemas?).
* Tendo uma variável inteira para a média, em centavos, dos participantes da viagem, além de outro inteiro para o resto, ou seja, a diferença máxima que poderá haver entre eles.
* Depois de armazenar o que foi gasto por cada um, faça um laço para todo o vetor de gastos e veja: se o resto == 0 e o gasto desse participante for maior do que a média, então aumente ao valor transferido a diferença gastos[i] – media; se o resto != 0 e gastos[i] – media > 1, então aumente em transferência o valor de gastos[i] – media – 1 (devido ao resto) e retire 1 dessa variável.
Pronto, só será preciso agora lembrar que seu valor de transferência é inteiro e ele pede para imprimir um real, todavia a ideia do programa está completa! =D
Boa sorte a todos!
OBS: Diversas dessas dicas foram dadas por Herbert de Mélo Duarte, Mestre em Engenharia da Computação pela UFRN.
maio 23rd, 2009 at 22:17
[...] colocados comentários com dicas para os problemas “The Trip”, em Exercícios 1 (Parte I) e “Jolly Jumpers”, na Aula 2, pois foram resolvidos por mim no site do UVa Online Judge [...]
agosto 21st, 2009 at 16:01
[...] Programando melhor: Exercícios 1 (Parte I) [...]