Maratona de Programação Beneficente
Departamento de Informática – 1 de julho de 2006
ProblemaA – É Lagoaou não é?
Arquivofonte: lagoa.pas lagoa.c lagoa.cpp lagoa.java
Autor:Pablo Durans,alunodo 3o. Períodode Computação
Um aluno de geografia, interessadoem catalogartodas as lagoasencontradasem um arquipélago,utilizou uma matriz que
representava fotos de satélite de um arquipélago com milhares de lagoas e lagunas. Essa matriz lhe dizia se uma
determinada coordenadada foto era coberta por “água” ou por “terra”. Pra determinar se uma área é ou não é lagoa, ele
definiu que basta existirem coordenadas “água” adjacentes cercada de coordenadas “terra” por todos os lados.
Assim,ajude-o nessaimportantemissão!Obs: A águaescorreem sentidodiagonal.
Entrada
A entradase divide em duas partes: na primeira parte, serão lidos dois inteiros m e n que representama matriz m x n que
será preenchida por 'A's ou 'T's (A de água e T de terra). Na segunda parte será lido um inteiro k, que será o número de
casos de teste. Cadacaso de teste apresentadois valores inteiros x,y (0<x≤m,0<y≤n),que representaa coordenadaa ser
analisada.O programaterminacomos valoresde m e n iguais a 0.
Saída
Para cadacaso de teste, deve ser dada comosaídaumalinha contendo“Naoe Lagoa”para o caso da coordenadanão ser
umalagoaou “E Lagoa”caso contrário.
Exemplode entrada
7 9
TTTTATTTT
Respectivasaída
Nao e Lagoa
Nao e Lagoa
E Lagoa
TTTTTAATT
ATTTAAATT
AATTTTTTT
ATTTTAAAT
TTTTTAAAT
TTTTTTTTT
3
2 6
1
Maratona de Programação Beneficente
Departamento de Informática – 1 de julho de 2006
ProblemaB – O Dilemada Arqueologista
Arquivofonte: dilema.pas dilema.c dilema.cpp dilema.java
Adaptação:DiogoDuailibeda Silva, alunodo 5o. períodode Computação
Uma arqueologista, procurando uma prova da presença de civilizações antigas, descobriu uma muralha parcialmente
destruída contendo cadeias de números muito estranhas. A parte esquerda desta linha de dígitos estava praticamente
intacta, mas para infelicidade da arqueóloga, a parte direita estava muito danificada devido a ação da erosão. Entretanto,
ela percebeu que todos os números com os dígitos intactos eram potências de 2 e assim ela chegou a uma hipótese: de
que todosos númeroserampotênciasde dois. Para reforçar sua crença, ela selecionouuma lista de númerosem que,
aparentemente, o número dos dígitos legíveis é estritamente menor que o dos dígitos danificados. Então ela pede para
você encontrar a menor potência de dois, se ela existir, em que os primeiros dígitos coincidam com aqueles da lista. Ou
seja, escreva um programaque, dado um inteiro, ele determine o menor expoente E em que os primeiros dígitos de 2^E
coincidamcomo inteiro. (Lembre-se que maisda metadedos dígitosestãoperdidos).
Entrada
A entrada consiste de várias linhas, uma linha por caso. Cada linha contém um número inteiro simples. Se existir uma
potênciade 2 que correspondeao número,ele é menorou igual a 2^31. A entradaterminacomumalinha contendo0.
Saída
Para cada linha da entrada, deve ser exibido o menor valor E para que os primeiros dígitos de 2^E sejam precisamenteos
dígitos da entrada.Se não existir a potência, devehaver na saída“Naoexiste potenciade 2”.
Exemplode entrada
1
2
10
0
Respectivasaída
7
8
20
2
Maratona de Programação Beneficente
Departamento de Informática – 1 de julho de 2006
ProblemaC – Despesasdo Hotel
Arquivofonte: hotel.pas hotel.c hotel.cpp hotel.java
Autor:Daniel Lima, alunodo 7o. Períodode Computação
O dono de um hotel está tendo problemas financeiros, principalmente as contas de energia, que estão altíssimas. Para
resolver esse problema,ele contratouum economista, que lhe deu a brilhante solução: nos dias em que houvessea maior
quantidade de quartos ocupados, ele poderia fazer um sistema de racionamento de energia. Mas para isso ele precisa
determinarem quais períodosdo ano ele terá maior númerode hóspedes,de acordocomo númerode reservas.Ajude-o!
Entrada
São dados vários conjuntosde entradas. Cadaconjunto de entradasé compostopor duas partes: na primeira linha é dado
um valor k, indicando o número de hospedagens no período. Para cada uma das k-linhas seguintes é dado o dia de
entradae o dia de saída (os dias são numeradosde 1 a 365, a partir de primeiro de janeiro). O hotel fecha no dia 365 (31
de dezembro), não permitindo, portanto, hospedagenspara o Reveillon (desconsidereanos bissextos). Um conjuntocom 0
hospedagensindica o fim da entrada.
Saída
Cada conjunto da entrada deve ter como saída dois valores: a quantidade máxima de hóspedes e os dias em que houve
essa máxima.As respostasdevemconterumalinhaem brancoseparando-as.
Exemplode entrada
3
3 26
23 46
18 22
2
1 20
18 24
0
Respectivasaída
2
18 19 20 21 22 23 24 25 26
2
18 19 20
3
Maratona de Programação Beneficente
Departamento de Informática – 1 de julho de 2006
ProblemaD – Degraus
Arquivofonte: degraus.pas degraus.c degraus.cpp degraus.java
Autora:VanessaLeite, alunado 3o. períodode Computação
Duas amigas bastante curiosas achamque para tudo existe uma explicação lógica e matemática. Certa vez, foram juntas
ao shopping e observaram durante muito tempo a escada rolante. Ficaram curiosas em saber quantos degraus ficariam
visíveis por vez. Para isso, elas começarama subir a escadajuntas, sendoque uma subia de um degraupor vez e a outra
ia de dois em dois. Dada a quantidade de degraus contada por uma e por outra, você é capaz de criar uma solução que
informequantosdegrausestãovisíveis?Nãoesqueçamque a escadacontinuaem movimento.
Entrada
A entrada consistemem dois valores p e q , sendo p<q<100que representamo numero de degraus da menina que subiu
um degrau por vez e o da menina que subiu dois de cada vez, respectivamente. A entrada termina com o valor de p e q
igual a 0.
Saída
Para cadalinha da entrada,deveráser exibidacomosaídaquantosdegrausvisíveis possui a escadarolante.
Exemplode entrada
21 28
24 32
0 0
Respectivasaída
42
48
4
Maratona de Programação Beneficente
Departamento de Informática – 1 de julho de 2006
ProblemaE – NúmerosFigurativos
Arquivofonte: figurativos.pas figurativos.c figurativos.cpp figurativos.java
Autor:EduardoAraújo, alunodo 3o. Períodode Computação
Na escola de Pitágoras no século VI a.C., onde se dizia que “Tudo é Número”, iniciou-se o estudo de números especiais,
chamados de figurativos, que são os números que podem ser representados geometricamente como uma disposição de
pontosem configuraçõespoligonais. Sendoformadospelasdisposiçõesde pontos, podese notar aindaque 1 pontoé base
para todos os polígonos. Assimos númerostriangulares, caso particular dos númerosfigurativospodemser representados
geometricamente como disposição de pontos em forma de triângulos. Tomando os números triangulares ainda como
exemplopodemosdefinir sua seqüênciaassim:
T(3) = 1, 3, 6, 10, 15, 21, ...
T(3, 1) = 1
T(3, 2) = 3 T(3, 3) = 6
T(3, 4) = 10
T(3, 5) = 15
T(3, 6) = 21
Sua tarefa é informara quantidadeQ de pontosno n-ésimotermoda seqüênciapara um polígonode k lados, em
que Q é sempre0 < Q < 2³². E aindak > 2 e n > 0.
Entrada
A entrada consiste de um numero k que representa o tipo de polígono, ou seja, a quantidade lados, e um número n que
representao n-ésimotermoda seqüência.A entradaterminaquandoos valoresde k e n são 0
Saída
A saída deve imprimir uma linha que informa qual o tipo de polígono e uma outra que informa a quantidade pontos no nésimotermoda seqüência.Duassaídasconsecutivassão separadaspor umalinha em branco
Exemplode entrada
3
4
7
0
4
6
15
0
Respectivasaída
10
36
540
5
Maratona de Programação Beneficente
Departamento de Informática – 1 de julho de 2006
ProblemaF – Estrelasem Slogo
Arquivofonte: estrelas.pas estrelas.c estrelas.cpp estrelas.java
Autor:PabloDurans,alunodo 3o. períodode Computação
Slogo é uma linguagem de programação para crianças que consiste em uma tartaruga que obedece ordens de ir para
frente, ou para trás ou virar a esquerda ou virar a direita. Além disso, assim como a maioria (senão em todas as
linguagens),ela tem comandoscondicionaise de repetições.Por ondea tartarugapassaela deixa um rastro que, conforme
a capacidade daquele que a domina, é capaz de fazer desenhos. Uma certa criança, tentando fazer um desenho,
descobriuque existe uma maneirabemsimplesde fazer estrelas de 5 pontas. O comandoque ela digitavaera: “repita 5 [pf
100 pe 144]”. Onde “repita 5” quer dizer que a tartaruga vai repetir o bloco que comando a seguir 5 vezes, “pf 100” que
dizer que a tartarugairá avançar 100 unidadesde comprimentoe “pe 144” diz que a tartarugairá virar a esquerdacom um
ângulo de 144º. Como criança inteligente que ela era, ela descobriu que era possível fazer estrelas de mais de cinco
pontas e com a mesmaformula “repita n[pf len pe ang] ”, onde n seria o númerode pontas na estrela, len seria o tamanho
da estrela e ang seria um ânguloque dificilmente umacriançapoderiacalcular. Entãoesse é seu trabalho.
Entrada
A entrada consiste em um numero n (0<n<1000), que é o numero de pontas que uma estrela têm. A entrada termina
quandoo valoresde n for igual a zero.
Saída
A saída deve ser um ângulo x (0<x<180) com três casas de precisão que é menor ângulo que a tartaruga deve virar a
esquerda ou, caso a estrela seja impossível de ser feita com uma só linha, uma mensagem “Estrela impossível de ser
feita”.
Exemplode entrada
2
6
30
0
Respectivasaída
Estrela impossível de se fazer
Estrela impossível de se fazer
84.000
6