7/28/2019 Problemas OTI
1/23
PROBLEMA A:
O Problema 3n + 1
Introduo
Os problemas em Cincia da Computao so normalmente classificados como pertencendo a
alguma classse de problemas (por exemplo, NP, No-solucionveis, Recursivos). Neste
problema voc estar analisando uma propriedade de um algoritmo cuja classificao no
conhecida para nenhuma entrada.
O Problema
Considere o seguinte algoritmo:
1. leia n
2. imprima n
3. se n = 1 ento PARE4. se n mpar ento n 3n + 1
5. seno n n / 2
6. V para o passo 2
Dado a entrada 22, a seguinte sequncia de nmeros ser exibida 22 11 34 17 52 26 13 40 20
10 5 16 8 4 2 1
Conjectura-se que o algoritmo acima ir terminar (quando 1 impresso) para qualquer valor
inteiro de entrada. Apesar da simplicidade do algoritmo, no se sabe se essa conjectura
verdadeira. Foi verificado, entretanto, para todos os inteiros n tais que 0 < n < 1.000.000 (e, de
fato, para muitos nmeros mais do que isso.)
Dado um valor de entrada n, possvel determinar o nmero de nmeros impressos (incluindo
a 1). Para um dado n isso chamado de ciclo de comprimento de n. No exemplo acima, a
durao do ciclo de 22 16.
Para quaisquer nmeros i e j voc deve determinar o tamanho do ciclo mximo para todos os
nmeros entre iej.
A Entrada
A entrada ser composta de uma srie de pares de inteiros i e j, um par de inteiros por linha.
Todos os inteiros sero menores que 1.000.000 e maiores que 0.
Voc deve processar todos os pares de nmeros inteiros e para cada par determinar o
tamanho do ciclo mximo para todos os inteiros entre i e j incluindo eles.
Voc pode assumir que nenhuma operao estoura um inteiro de 32 bits.
A Sada
Para cada par de inteiros de entrada i ej voc deve exibir i, j e o tamanho do ciclo mximo de
inteiros entre i ej, incluindo eles. Esses trs nmeros devem ser separados por pelo menos um
7/28/2019 Problemas OTI
2/23
espao com todos os trs nmeros em uma linha e com uma linha de sada para cada linha de
entrada. Os inteiros i e j devem aparecer na sada na mesma ordem na qual aparecem na
entrada e devem ser seguidos pelo tamanho do ciclo mximo (na mesma linha).
Exemplo de Entrada
1 10100 200
201 210
900 1000
Exemplo de Sada
1 10 20
100 200 125
201 210 89
900 1000 174
7/28/2019 Problemas OTI
3/23
PROBLEMA A:
The 3n + 1 problem
Background
Problems in Computer Science are often classified as belonging to a certain class of problems
(e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an
algorithm whose classification is not known for all possible inputs.
The Problem
Consider the following algorithm:
1. input n
2. print n
3. if n = 1 then STOP
4. if n is odd then tex2html_wrap_inline445. else tex2html_wrap_inline46
6. GOTO 2
Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40
20 10 5 16 8 4 2 1
It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral
input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is
true. It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact,
for many more numbers than this.)
Given an input n, it is possible to determine the number of numbers printed (including the 1).
For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is
16.
For any two numbers i and j you are to determine the maximum cycle length over all numbers
between i and j.
The Input
The input will consist of a series of pairs of integers i and j, one pair of integers per line. All
integers will be less than 1,000,000 and greater than 0.
You should process all pairs of integers and for each pair determine the maximum cycle length
over all integers between and including i and j.
You can assume that no operation overflows a 32-bit integer.
The Output
For each pair of input integers i and j you should output i, j, and the maximum cycle length for
integers between and including i and j. These three numbers should be separated by at least
one space with all three numbers on one line and with one line of output for each line of input.
7/28/2019 Problemas OTI
4/23
The integers i and j must appear in the output in the same order in which they appeared in the
input and should be followed by the maximum cycle length (on the same line).
Sample Input
1 10
100 200201 210
900 1000
Sample Output
1 10 20
100 200 125
201 210 89
900 1000 174
7/28/2019 Problemas OTI
5/23
PROBLEMA B:
O Problema dos Blocos
Introduo
Muitas reas da Cincia da Computao usam domnios abstratos e simples tanto para estudos
analticos quanto empricos. Por exemplo, um recente estudo de IA em planejamento e
robtica (STRIPS) usou um conjunto de blocos na qual um brao-rob realiza tarefas
envolvendo a manipulao dos blocos.
Neste problema voc ir modelar um simples conjunto de blocos sob certas regras e
restries. Melhor do que determinar como alcanar um estado especfico, voc ir
programar um brao robtico para responder a um conjunto limitado de comandos.
O Problema
O problema analisar uma srie de comandos que instruem o brao-rob sobre comomanipular blocos que esto em uma mesa. Inicialmente existem n blocos na mesa (numerados
de 0 a n-1) com o bloco bi adjacente ao bloco bi+1 para todos os 0 i < n-1 como mostra a
figura abaixo:
Figura 1 - Conjunto inicial de blocos
Os comandos vlidos para o brao-rob que manipulam os blocos so:
move a onto bonde a e b so nmeros dos blocos, colocar o bloco a sobre o bloco b e depois
retornando qualquer bloco que est empilhado sobre os blocos a e b para suas posies
iniciais.
move a over bonde a e b so nmeros dos blocos, colocar o bloco a no topo da pilha contendo o
bloco b, depois retornando qualquer bloco que est empilhado sobre o bloco a para suas
posies iniciais.
pile a onto bonde a e b so nmeros dos blocos, mover a pilha de bloco contendo o bloco a, e
qualquer bloco que est empilhado sobre o bloco a, sobre o bloco b. Todos os blocos sobre o
bloco b so movidos para suas posies iniciais antes que o movimento acontea. Os blocosempilhados sobre o bloco a mantm suas ordens quando movidos.
pile a over bonde a e b so nmeros dos blocos, colocar a pilha de bloco contendo o bloco a, e
qualquer bloco que est empilhado sobre o bloco a, no topo da pilha contendo o bloco b. Os
blocos empilhados sobre o bloco a mantm suas ordens quando movidos.
quit
7/28/2019 Problemas OTI
6/23
termina a manipulao no conjunto de blocos.
Qualquer comando na qual a = b or na qual a e b esto na mesma pilha de blocos um
comando ilegal. Todos os comandos ilegais devem ser ignorados e no devem afetar a
configurao dos blocos.
A Entrada
A entrada comea com um inteiro n sozinho em uma linha, representando o nmero de blocos
no conjunto de blocos. Assuma que 0 < n < 25.
O nmero de blocos seguido para uma sequncia de comandos de blocos, um comando por
linha. Seu programa deve processar todos os comandos at que o comando quit seja
encontrado.
Assuma que todos os comandos sero da forma especificada acima. No havero comando
sintaticamente incorretos.
A Sada
A sada deve ser o estado final do conjunto de blocos. Cada posio do bloco original
numerado i ( 0 i< n onde n o nmero de blocos) devem aparecer seguido imediatamente
de dois pontos. Se houver pelo menos um bloco nesta posio, o dois pontos deve ser seguido
por um espao, seguido por uma lista de blocos que aparecem empilhados nesta posio com
cada nmero do bloco separado do outro nmero do bloco por um espao. No coloque
nenhum espao no final da linha.
Deve ter uma linha de sada para cada posio de bloco (ou seja, n linhas de sada onde n o
inteiro na primeira linha da entrada).
Exemplo de Entrada
10
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit
Exemplo de Sada
0: 0
1: 1 9 2 4
2:
3: 3
4:
5: 5 8 7 6
6:
7/28/2019 Problemas OTI
7/23
7:
8:
9:
7/28/2019 Problemas OTI
8/23
PROBLEMA B:
The Blocks Problem
Background
Many areas of Computer Science use simple, abstract domains for both analytical and
empirical studies. For example, an early AI study of planning and robotics (STRIPS) used a block
world in which a robot arm performed tasks involving the manipulation of blocks.
In this problem you will model a simple block world under certain rules and constraints. Rather
than determine how to achieve a specified state, you will program a robotic arm to respond
to a limited set of commands.
The Problem
The problem is to parse a series of commands that instruct a robot arm in how to manipulate
blocks that lie on a flat table. Initially there are n blocks on the table (numbered from 0 to n-1)with block bi adjacent to block bi+1 for all 0 i < n-1 as shown in the diagram below:
Figura 2 - Initial blocks world
The valid commands for the robot arm that manipulates blocks are:
move a onto bwhere a and b are block numbers, puts block a onto block b after returning any blocks
that are stacked on top of blocks a and b to their initial positions.
move a over bwhere a and b are block numbers, puts block a onto the top of the stack containing block
b, after returning any blocks that are stacked on top of block a to their initial positions.
pile a onto bwhere a and b are block numbers, moves the pile of blocks consisting of block a, and any
blocks that are stacked above block a, onto block b. All blocks on top of block b are moved to
their initial positions prior to the pile taking place. The blocks stacked above block a retain
their order when moved.
pile a over bwhere a and b are block numbers, puts the pile of blocks consisting of block a, and any
blocks that are stacked above block a, onto the top of the stack containing block b. The blocks
stacked above block a retain their original order when moved.
quitterminates manipulations in the block world.
7/28/2019 Problemas OTI
9/23
Any command in which a = b or in which a and b are in the same stack of blocks is an illegal
command. All illegal commands should be ignored and should have no affect on the
configuration of blocks.
The Input
The input begins with an integer n on a line by itself representing the number of blocks in theblock world. You may assume that 0 < n < 25.
The number of blocks is followed by a sequence of block commands, one command per line.
Your program should process all commands until the quit command is encountered.
You may assume that all commands will be of the form specified above. There will be no
syntactically incorrect commands.
The Output
The output should consist of the final state of the blocks world. Each original block position
numbered i(0 i< n where n is the number of blocks) should appear followed immediately by
a colon. If there is at least a block on it, the colon must be followed by one space, followed by
a list of blocks that appear stacked in that position with each block number separated from
other block numbers by a space. Don't put any trailing spaces on a line.
There should be one line of output for each block position (i.e., n lines of output where n is the
integer on the first line of input).
Sample Input
10
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit
Sample Output
0: 0
1: 1 9 2 4
2:
3: 3
4:
5: 5 8 7 6
6:
7:
8:
9:
7/28/2019 Problemas OTI
10/23
PROBLEMA C:
Um N Muito Distante
O Problema
Para evitar o potencial problema de loops infinitos de mensagens de rede (pacotes) dentro de
uma rede, cada mensagem contm um campo Time To Live (TTL). Este campo contm o
nmero de ns (estaes, computadores, etc.) que podem retransmitir a mensagem,
encaminhando-a at o seu destino, antes da mensagem ser rudemente ignorados. Cada vez
que uma estao recebe uma mensagem o campo TTL decrementado de 1. Se o destino da
mensagem a estao atual, ento o valor do campo TTL ignorado. Entretanto, se a
mensagem deve ser encaminhada, e o campo TTL decrementado contm zero, ento a
mensagem no encaminhada.
Neste problema dada a descrio de um nmero de redes, e para cada rede pedido para
determinar o nmero de ns que no so alcanveis dado um n inicial e valor do campo TTL.
Considere a rede exemplo a seguir:
Se uma mensagem com um campo TTL de 2 foi enviado a partir do n 35, ela pode atingir os
ns de 15, 10, 55, 50, 40, 20 e 60. No poderia chegar aos ns 30, 47, 25, 45 ou 65, uma vezque o campo TTL teria chegado a zero quando a mensagem atingiu os ns 10, 20, 50 e 60. Se
aumentarmos o valor inicial do campo TTL para 3, partindo do n 35 uma mensagem pode
chegar a todos, exceto o n 45.
Entrada e Sada
Haver mltiplas configuraes de rede fornecidas na entrada. Cada descrio da rede comea
com um inteiro NC especificando o nmero de conexes entre ns da rede. Um valor de NC de
zero marca o fim dos dados de entrada. Aps o NC haver pares NC de inteiros positivos. Estes
pares identificam os ns que so conectados por uma linha de comunicao. No haver mais
de uma linha de comunicao (direta) entre qualquer par de ns, e nenhuma rede vai conter
mais de 30 ns. Aps cada configurao da rede, haver vrias consultas sobre os ns que noso alcanveis a partir de um n inicial e um valor para o campo TTL. Essas consultas so
dadas como um par de inteiros, o primeiro identificando o n inicial e o segundo dando o valor
inicial do campo TTL. As consultas so terminadas por um par de zeros.
Para cada consulta exibida uma linha com o nmero do casos de teste (numerados
seqencialmente a partir do um), o nmero de ns no alcanveis, o nmero do n de
partida, e o valor inicial do campo TTL. O exemplo de entrada e sada abaixo mostra o formato
da entrada e sada do programa.
7/28/2019 Problemas OTI
11/23
Exemplo de Entrada
16
10 15 15 20 20 25 10 30 30 47 47 50 25 45 45 65
15 35 35 55 20 40 50 55 35 40 55 60 40 60 60 65
35 2 35 3 0 0
14
1 2 2 7 1 3 3 4 3 5 5 10 5 11
4 6 7 6 7 8 7 9 8 9 8 6 6 11
1 1 1 2 3 2 3 3 0 0
0
Exemplo de Sada
Case 1: 5 nodes not reachable from node 35 with TTL = 2.
Case 2: 1 nodes not reachable from node 35 with TTL = 3.
Case 3: 8 nodes not reachable from node 1 with TTL = 1.
Case 4: 5 nodes not reachable from node 1 with TTL = 2.
Case 5: 3 nodes not reachable from node 3 with TTL = 2.
Case 6: 1 nodes not reachable from node 3 with TTL = 3.
7/28/2019 Problemas OTI
12/23
PROBLEMA C:
A Node Too Far
The Problem
To avoid the potential problem of network messages (packets) looping around forever inside a
network, each message includes a Time To Live (TTL) field. This field contains the number of
nodes (stations, computers, etc.) that can retransmit the message, forwarding it along toward
its destination, before the message is unceremoniously dropped. Each time a station receives a
message it decrements the TTL field by 1. If the destination of the message is the current
station, then the TTL field's value is ignored. However, if the message must be forwarded, and
the decremented TTL field contains zero, then the message is not forwarded.
In this problem you are given the description of a number of networks, and for each network
you are asked to determine the number of nodes that are not reachable given an initial node
and TTL field value. Consider the following example network:
If a message with a TTL field of 2 was sent from node 35 it could reach nodes 15, 10, 55, 50, 40,
20 and 60. It could not reach nodes 30, 47, 25, 45 or 65, since the TTL field would have been
set to zero on arrival of the message at nodes 10, 20, 50 and 60. If we increase the TTL field'sinitial value to 3, starting from node 35 a message could reach all except node 45.
Input and Output
There will be multiple network configurations provided in the input. Each network description
starts with an integer NC specifying the number of connections between network nodes. An
NC value of zero marks the end of the input data. Following NC there will be NC pairs of
positive integers. These pairs identify the nodes that are connected by a communication line.
There will be no more than one (direct) communication line between any pair of nodes, and no
network will contain more than 30 nodes. Following each network configuration there will be
multiple queries as to how many nodes are not reachable given an initial node and TTL field
setting. These queries are given as a pair of integers, the first identifying the starting node andthe second giving the initial TTL field setting. The queries are terminated by a pair of zeroes.
For each query display a single line showing the test case number (numbered sequentially
from one), the number of nodes not reachable, the starting node number, and the initial TTL
field setting. The sample input and output shown below illustrate the input and output format.
Sample Input
7/28/2019 Problemas OTI
13/23
16
10 15 15 20 20 25 10 30 30 47 47 50 25 45 45 65
15 35 35 55 20 40 50 55 35 40 55 60 40 60 60 65
35 2 35 3 0 0
14
1 2 2 7 1 3 3 4 3 5 5 10 5 114 6 7 6 7 8 7 9 8 9 8 6 6 11
1 1 1 2 3 2 3 3 0 0
0
Sample Output
Case 1: 5 nodes not reachable from node 35 with TTL = 2.
Case 2: 1 nodes not reachable from node 35 with TTL = 3.
Case 3: 8 nodes not reachable from node 1 with TTL = 1.
Case 4: 5 nodes not reachable from node 1 with TTL = 2.
Case 5: 3 nodes not reachable from node 3 with TTL = 2.
Case 6: 1 nodes not reachable from node 3 with TTL = 3.
7/28/2019 Problemas OTI
14/23
PROBLEMA D:
Dgitos Romanos
O Problema
Muitas pessoas esto familiarizadas com os numerais romanos para os nmeros relativamente
pequenos. Os smbolos i, v, x, l, e c representam os valores decimais 1, 5, 10, 50 e
100, respectivamente. Para representar outros valores, esses smbolos, e mltiplos quando
necessrio, so concatenados, com smbolos de menor valor escrito mais para a direita. Por
exemplo, o nmero 3 representado como iii, e o valor 73 representado como lxxiii. As
excees a esta regra ocorrem com os nmeros que possuem como unidades os valores 4 ou
9, e para as dezenas de 40 ou 90. Para estes casos, as representaes numricas romanas so
iv (4), ix (9), xl (40), e xc (90). Assim, as representaes numricas romanas para 24,
39, 44, 49 e 94 so xxiv, xxxix, xliv, xlix, e xciv, respectivamente.
O prefcio de vrios livros possuem pginas numeradas com algarismos romanos, comeando
com i para a primeira pgina do prefcio, e continuando em seqncia. Assuma livros compginas tendo 100 ou menos pginas de prefcio. Quantos caracteres i, v, x, l, e c
so necessrios para numerar as pginas do prefcio? Por exemplo, em um prefcio de cinco
pginas vamos usar a numerao romana i , ii, iii, iv, e v, ou seja, precisamos de 7
caracterres i e 2 caracteres v.
A Entrada
A entrada consistir de uma sequncia de inteiro no intervalo de 1 a 100, terminados por zero.
Para cada inteiro, exceto para o zero, determine o nmero de tipos diferentes de caracteres
necessrios para numerar as pginas de prefcio usando numerais romanos.
A Sada
Para cada inteiro da entrada, escreva uma linha contendo o inteiro de entrada e o nmero
necessrio de cada tipo de caracter. Os exemplos abaixo ilustram o formato aceitvel.
Exemplo de Entrada
1
2
20
99
0
Exemplo de Sada
1: 1 i, 0 v, 0 x, 0 l, 0 c
2: 3 i, 0 v, 0 x, 0 l, 0 c
20: 28 i, 10 v, 14 x, 0 l, 0 c
99: 140 i, 50 v, 150 x, 50 l, 10 c
7/28/2019 Problemas OTI
15/23
PROBLEMA D:
Roman Digits
The Problem
Many persons are familiar with the Roman numerals for relatively small numbers. The symbols
i, v, x, l, and c represent the decimal values 1, 5, 10, 50, and 100 respectively. To
represent other values, these symbols, and multiples where necessary, are concatenated, with
the smaller-valued symbols written further to the right. For example, the number 3 is
represented as iii, and the value 73 is represented as lxxiii. The exceptions to this rule
occur for numbers having units values of 4 or 9, and for tens values of 40 or 90. For these
cases, the Roman numeral representations are iv (4), ix (9), xl (40), and xc (90). So the
Roman numeral representations for 24, 39, 44, 49, and 94 are xxiv, xxxix, xliv, xlix, and
xciv, respectively.
The preface of many books has pages numbered with Roman numerals, starting with i for
the first page of the preface, and continuing in sequence. Assume books with pages having 100or fewer pages of preface. How many i, v, x, l, and c characters are required to
number the pages in the preface? For example, in a five page preface well use the Roman
numerals i, ii, iii, iv, and v, meaning we need 7 i characters and 2 v characters.
The Input
The input will consist of a sequence of integers in the range 1 to 100, terminated by a zero. For
each such integer, except the final zero, determine the number of different types of characters
needed to number the prefix pages with Roman numerals.
The Output
For each integer in the input, write one line containing the input integer and the number of
characters of each type required. The examples shown below illustrate an acceptable format.
Sample Input
1
2
20
99
0
Sample Output
1: 1 i, 0 v, 0 x, 0 l, 0 c
2: 3 i, 0 v, 0 x, 0 l, 0 c
20: 28 i, 10 v, 14 x, 0 l, 0 c
99: 140 i, 50 v, 150 x, 50 l, 10 c
7/28/2019 Problemas OTI
16/23
PROBLEMA E:
Codificador e Decodificador
O Problema
Ser responsvel pelo departamento de informtica da Agncia Internacional de Espionagem,
voc convidado a escrever um programa que permitir que um espio codifique e
decodifique suas mensagens. Voc pode assumir a mensagem de um espio tem no mximo
80 caracteres, e inclui todas as letras maisculas e minsculas do alfabeto mais o espao, e
qualquer um dos seguintes caracteres:
! , . : ; ?
Abaixo est a tabela ASCII dos caracteres vlidos em uma mensagem:
A 65 a 97 32
B 66 b 98 ! 33. . "," 44
. . "." 46
. . ":" 58
Y 89 y 121 , 59
Z90 z 122 ? 63
O algoritmo que voc deve usar para codificar mensagens pegar o valor ASCII de cada
caracter da mensagem, comeando com o ltimo caracter na mensagem e terminando com o
primeiro caracter na mensagem. Voc deve ento adicionar mensagem codificada esse valor
ASCII escrito na ordem inversa. Por exemplo, se o valor ASCII 123, a mensagem codificada
deve conter a string 321. No deve haver espaos para separar os nmeros na mensagem
codificada
Entrada e Sada
O arquivo de entrada consiste de uma ou mais linhas com uma mensagem normal (no
codificada) ou codificada em cada linha.
O arquivo de sada deve ter o mesmo nmero de linhas com a mensagem correspondente
codificada ou decodificada, respectivamente.
Exemplo de Entrada
abc
798999
Have a Nice Day !
Exemplo de Sada
998979
cba
332312179862310199501872379231018117927
7/28/2019 Problemas OTI
17/23
PROBLEMA E:
Encoder and Decoder
The Problem
Being in charge of the computer department of the Agency of International Espionage, you are
asked to write a program that will allow a spy to encode and decode their messages. You can
assume a spy's message is at most 80 characters long, and it includes all the upper and
lowercase letters of the alphabet plus the space, and any of the following characters:
! , . : ; ?
The following is an ASCII table of the valid characters in a message:
A 65 a 97 32
B 66 b 98 ! 33
. . "," 44. . "." 46
. . ":" 58
Y 89 y 121 , 59
Z90 z 122 ? 63
The algorithm that you should use to encode messages is to take the ASCII value of each
character in the message, starting with the last character in the message and ending with the
first character in the message. You should then add on to the coded message this ASCII value
written in reverse order. For example, if the ASCII value is 123, the encoded message should
contain the string "321". There should be no spaces separating the numbers in the encoded
message.
Input and Output
The input file consists of one or more lines with a normal (not encoded) or encoded message
each.
Output file must have the same number of lines with the corresponding encoded message or
the decoded one, respectively.
Sample Input
abc
798999
Have a Nice Day !
Sample Output
998979
cba
332312179862310199501872379231018117927
7/28/2019 Problemas OTI
18/23
PROBLEMA F:
Brazil 2014
O Problema
Imagine que a fase de grupos na Copa do Mundo de Futebol no Brasil tenha terminado. 16
selees permanecem agora, entre as quais uma campe ser determinada pelo seguinte
torneio:
Para cada possvel jogo A vs. B entre essas 16 selees, dada a probabilidade de que a
seleo A ganhe da B. Isto (juntamente com o modo torneio mostrado acima) suficiente para
calcular a probabilidade de que uma determinada seleo ganhe a Copa do Mundo. Por
exemplo, se Germany tem 80% de chance de ganhar do Mexico, Romania tem 60% contra a
contra a Croatia, Germany tem 70% contra Romania, e Germany tem 90% contra Croatia,
7/28/2019 Problemas OTI
19/23
ento a probabilidade de que Germany chegue s semi-finais 80% * (70% * 60% + 90% *
40%) = 62,4%.
Sua tarefa escrever um programa que calcula as chances das 16 selees de se tornar a
Campe do Mundo em 2014.
A Entrada
O arquivo de entrada ir conter apenas um caso de teste.
As primeiras 16 linhas do arquivo de entrada fornece os nomes das 16 selees, de cima para
baixo de acordo com as finais apresentada acima.
Em seguida, haver uma matriz P de inteiros de tamanho 16 x 16, onde o elemento pij d a
probabilidade em porcentagem dessa seleo #iderrotar a seleo #jem uma partida direta.
Seleo #i significa que a i-sima seleo de cima para baixo como indicada na lista de
selees. Na figura acima, Brazil #1 e Germany a #13, ento p1,13 = 55, o que significa que em
uma partida entre Brazil e Germany, Brazil ganha com uma probabilidade de 55%.
Note que as partidas no podem terminar empatadas, ou seja, pij + pji = 100 para todos os i, j.
A Sada
Sada de 16 linhas da forma XXXXXXXXXX p=Y.YY%, onde XXXXXXXXXX o nome da seleo,
justificado esquerda em um campo de 10 caracteres, e Y.YY a sua chance em porcentagem
de ganhar a Copa, escrito com duas casas decimais. Use a mesma ordem de pases como no
arquivo de entrada.
Exemplo de Entrada
Brazil
Chile
Nigeria
Denmark
Holland
Yugoslavia
Argentina
England
Italy
Norway
France
Paraguay
Germany
Mexico
Romania
Croatia
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
35 50 35 45 40 35 35 50 30 40 25 40 25 40 35 35
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
40 55 40 50 45 40 40 55 35 45 30 45 30 45 40 40
45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
7/28/2019 Problemas OTI
20/23
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
35 50 35 45 40 35 35 50 30 40 25 40 25 40 35 35
55 70 55 65 60 55 55 70 50 60 45 60 45 60 55 55
45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45
60 75 60 70 65 60 60 75 55 65 50 65 50 65 60 60
45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45
60 75 60 70 65 60 60 75 55 65 50 65 50 65 60 6045 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
Exemplo de Sada
Brazil p=8.54%
Chile p=1.60%
Nigeria p=8.06%
Denmark p=2.79%
Holland p=4.51%
Yugoslavia p=7.50%
Argentina p=8.38%
England p=1.56%
Italy p=9.05%
Norway p=3.23%
France p=13.72%
Paraguay p=3.09%
Germany p=13.79%
Mexico p=3.11%
Romania p=5.53%
Croatia p=5.53%
7/28/2019 Problemas OTI
21/23
PROBLEMA F:
Brazil 2014
The Problem
Imagine that the group stage at the World Cup of Soccer in Brazil is over. 16 countries are
remaining now, among which the winner is determined by the following tournament:
For each possible match A vs. B between these 16 nations, you are given the probability that
team A wins against B. This (together with the tournament mode displayed above) is sufficient
to compute the probability that a given nation wins the World Cup. For example, if Germany
wins against Mexico with 80%, Romania against Croatia with 60%, Germany against Romania
with 70% and Germany against Croatia with 90%, then the probability that Germany reaches
the semi-finals is 80% * (70% * 60% + 90% * 40%) = 62.4%.
7/28/2019 Problemas OTI
22/23
Your task is to write a program that computes the chances of the 16 nations to become the
World Champion '98.
The Input
The input file will contain just one test case.
The first 16 lines of the input file give the names of the 16 countries, from top to bottom
according to the picture given above.
Next, there will follow a 16 x 16 integer matrix P where element pij gives the probability in
percent that country #idefeats country #jin a direct match. Country #imeans the i-th country
from top to bottom given in the list of countries. In the picture above Brazil is #1 and Germany
is #13, so p1,13 = 55 would mean that in a match between Brazil and Germany, Brazil wins with
a probability of 55%.
Note that matches may not end with a draw, i.e. pij + pji = 100 for all i,j.
The Output
Output 16 lines of the form XXXXXXXXXX p=Y.YY%, where XXXXXXXXXX is the country's
name, left-justified in a field of 10 characters, and Y.YY is their chance in percent to win the
cup, written to two decimal places. Use the same order of countries like in the input file.
Sample Input
Brazil
Chile
Nigeria
Denmark
Holland
Yugoslavia
Argentina
England
Italy
Norway
France
Paraguay
Germany
Mexico
Romania
Croatia
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
35 50 35 45 40 35 35 50 30 40 25 40 25 40 35 35
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
40 55 40 50 45 40 40 55 35 45 30 45 30 45 40 40
45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
35 50 35 45 40 35 35 50 30 40 25 40 25 40 35 35
55 70 55 65 60 55 55 70 50 60 45 60 45 60 55 55
45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45
7/28/2019 Problemas OTI
23/23
60 75 60 70 65 60 60 75 55 65 50 65 50 65 60 60
45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45
60 75 60 70 65 60 60 75 55 65 50 65 50 65 60 60
45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50
Sample Output
Brazil p=8.54%
Chile p=1.60%
Nigeria p=8.06%
Denmark p=2.79%
Holland p=4.51%
Yugoslavia p=7.50%
Argentina p=8.38%
England p=1.56%
Italy p=9.05%
Norway p=3.23%
France p=13.72%
Paraguay p=3.09%
Germany p=13.79%
Mexico p=3.11%
Romania p=5.53%
Croatia p=5.53%