Programando melhor: Exercícios 1 (Parte II)
Mais diversão para vocês!
Problema 3: LCD Display
UVa ID: 706 ; Nível: Fácil
Um amigo seu acabou de comprar um novo computador. Antes disso, a máquina mais poderosa que ele havia usado foi uma calculadora de bolso. Ele está um pouco desapontado porque ele gostava do display LCD da sua calculadora mais do que da tela do seu novo computador! Para fazê-lo feliz, escreva um programa que imprima números no estilo de um display LCD.
Entrada
O arquivo de entrada contém diversas linhas, uma para cada número a ser disposto na tela. Cada linha contém inteiros s e n, onde n é o número a ser disposto (0 <= n <= 99.999.999) e s é o tamanho que ele irá aparecer (1 <= s <= 10). A entrada será terminada por uma linha contendo dois zeros, que não deve ser processada.
Saída
Escreva os números especificados no arquivo de entrada em estilo display LCD usando s sinais “-” para os segmentos horizontais e s sinais “|” para os verticais. Cada dígito ocupa exatamente s + 2 colunas e 2s + 3 linhas. Esteja certo de preencher todos os espaços brancos ocupados pelos dígitos com “espaços”, incluindo o último dígito. Deve haver exatamente uma coluna de “espaços” entre dois dígitos.
Coloque uma linha de “espaço” após cada número. Você encontrará um exemplo de cada dígito no Exemplo de saída abaixo.
Exemplo de entrada
2 12345
3 67890
Exemplo de saída
Problema 4: Interpreter (Interpretador)
UVa ID: 10033 ; Nível: Médio
Um certo computador tem dez registradores e 1000 palavras de RAM. Cada registrador ou local na RAM armazena um inteiro de três dígitos entre 0 (zero) e 999. Intruções são codificadas como inteiros de três dígitos e armazenadas na RAM. Os códigos são os seguintes:
100 | manter
2dn | armazena no registrador d o valor n (entre 0 e 9)
3dn | adiciona n ao valor armazenado em d
4dn | multiplica por n o valor armazenado em d
5ds | armazena em d o mesmo valor armazenado em s
6ds | adiciona o valor armazenado em s ao armazenado em d
7ds | multiplica o valor armazenado em d pelo de s
8da | armazena em d o valor de RAM que tiver seu endereço armazenado no registrador a
9sa | armazena na RAM, cujo endereço esteja em a, o valor armazenado no registrador s
0ds | vai para o local armazenado no registrador d a menos que o registrador s cotenha 0 (zero)
Todos os registradores inicialmente contém 000 (zero). O conteúdo inicial da RAM é lido de uma entrada padrão. A primeira instrução a ser executada é no endereço RAM zero. Todos os resultados são reduzidos módulo 1000.
Entrada
A entrada começa com um único inteiro positivo na linha, indicando o número de casos, cada um descrito abaixo. É seguido por uma linha em branco e haverá uma linha em branco entre cada duas entradas consecutivas.
Cada caso de entrada consiste num inteiro sem sinal de três dígitos, representando os conteúdos de locais consecutivos na RAM, começando pelo zero. Locais de RAM não especificados são inicializados com 000 (zero).
Saída
A saída de cada caso de teste é um único inteiro: o número de instruções executadas acima e incluindo a de “manter”. Você pode assumir que o programa faz o “manter”. Separe a saída de dois casos consecutivos por uma linha em branco.
Exemplo de entrada
1
299
492
495
399
492
495
399
283
279
689
078
100
000
000
000
Exemplo de saída
16
É isso aí pessoal, temos agora a segunda parte da primeira bateria de exercícios proposta como treinamento, ok? Os exeercícios de agora são um pouco mais difíceis (confesso que não entendi nem o que pede o problema 4 de primeira olhada xD ), contudo não desanimem, pois precisamos pegar pesado se queremos alguma coisa.
Posts interessantes:
- Programando melhor: Exercícios 1 (Parte I)
- Programando melhor: Aula 1 – Começando
- Cursos grátis na Internet – MIT
- Top Coder Marathon Matches
- Olimpíadas do Conhecimento
Novamente, qualquer dica para a solução de problemas é extremamente bem vinda e dúvidas serão, à medida do possível, respondidas. Deixe seu comentário falando o que achou dos problemas! E conte também seu caso de sucesso!
Helton de Melo Duarte
“A sabedoria exalta aos que a favorecem, honra aos que a amam, e empresta graça à aparência de uma pessoa, para que esta seja admirada e respeitada por aqueles que a conhecem.” Charles Fritsch
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)
