Caderno de provas maratona 2017
19 pág.

Caderno de provas maratona 2017


DisciplinaPreparação para Maratona de Programação I17 materiais19 seguidores
Pré-visualização4 páginas
acmInternational CollegiateProgramming Contest eventsponsor2017
Maratona de Programac¸a\u2dco da SBC 2017
Sub-Regional Brasil do ACM ICPC
9 de Setembro de 2017
Caderno de Problemas
Informac¸o\u2dces Gerais
Este caderno conte´m 13 problemas; as pa´ginas esta\u2dco numeradas de 1 a 18, na\u2dco contando esta pa´gina de rosto.
Verifique se o caderno esta´ completo.
A) Sobre os nomes dos programas
1) Sua soluc¸a\u2dco deve ser chamada codigo de problema.c, codigo de problema.cpp, codigo de problema.pas, co-
digo de problema.java ou codigo de problema.py, onde codigo de problema e´ a letra maiu´scula que identifica o
problema. Lembre que em Java o nome da classe principal deve ser igual ao nome do arquivo.
B) Sobre a entrada
1) A entrada de seu programa deve ser lida da entrada padra\u2dco.
2) A entrada e´ composta de um u´nico caso de teste, descrito em um nu´mero de linhas que depende do problema.
3) Quando uma linha da entrada conte´m va´rios valores, estes sa\u2dco separados por um u´nico espac¸o em branco; a
entrada na\u2dco conte´m nenhum outro espac¸o em branco.
4) Cada linha, incluindo a u´ltima, conte´m exatamente um caractere final-de-linha.
5) O final da entrada coincide com o final do arquivo.
C) Sobre a sa´\u131da
1) A sa´\u131da de seu programa deve ser escrita na sa´\u131da padra\u2dco.
2) Quando uma linha da sa´\u131da conte´m va´rios valores, estes devem ser separados por um u´nico espac¸o em branco;
a sa´\u131da na\u2dco deve conter nenhum outro espac¸o em branco.
3) Cada linha, incluindo a u´ltima, deve conter exatamente um caractere final-de-linha.
Promoc¸a\u2dco:
v1.0
Maratona de Programac¸a\u2dco da SBC \u2013 ACM ICPC \u2013 2017 1
Problema A
Acordes intergala´ticos
A maratona de composic¸a\u2dco de sonatas para piano intergala´tico esta´ tentando dificultar a vida dos
competidores, pois cada vez mais seres de intelige\u2c6ncia superior esta\u2dco participando. O piano e´ composto
de N teclas, numeradas de 0 a N \u2212 1. O sistema tonal intergala´tico possui 9 notas musicais, com
valores de 0 a 8. Inicialmente todas as teclas do piano esta\u2dco associadas a` mesma nota 1. O competidor
vai tocar uma seque\u2c6ncia de acordes. Cada acorde intergala´tico e´ composto por duas teclas distintas,
a e b, 0 \u2264 a < b < N . Quando o acorde e´ tocado, o piano vai emitir a nota mais frequente, f , entre
todas as teclas do intervalo [a, b]. Se houver mais de uma nota mais frequente, ele emite a maior delas.
Imediatamente apo´s emitir a nota, o piano muda a nota associada a todas as teclas do intervalo [a, b].
A nova nota associada a` tecla k, a \u2264 k \u2264 b, sera´ a anterior mais f , mo´dulo 9.
Por exemplo, se em determinado momento as notas associadas a um piano de N = 15 teclas sa\u2dco
teclas 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
notas 2 2 1 4 5 4 3 4 8 0 1 6 2 0 1
e o acorde [3, 9] e´ tocado, enta\u2dco a nota mais frequente sera´ 4 e as novas notas apo´s o acorde sera\u2dco:
teclas 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
notas 2 2 1 8 0 8 7 8 3 4 1 6 2 0 1
Dada a seque\u2c6ncia de Q acordes, seu programa deve imprimir as notas que estara\u2dco associadas a`s
teclas do piano apo´s todos os acordes da seque\u2c6ncia terem sido tocados.
Entrada
A primeira linha da entrada conte´m dois inteiros, N (2 \u2264 N \u2264 100000), e Q (1 \u2264 Q \u2264 100000),
respectivamente o nu´mero de teclas do piano intergala´tico e a quantidade de acordes. As Q linhas
seguintes conte\u2c6m, cada uma, dois inteiros A e B, (0 \u2264 A < B < N), representando um acorde.
Sa´\u131da
Seu programa deve imprimir N inteiros, um por linha, representando as notas associadas a`s teclas
do piano, apo´s todos os acordes terem sido tocados.
Exemplos
Exemplo de entrada 1
5 3
1 2
0 4
0 2
Exemplo de sa´\u131da 1
5
6
6
2
2
Maratona de Programac¸a\u2dco da SBC \u2013 ACM ICPC \u2013 2017 2
Exemplo de entrada 2
15 15
10 12
4 5
1 14
6 10
9 11
11 12
9 13
8 9
5 7
11 13
8 10
11 12
11 13
8 14
3 9
Exemplo de sa´\u131da 2
1
2
2
1
2
6
7
7
8
6
4
4
8
0
4
Maratona de Programac¸a\u2dco da SBC \u2013 ACM ICPC \u2013 2017 3
Problema B
Brincadeira
Um Registrador de Deslocamento e´ um circuito que desloca de uma posic¸a\u2dco os elementos de um vetor
de bits. O registrador de deslocamento tem uma entrada (um bit) e uma sa´\u131da (tambe´m um bit),
e e´ comandado por um pulso de relo´gio. Quando o pulso ocorre, o bit de entrada se transforma no
bit mais significativo do vetor, o bit menos significativo e´ jogado na sa´\u131da do registrador, e todos os
outros bits sa\u2dco deslocados de uma posic¸a\u2dco em direc¸a\u2dco ao bit menos significativo do vetor (em direc¸a\u2dco
a` sa´\u131da).
Um Registrador de Deslocamento com Retroalimentac¸a\u2dco Linear (em ingle\u2c6s, LFSR) e´ um registrador
de deslocamento no qual o bit de entrada e´ determinado pelo valor do ou-exclusivo de alguns dos bits
do registrador antes do pulso de relo´gio. Os bits que sa\u2dco utilizados na retroalimentac¸a\u2dco do registrador
sa\u2dco chamados de torneiras. A figura abaixo mostra um LFSR de 8 bits, com tre\u2c6s torneiras (bits 0, 3
e 5).
10010101
estado inicial
bit 0
0
1
00101011
estado apo´s um pulso
bit 0
0
0
01010110
estado apo´s dois pulsos
bit 0
1
0
10101100
estado apo´s tre\u2c6s pulsos
bit 0
1
0
Durante uma competic¸a\u2dco de programac¸a\u2dco, enquanto aguardam a divulgac¸a\u2dco do resultado final,
Ricardo e Cla´udio se divertem com um LFSR que encontraram no local.
Eles usam o LFSR para gerar uma seque\u2c6ncia infinita de nu´meros. Para gerar tal seque\u2c6ncia, antes
de cada pulso do relo´gio, os bits do registrador sa\u2dco convertidos para decimal. Assim, para um LFSR
como o da figura os primeiros elementos da seque\u2c6ncia sa\u2dco: A0 = 169 (10101001), A1 = 212 (11010100),
A2 = 106 (01101010), A3 = 53 (00110101) e A4 = 26 (00011010). Note que o valor dos bits antes do
primeiro pulso e´ o primeiro elemento da seque\u2c6ncia.
Em cada rodada da brincadeira um deles fala dois nu´meros inteiros, X e Y . Da´\u131 em diante o
outro deve encontrar uma subseque\u2c6ncia cont´\u131gua, de tamanho maior ou igual a Y , dos elementos
da seque\u2c6ncia gerada pelo LFSR, de modo que a soma dos elementos da subseque\u2c6ncia cont´\u131gua seja
divis´\u131vel por X.
De alguma forma os dois sa\u2dco capazes de se divertir com isso e encontrar as respostas mesmo sem
a ajuda de um computador. E voce\u2c6, dada a descric¸a\u2dco de um LSFR e dois inteiros X e Y , e´ capaz de
encontrar uma subseque\u2c6ncia va´lida (ou informar caso na\u2dco exista uma)?
Entrada
A primeira linha conte´m cinco nu´meros inteiros N,T,A0, X e Y . O inteiro N representa o nu´mero
de bits (2 \u2264 N \u2264 30), T e´ o nu´mero de torneiras (1 \u2264 T \u2264 N), A0 e´ a representac¸a\u2dco decimal do estado
inicial do LFSR, X o valor pelo qual a soma da subseque\u2c6ncia cont´\u131gua deve ser divis´\u131vel (1 \u2264 X \u2264 106)
e Y e´ a quantidade m\u131´nima de elementos na subseque\u2c6ncia cont´\u131gua desejada (1 \u2264 Y \u2264 106). Os bits sa\u2dco
identificados por inteiros de 0 (bit menos significativo) a N\u22121 (bit mais significativo). A segunda linha
Maratona de Programac¸a\u2dco da SBC \u2013 ACM ICPC \u2013 2017 4
conte´m T inteiros, separados por espac¸os, representando os identificadores dos bits que sa\u2dco torneiras,
em ordem crescente. O bit 0 sempre e´ uma torneira.
Sa´\u131da
Seu programa deve imprimir, em uma u´nica linha, dois inteiros I e F , representando os \u131´ndices
do primeiro e do u´ltimo elementos da subseque\u2c6ncia cont´\u131gua escolhida. Caso na\u2dco exista uma soluc¸a\u2dco
imprima a palavra impossivel. Caso exista mais de uma soluc¸a\u2dco poss´\u131vel escolha aquela que minimiza
o valor de F . Se mesmo assim houver mais de uma possibilidade opte por aquela que minimiza o valor
de I.
Exemplo de entrada 1
8 3 169 169 1
0 3 5
Exemplo de sa´\u131da 1
0 0
Exemplo de entrada 2
8 3 169 238 2
0 3 5
Exemplo de sa´\u131da 2
13 25
Maratona de Programac¸a\u2dco da SBC \u2013 ACM ICPC \u2013 2017 5
Problema C
Cigarras perio´dicas
As \u201ccigarras perio´dicas\u201d americanas te\u2c6m o ciclo de vida mais longo de todos os insetos conhecidos.