VIII MARATONA DE PROGRAMAÇÃO UERJ – 06/12/2014
Este caderno contém 12 páginas com a descrição de 11 problemas1 definidos
a seguir:
A - DNA
B – Pesagem
C – Vírus
D - Rede sob ataque!
E – Somando
F – Subtraindo
G – Quadratura do retângulo
H – Vetores
I – Burlando a Balança
J - Parênteses e mais parênteses.
K - Homem Primata
1. Resolva os problemas conforme orientação anterior.
2. Não usar nenhum recurso eletrônico extra (pen-drives, tablet, celular)
3. Não utilizar Internet.
4. Permitida a consulta a qualquer material escrito.
5. Tenha muita atenção e calma.
Boa sorte.
1
Autoria de Paulo Eustáquio Duarte Pinto e Fabiano de Souza Oliveira.
1
Problema A
DNA
A Biologia computacional trabalha com a representação do DNA em cadeias de genes e
estuda transformações genéticas que podem ter ocorrido, ao longo dos séculos, nessas
cadeias. Em alguns processamentos os genes são identificados com os números 1 a n e as
cadeias podem ter sofrido transformações que embaralharam esses genes. Dada uma
cadeia contendo n números você deve fazer um programa para indicar se os n genes iniciais,
numerados de 1 a n, estão presentes na cadeia.
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. A seguir são descritos t testes. Cada teste
consiste de duas linhas de entrada. Na primeira linha existe um inteiro n (1 ≤ n ≤ 100),
que indica o número de genes na cadeia. Na segunda linha existem n inteiros positivos
quaisquer indicando o número do gene na cadeia.
Saída
Para cada caso de teste imprima 'S' se a cadeia continua com os n genes iniciais ou 'N',
caso contrário.
Exemplo de entrada
2
10
10 8 6 4 2 1 3 5 7 9
10
10 8 6 4 2 1 3 5 77777 9
Saída para o exemplo de entrada
S
N
2
Problema B
Pesagem
As balanças de dois pratos ainda são encontradas em feiras, em laboratórios especiais e em
museus. Em um dos pratos coloca-se o objeto a ser pesado e, no outro os pesos até
equilibrar a balança. Somam-se os pesos e obtém-se o peso do objeto. Mas também podem
ser colocados alguns pesos junto com o objeto a ser pesado e, nesse caso, tem-se que
subtrair esses pesos da soma dos pesos do lado oposto. Por exemplo, um objeto de peso 15
pode ser pesado colocando-se do outro lado da balança os pesos 8, 4, 2, 1, pois
15 = 8+4+2+1. Mas também pode ser pesado colocando-se o peso 16 do lado oposto e o peso
1 junto com o objeto pois 15 = 16-1.
Neste problema, os pesos são todos as potências de 2 e somente há um peso de cada valor.
Você deve descobrir o esquema que pesa dado objeto de peso inteiro, usando o menor
número de pesos do tipo descrito.
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 contendo um inteiro n (1 ≤ n ≤ 2048) .
Saída
Para cada caso de teste imprima o número mínimo de pesos necessários para pesar o objeto
dado.
Exemplo de entrada
4
1
10
100
1000
Saída para o exemplo de entrada
1
2
3
3
3
Problema C
Vírus
3
5
6
7
1
9
2
4
8
Estamos em um país da África, onde um vírus perigosíssimo acaba de chegar em uma grande
cidade. O país vai ter que tomar medidas extremas para que ele não se propague. A única
saída será bloquear estradas que chegam nas cidades infectadas. Mas o país só tem
dinheiro para bloquear um único trecho de estrada. A Vigilância Sanitária quer descobrir se
existe um trecho de estrada que, quando bloqueado, separa o resto do país da área
infectada. Você vai ajudar, fazendo um programa para identificar se existe um tal trecho
e indicar qual o número máximo de cidades que podem ser isoladas do vírus. Observe que
pode haver mais de um trecho de estrada entre duas cidades.
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. A seguir são descritos t testes. Cada teste é
descrito em várias linhas. A primeira contém 3 inteiros: n (1 ≤ n ≤ 1000), o número de
cidades do país, m (n-1 ≤ m ≤ 10000), o número de interligações entre as cidades e
c (1 ≤ c ≤ n), o número da cidade infectada. A seguir vêm m linhas com 2 inteiros indicando
todos os pares de cidades interligadas.
Saída
Para cada caso de teste imprima o número máximo de cidades que podem ser isoladas com o
bloqueio de um trecho de estrada. Se não houver um trecho com as características
procuradas, responda 0.
Exemplo de entrada
2
9 10 3
13
42
34
53
45
65
76
65
87
89
441
12
23
34
14
Saída para o exemplo de entrada
3
0
4
Problema D
Rede sob ataque!
Ataques a servidores importantes numa rede de computadores constituem uma ameaça
constante. As formas de ataque são muitas e, quando uma equipe de Segurança da
Informação detecta um servidor comprometido, desliga-o imediatamente para evitar perda
de informações sigilosas e que uma possível infecção se alastre. A grande desvantagem
desta abordagem é que os servidores são utilizados como pontes (gateways) para troca de
mensagens entre os outros servidores. Assim, quando um servidor sai do ar, ele deixa de
ser um possível intermediário na comunicação entre dois outros servidores. Quando todos
os caminhos de um servidor A a outro B possuem como servidor intermediário um certo nó
C, dizemos que C é um ponto de vulnerabilidade da rede.
Sua missão é escrever um programa que ajude no estudo de uma rede, detectando seus
pontos de vulnerabilidade. A intenção é usar este estudo como base para uma avaliação de
quão robusta é uma rede (quanto menos pontos de vulnerabilidade, mais robusta é
considerada a rede)..
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 contém 2 inteiros: n (1 ≤ n ≤ 1000) representando o
número de servidores na rede, e m (n-1 ≤ m ≤ 1000000), o número de interligações entre
pares de servidores por onde uma mensagem pode transitar, Em seguida, há m linhas com 2
inteiros indicando todos os pares de servidores interligadas.
Saída
Para cada caso de teste imprima o número de pontos de vulnerabilidades encontrados.
Exemplo de entrada
3
32
12
23
44
12
23
34
14
13 14
12
23
34
37
45
57
56
78
89
8 10
8 11
11 12
12 13
11 13
Exemplo de saída
1
0
6
5
Problema E
Somando
Um problema clássico é o de determinar todos os subconjuntos cuja soma é determinado
valor, dado um conjunto de inteiros positivos. Agora você tem que calcular algo mais
simples. Dado um conjunto de n numeros inteiros e um valor s, você deve apenas calcular
quantos subconjuntos têm a soma de seus elementos igual ou superior a s.
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 duas linhas. A primeira contém dois inteiros n (1 ≤ n ≤ 100), o número de
elementos do conjunto e s (1 ≤ s ≤ 100), o valor mínimo que a soma dos elementos dos
subconjuntos procurados deve ter. Na segunda linha vêm n inteiros ordenados de forma não
decrescente, todos entre 1 e 1000.
Saída
Para cada caso de teste imprima o número de subconjuntos cuja soma é igual ou superior a
s.
Exemplo de entrada
3
40 2
2222222222222222222222222222222222222222
56
22222
10 100
1 3 5 7 9 11 13 15 17 19
Saída para o exemplo de entrada
1099511627775
16
1
6
Problema F
Subtraindo
Cinco amigos de várias idades se encontram para almoçar e começam a especular qual seria
a maior diferença de idade entre dois amigos no grupo. Você é um dos amigos e pode
calcular isso, pois quem disser mais rápido esse valor não pagará a conta do restaurante.
Faça rápido um programa para obter o resultado.
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. A seguir são descritos t testes. Cada teste é
descrito em uma linha com 5 inteiros, as idades dos amigos.
Saída
Para cada caso de teste imprima a diferença máxima de idade entre dois amigos do grupo.
EXEMPLO DE ENTRADA
3
18 10 9 60 44
21 21 21 21 21
19 21 18 19 20
EXEMPLO DE SAÍDA
51
0
3
7
Problema G
Quadratura do retângulo
a+b
a
b
No século XX muitos matemáticos trataram da decomposição de retângulos e quadrados em
quadrados distintos e, surpreendentemente, a solução para esse problema encontra
aplicações em circuitos elétricos. Neste problema, você vai trabalhar com uma partição em
quadrados especial definida na figura acima. Em tal partição, o menor quadrado tem lado a
(número inteiro), o segundo menor tem lado b (número inteiro) e os lados dos demais
quadrados podem ser inferidos a partir da soma dos lados de algum subconjunto de
quadrados menores, conforme a figura. Você vai fazer um programa no qual, dados a e b,
deve-se calcular o perímetro do retângulo correspondente, caso seja possível construí-lo,
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. A seguir são descritos t testes. Cada teste é
descrito em uma linha, contendo dois inteiros a e b, representados em 32 bits, indicando,
respectivamente, o lado do menor e do segundo menor quadrados da partição.
Saída
Para cada caso de teste imprima um valor inteiro representando o perímetro do retângulo,
se ele puder ser construído ou 0, caso contrário.
Exemplo de entrada
2
4 10
10 4
Saída para o exemplo de entrada
520
0
8
Problema H
Vetores
Vetores são ferramentas matemáticas muito úteis e tornam muitos cálculos bem fáceis.
Vetores de duas dimensões podem ser desenhados no plano. Para desenhar o vetor (3, 4)
toma-se o retângulo de dimensões 3 x 4 e o vetor é a diagonal desse retângulo que começa
na posição (0, 0) e termia na posição (3, 4). Vetores podem ser justapostos deslocando-se o
começo de um deles para o final do outro. Dessa forma, podemos ter uma área
compreendida pelos vetores justapostos e o eixo x. A figura mostra a justaposição de três
vetores: (3, 4), (4, 0), (8, 4), gerando uma área de 6+16+48 = 70. Observe que se
tivéssemos trocado a ordem da justaposição dos dois últimos vetores, teríamos obtido uma
área de 6+48+32=86.
Neste problema você vai receber uma série de vetores e determinar qual a maior área que
pode ser formada pela justaposição dos mesmos.
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. A seguir são descritos t testes. Cada teste é
descrito em duas linhas. Na primeira vem o número n de vetores (1 ≤ n ≤ 1000). Na segunda
linha vêm 2n pares de inteiros positivos, representando as dimensões x e y de cada vetor.
Essas dimensões variam de 0 a 1000.
Saída
Para cada caso imprimir uma linha contendo um valor real, com uma decimal, indicando a
área máxima que pode ser conseguida justapondo-se convenientemente os vetores.
Exemplo de Entrada
2
3
34 40 8 4
2
1133
Exemplo de Saída
86.0
8.0
9
Problema I
Burlando a Balança
Algumas crianças de uma escola
descobriram que se pesassem em
uma máquina de pesagem aos pares,
e depois trocassem de lugares - um
de cada vez , poderiam obter o
peso correto de todos, pagando apenas uma vez.
O grupo tinha 5 crianças e eles obtiveram as seguintes pesagens: 101, 102, 103, 103, 104,
104, 105, 105, 106, 107. Os pesos de cada um eram 50, 51, 52 , 53, 54. Como pesar dessa
forma e achar o peso de cada criança separadamente?
Dada um valor n e as pesagens de todos os pares de crianças do grupo, determinar o pesos
de cada criança, sabendo-se que esse peso varia entre 40 e 70.
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. A seguir são descritos t testes. Cada teste
contém duas linhas. A primeira linha contém o número n de crianças (3 ≤ n ≤ 100). Na
segunda linha vêm n(n-1)/2 inteiros ordenados, representando os pesos de todos os pares
distintos de crianças. Cada valor varia entre 80 e 140.
Saída
Para cada caso de teste imprima, ordenadamente, os pesos de cada uma das n crianças.
Exemplo de entrada
3
5
80 80 80 80 80 80 80 80 80 80
4
101 102 103 103 104 105
5
101 103 104 107 108 110 112 113 115 119
Saída para o exemplo de entrada
40 40 40 40 40
50 51 52 53
50 51 53 57 62
10
Problema J
Parênteses e mais parênteses...
Em Matemática, a avaliação de expressões envolvendo múltiplos operadores requer a definição
da precedência de aplicação de tais operadores. Por exemplo, é definido o padrão de que numa
expressão algébrica, multiplicações e divisões vêm antes de adições e subtrações, de modo que
3 + 4 x 5 é igual a 23. Mas quando a precedência dos operadores deve ser outra daquela
definida por convenção, o uso dos parênteses se torna necessário, de modo que (3 + 4) x 5
resulta em 35.
Embora a ordem de precedência de operadores de qualquer expressão possa ser totalmente
definida por parênteses, é comum utilizar outros tipos de parênteses para facilitar a leitura,
como as chaves e os colchetes. O problema da avaliação da expressão parentizada bem formada
é aquele de decidir se, dada uma expressão parentizada, se a todo parêntese aberto de um
determinado tipo correspondente unicamente um parêntese fechado de mesmo tipo (e viceversa) e que a sub-expressão entre tal par de abre-e-fecha parênteses é uma expressão
parentizada bem formada.
Neste problema, você deve verificar se uma expressão parentizada, que pode envolver um
número arbitrário de tipos de parênteses, está bem formada. Por simplicidade, apenas os
parênteses são informados na expressão, omitindo-se quaisquer outros elementos. Uma
expressão parentizada é dada por uma sequência de duplas X Y, onde X denota se corresponde
a um abre-parêntese (quando X = A), ou a um fecha-parêntese (quando X = F) e o tipo
do parêntese sendo aberto ou fechado é dado por um valor numérico, valor de Y. Assim, a
dupla A 2 significa que um parêntese do tipo 2 está sendo aberto na expressão, enquanto
a dupla F 3 representa que um parêntese do tipo 3 está sendo fechado na expressão.
Seu trabalho é escrever um programa que determine se expressões que só possuam parênteses,
e codificados como acima, são bem formadas ou não.
Entrada
Haverá vários casos de teste. A primeira linha da entrada é um inteiro t (1 ≤ t ≤ 200) que
indica quantos serão os casos de teste. A seguir são descritos t testes. Cada teste é descrito
em duas linhas. A primeira inicia um inteiro n (1 ≤ n ≤ 100000) representando o número
de parênteses contidos na expressão. Na segunda linha, há n duplas X Y separadas por espaço,
onde X é igual a A (abertura) ou F (fechamento) e Y (1 ≤ n ≤ 100000) representa o tipo
de parêntese sendo aberto ou fechado.
Saída
Para cada caso de teste, imprima S se a expressão parentizada é bem-formada ou N no caso
contrário.
Exemplo de entrada
4
4
A1A2F2F1
4
A1A2F1F2
16
A1A2A3F3A3A3F3A4F4F3A1F1F2A3F3F1
16
A1A2A3F3A3A3F3A4F4F3A1F1F2A3F1F3
Exemplo de saída
S
N
S
N
11
Problema K
Homem Primata
A Teoria Evolucionista consiste da hipótese de que as diversas espécimes de vida,
caracterizadas pela sua estrutura de DNA, foram geradas a partir de mutações de
estruturas de DNA de outras formas de vida com o passar do tempo. Os seres mutantes
que eram adaptados às condições de vida sobreviveram e se reproduziram, estabelecendo,
assim, uma nova espécime de seres vivos.
Um grupo de cientistas evolucionistas de um reconhecido centro de pesquisas conjecturam
que a probabilidade de uma espécime A derivar diretamente de uma espécime B possui
relação com o número mínimo necessário de mutações para se transformar uma cadeia de
DNA de A numa daquela de B. Quanto menor tal número, mais chances há de uma derivação
direta. Você foi contratado por este centro de pesquisas para auxiliá-los neste projeto.
Os quatro subtipos de nucleotídeos são simbolizados por T, A, G e C. Uma cadeia de DNA é
caracterizada, de forma simplificada, por uma sequência de nucleotídeos. Uma mutação em
uma cadeia de DNA consiste de um dentre os seguintes acontecimentos: (i) a aparição de
um nucleotídeo em uma posição arbitrária da cadeia; (ii) a mudança de um nucleotídeo numa
posição arbitrária da cadeia por outro; ou (iii) o desaparecimento de um nucleotídeo numa
posição arbitrária da cadeia.
Sua tarefa é escrever um programa de computador para determinar, dadas duas cadeias de
DNAs A e B, o número mínimo de mutações para que A se transforme em B.
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 duas linhas. Cada linha contém um string representando uma das cadeias de
DNA. Cada cadeia tem de 1 a 1000 nucleotídeos.
Saída
Para cada caso de teste, imprima o número de mínimo de mutações para se transformar a
primeira cadeia na segunda..
Exemplo de entrada
2
CTC
ATCG
ACTG
AAG
Saída para o exemplo de entrada
2
2
12