IV MARATONA DE PROGRAMAÇÃO INTERNA UERJ – 18/06/2011
Este caderno contém 11 páginas com a descrição de 10 problemas1 definidos
a seguir:
A - Liquidação!!!
B – Quadratura do retângulo II
C – Bolas chinesas II
D – Jogo da matriz
E – Aquecimento global
F – Travessia de ponte
G - Pista de esqui
H – Corra que a Copa vem aí...
I – Inversões
J - NegaFibonacci
1. Resolva os problemas conforme orientação anterior.
2. Tenha muita atenção e calma.
Boa sorte.
1
Problema A
Liquidação!!!
Josefina não perde uma liquidação na cidade. Ela adora comprar, mas é do tipo de
consumidor que pesquisa antes da compra. Como estamos na estação das liquidações, ela
descobriu inúmeras ofertas para compras de mais de uma unidade de cada objeto. As
ofertas são assim: você leva p peças e só paga q. Por exemplo: você leva 10 camisas e só
paga 8 ou leva 7 e paga só 5. Josefina está em dúvidas sobre qual oferta é mais vantajosa,
dentre tantas.
Você vai ajudá-la escrevendo um programa que indica a compra mais vantajosa, de uma
série de ofertas encontradas.
Entrada
Haverá vários casos de teste. A primeira linha da entrada é um inteiro t (1 ≤ t ≤ 1000)
que indica quantos serão os casos de teste. A seguir são descritos t testes. Cada teste é
descrito em várias linhas. A primeira indica o número n de ofertas de um dado objeto
(1 ≤ n ≤ 100). A seguir vêm n linhas, cada uma contendo dois inteiros, p e q, ambos entre 1
e 1000. O primeiro, p, indica quantas peças o cliente leva e o segundo indica quantas peças,
q, ele paga.
Saída
Para cada caso de teste imprima os valores de p e q que correspondem à oferta mais
vantajosa encontrada (aquela com o menor preço médio). Só haverá uma resposta certa.
Exemplo de entrada
2
3
10 7
20 15
30 20
2
20 7
10 3
Saída para o exemplo de entrada
30 20
10 3
2
Problema B
Quadratura do Retângulo II
Certos retângulos a x b, onde b é o lado maior, podem ser transformados em quadrados
segundo a construção ilustrada nas figuras. São obtidas três peças, 1, 2 e 3, por corte.
Justapondo as peças, obtem-se o quadrado procurado. Os passos são os seguintes:
a) marca-se a linha média, GH, relativa ao lado maior, de tamanho b.
b) marca-se o quadrado AFED, (lado AD = a, o menor) obtendo a linha EF.
c) obtem-se O, tal que HO = HB. Em seguida marca-se a linha BI, passando por O.
Você pode observar que AO é o lado do quadrado procurado, pois AO = BI = ab
d) cortam-se as figuras segundo as linhas BI e AO.
e) as imagens inferiores mostram a montagem do quadrado final.
Neste problema, dado um retângulo, você vai determinar as áreas das Figuras 1, 2 e 3, caso
seja possível fazer a quadratura.
Entrada
A primeira linha da entrada é um inteiro t (1 ≤ t ≤ 10000) que indica quantos serão os
casos de teste. Cada teste consiste de uma linha com 2 inteiros,
a, b (1 ≤ a, b ≤
1000), as dimensões do retângulo.
Saída
Para cada caso de teste imprima três números (com precisão de 2 casas decimais), indicando as áreas das Figuras 1, 2 e 3. Caso não seja possível fazer a construção, escrever -1.
Exemplo de entrada
3
15 10
10 20
10 30
Saída para o xemplo de entrada
53.03 61.61 35.36
100.00 50.00 50.00
-1
3
Problema C
Bolas chinesas II
Ano passado, numa viagem à China, Joaquim comprou duas lindas bolas de vidro que são
antistress. Ele teve dificuldade em acomodar essas bolas numa caixa em forma de
paralelepípedo. Neste ano ele voltou à China, comprou duas bolas e quer colocá-las em uma
caixa em forma de cubo. Ele quer saber qual o menor tamanho de caixa onde cabem as duas
bolas. Ou seja, ele conhece os raios das bolas e quer saber o lado do menor cubo onde
caibam as bolas.
Você vai ajudá-lo, escrevendo um programa para indicar o tamanho do lado dessa menor
caixa cúbica.
Entrada
Haverá vários casos de teste. A primeira linha da entrada é um inteiro t (1 ≤ t ≤ 1000)
que indica quantos serão os casos de teste. A seguir são descritos t testes. Cada teste
consiste de dois inteiros r1, r2, entre 1 e 1000, que são os raios das duas bolas.
Saída
Para cada teste você deve imprimir o tamanho do lado da caixa cúbica procurada,
arredondado para duas casas decimais.
Exemplo de Entrada
3
20 5
6 20
20 20
Saída para o exemplo de entrada
40.00
41.01
63.09
4
Problema D
Jogo da matriz
Sua turma está tendo aulas de Teoria dos Jogos e o professor quer exemplificar o princípio
de MaxMin. Então idealizou o seguinte jogo. É apresentada uma matriz quadrada n x n de
inteiros e os alunos escolhem um número p, entre 1 e n. O professor, então, tem liberdade
de escolher qualquer número da linha p ou da coluna p como a nota da turma. Mas ele, de
propósito, vai escolher o menor número possível. Por exemplo, dada a matriz:
2
10
10
10
9
6
4
10
6
3
7
9
10
8
3
8
6
10
7
6
9
10
3
6
6
se os alunos escolherem o número 1, o professor selecionaria a nota 2 (menor valor da linha
ou coluna 1); se escolherem 2, o professor seleciona a nota 3 (menor valor da coluna 2); se
escolherem 3, o professor seleciona 3 (menor valor da linha ou coluna 3); se escolherem 4,
o professor seleciona 6 (menor valor da linha ou coluna 4); finalmente, se escolherem 5, o
professor seleciona 3 (menor valor da linha ou coluna 5). Portanto, a melhor escolha para os
alunos é 4, obtendo a nota 6.
Você vai ajudar a turma, fazendo um programa que indica o número a ser escolhido pela
turma, para ter a maior nota possível escolhida pelo professor.
ENTRADA
A primeira linha contém um inteiro, “t”, que corresponde ao número total de casos. Cada
caso é descrito em várias linhas. A primeira delas é o número n, a dimensão da matriz
(1 ≤ n ≤ 1000). A seguir, vêm n linhas, cada linha contendo n inteiros, entre 0 e 100, os
elementos de cada linha da matriz.
SAÍDA
Para cada caso você deve imprimir a melhor nota possível que os alunos poderão receber,
escolhendo o número adequado.
EXEMPLO DE ENTRADA
2
5
26789
10 4 9 6 10
10 10 10 10 3
10 6 8 7 6
93366
3
70 100 100
100 90 100
100 100 80
EXEMPLO DE SAÍDA
6
90
5
Problema E
Aquecimento Global
Que dia quente! Tudo o que eu precisava era um copo d’água bem gelada! Peguei um copo
vazio, pus um cubo de gelo... Quarenta graus à sombra! Só pode ser culpa do aquecimento
global! Distraí-me pensando nisso e, quando, percebi parte do gelo já havia derretido. Havia
água suficiente para fazê-lo flutuar, ainda que minimamente. Quanto será que sobrou de
gelo, sabendo que o derretimento foi uniforme?
ENTRADA
A primeira linha contém um inteiro, “t”, que corresponde ao número total de casos. As “t”
linhas seguintes apresentam dois números inteiros, A e R, que representam
respectivamente a aresta inicial do cubo de gelo e o raio do copo, ambos menores que 1000.
Os números estão separados por um espaço simples. Considerar que o copo é perfeitamente
cilíndrico, bastante alto e que o gelo cabe completamente nele.
SAÍDA
Para cada caso informar o volume final do cubo de gelo com três casas decimais,
arredondando para o decimal mais próximo.
EXEMPLO DE ENTRADA
1
10 8
EXEMPLO DE SAÍDA
123.030
COMENTÁRIOS:
Princípio de Arquimedes (http://pt.wikipedia.org/wiki/Empuxo)
“Todo corpo mergulhado num fluido em repouso sofre, por parte do fluido, uma força
vertical para cima, cuja intensidade é igual ao peso do fluido deslocado pelo corpo.”
As figuras abaixo mostram de modo esquemático o derretimento do gelo e o surgimento do
nível de água. A situação descrita no problema corresponde à terceira figura.
Copo
Gelo
Situação inicial
Copo
Gelo
Derretimento inicial
Copo
Gelo
Flutuação mínima
Copo
Gelo
Derretimento
posterior
6
Problema F
Travessia de ponte
Uma importante ponte está semi-interditada por problemas de corrosão. Agora somente um
número limitado q de carros pode atravessar de cada vez. Então formam-se comboios de
até q veículos para atravessar juntos. Há carros de todos os tipos e cada um leva um tempo
diferente na travessia, de forma que o tempo de travessia de um grupo é aquele do carro
mais lento. Estamos pensando no menor tempo possível de travessia, considerando toda a
fila. Por exemplo se a fila tiver 5 carros com tempos de travessia 6, 20, 30, 15 e 5, é
melhor o primeiro carro atravessar sozinho, gastando 6 unidades de tempo, depois o grupo
dos três seguintes, gastando 30 e, por fim, o último carro, gastando 5, o que dá um tempo
total de 41. Você é o responsável para organizar os grupos, de forma a minimizar o tempo
total da travessia. Escreva um programa para ajudar nessa tarefa.
ENTRADA
A primeira linha contém um inteiro, “t”, que corresponde ao número total de casos. Cada
caso é descrito em uma linha com vários inteiros. Os dois primeiros, n e q (1 ≤ n, q ≤ 1000),
indicam o número de carros na fila e o número de carros que podem atravessar
simultaneamente. A seguir, na mesma linha, vêm n inteiros entre 1 e 1000, indicando o
tempo de travessia de cada carro, na mesma ordem da fila.
SAÍDA
Para cada caso você deve imprimir o tempo total mínimo possível para a travesia dos n
carros que estão na fila.
EXEMPLO DE ENTRADA
2
6 2 10 5 5 20 20 5
5 3 6 20 30 15 5
EXEMPLO DE SAÍDA
40
41
7
Problema G
Pista de esqui
Sandro está se preparando para ir esquiar no fim do ano na Argentina e está estudando as
melhores pistas de esqui. Ele gosta de fazer uma descida demorada da montanha. Por isso,
conseguiu o mapa das alturas do terreno e quer escolher um trajeto que permita a descida
mais longa possível, pois há teleférico para levar a qualquer parte da pista. As alturas do
terreno são representadas em uma matriz n x n. Sandro percebeu que pode escolher o
trajeto procurando números decrescentes vizinhos de cada posição. Os vizinhos de um
ponto estão acima, abaixo, à esquerda ou à direita na matriz. Por exemplo, na matriz
abaixo, o maior trajeto encontrado foi 11-9-4-2-1:
1
5
4
1
2
3
2
3
4
9
11
7
3
8
9
5
Você vai ajudar o Sandro, fazendo um programa que, dada a matriz de alturas, determina o
tamanho da maior sequência decrescente de números vizinhos, que indica a melhor
trajetória para Sandro fazer.
ENTRADA
Haverá
vários
casos
de
teste.
A
primeira
linha
da
entrada
é
um
inteiro
t (1 ≤ t ≤ 1000) que indica quantos serão os casos de teste. Cada caso de teste é
descrito em várias linhas. A primeira é o tamanho n da matriz quadrada, (1 ≤ n ≤ 100). A
seguir vêm n linhas, contendo os valores das alturas de cada linha da matriz, estando as
alturas entre 0 e 1000.
SAÍDA
Para cada caso escrever o tamanho da maior trajetória que Sandro pode fazer.
EXEMPLO DE ENTRADA
2
4
1243
5398
4 2 11 9
1375
3
123
894
765
EXEMPLO DE SAÍDA
5
9
8
Problema H
Corra que a Copa vem aí...
A cidade se prepara para a Copa e há obras por todo lado. O trânsito está caótico em
algumas ruas, porque muitas vias muito importantes foram fechadas para obras e alguns
pontos da cidade ficaram inalcançáveis a partir de outros. O prefeito quer reparar esses
erros com urgência e reabrir o trânsito em algum lugar, mas também não quer mudar muito
as obras. Dado o mapa de trânsito da cidade, representado em um digrafo, onde os vértices
são os cruzamentos de trânsito e as arestas os trechos de rua, com determinada direção
de tráfego, o prefeito quer saber se há como tornar mão dupla algum trecho hoje em mão
única, para que todos os locais da cidade sejam acessíveis a partir de qualquer outro ponto.
Por exemplo, se fizer isso no trecho entre os pontos 5 e 6 da figura abaixo, todos os
pontos passam a ser acessíveis a partir do ponto 6.
4
2
6
1
3
5
Entrada
A entrada consistirá de vários casos de testes indicados na primeira linha pelo valor inteiro
t. Cada teste começa com uma linha contendo 2 números: N, M. N (2 ≤ N ≤ 100) representa
o número de cruzamentos distintos. M (0 ≤ M ≤ 1000) indica o número de trechos de ruas.
A seguir existem M linhas contendo, cada uma delas dois números A e B, indicando que
existe um trecho de rua entre A e B, com o trânsito fluindo de A para B. Os trechos de rua
são numerados de 1 a N.
Saída
Para cada caso de teste você deve imprimir uma linha de saída, cujo conteúdo deve ser: 0,
se não existir o problema mencionado, -1, se o problema não pode ser resolvido ou 1 se o
problema pode ser resolvido, ou seja, é possível tornar um único trecho de rua, hoje em
mão única, para mão dupla, de forma que qualquer ponto da cidade seja alcançável a partir
de qualquer outro.
2 1
Exemplo de Entrada
1 2
3
2 2
6 7
1 2
5 4
2 1
31
2
4
5
5
1
3
5
2
3
6
2
2
Exemplo de Saída
1
-1
0
9
Problema I
Inversões
Júlio começou estudar Matemática Discreta e está pensando em inventar um algoritmo
mirabolante para ordenar dados guardados em um vetor. Inicialmente ele está trabalhando
com vetores de n elementos cujos elementos são os números de 1 a n (o vetor contém uma
permutação dos n primeiros inteiros positivos). Por exemplo, um vetor de 10 elementos de
interesse do Júlio poderia ser o seguinte:
1
2
3
4
5
6
7
8
9
10
4
5
6
8
2
3
10
7
1
9
Júlio quer contar quantos pares de elementos "conjugados" existem. Um par de elementos
(a, b) é conjugado no vetor V, se (a ≠ b), V[a] = b e V[b] = a. No vetor V mostrado temos
dois pares conjugados: o par (2, 5), pois V[2] = 5 e V[5] = 2 e o par (3, 6), pois V[3] = 6 e
V[6] = 3.
Você vai fazer um programa para contar o número de pares conjugados de um vetor de n
elementos, que contém uma permutação dos números 1 a n.
ENTRADA
Haverá
vários
casos
de
teste.
A
primeira
linha
da
entrada
é
um
inteiro
t (1 ≤ t ≤ 10000) que indica quantos serão os casos de teste. Cada caso de teste vem em
uma linha com vários inteiros. O primeiro número da linha, n (1 ≤ n ≤ 10000) indica o tamanho
do vetor. A seguir, na mesma linha, vêm n inteiros guardados, respectivamente nas posições
1 a n do vetor.
SAÍDA
Para cada caso escrever o número de pares conjugados do vetor.
EXEMPLO DE ENTRADA
2
10 4 5 6 8 2 3 10 7 1 9
6123456
EXEMPLO DE SAÍDA
2
0
10
Problema J
NegaFibonacci
Quem já participou de alguma Maratona de Programação provavelmente já se deparou com
a famosa série de Fibonacci. Apenas para recordar, a definição clássica desta série é:
F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2, para n > 1.
Mas vejamos o que acontece se aplicarmos a recursão para calcular os dois primeiros
termos da série:
F1 = F0 + F-1
F0 = F-1 + F-2
F-1? F-2? Conheçam os NegaFibonacci. Rearranjando as expressões acima, pode-se deduzir a
recursão para os demais termos dessa série:
F-1 = F1 – F0 = 1
F-2 = F0 – F-1 = -1
Fn = Fn+2 – Fn+1 , para n < -2
Portanto os primeiros termos desta série são: 1, -1, 2, -3, 5, -8, 13, -21 34 -55 89...
Uma propriedade interessante é que é possível representar, de forma única, qualquer
inteiro como uma soma de NegaFibonacci, usando um algoritmo guloso. Para garantir esta
unicidade da soma, não é permitido utilizar dois NegaFibonacci consecutivos. Por exemplo:
a) 18 = 5 + 13 = F-5 + F-7
b) -27 = 2 + (-8) + (-21) = F-3 + F-6 + F-8
Podemos transformar estas somas em notação binária, indicando por “1” os NegaFibonacci
presentes e por “0” os demais. Sendo assim os dois casos acima seriam representados por:
a) 18 = 1010000
b) -27 = 10100100
ENTRADA
Haverá
vários
casos
de
teste.
A
primeira
linha
da
entrada
é
um
inteiro
t (1 ≤ t ≤ 10000) que indica quantos serão os casos de teste. Cada caso é composto por
um número inteiro n (|n| ≤ 109) em uma linha.
SAÍDA
Para cada caso escrever a notação binária que representa a soma de NegaFibonacci cujo
resultado é igual a n. Notar que 0 vai ser representado como 0.
-27
EXEMPLO DE ENTRADA
EXEMPLO DE SAÍDA
3
0
0
1010000
18
10100100
11
12