Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

RONTGEN - Sequências de Röntgen

Wilhelm Conrad Röntgen foi um físico alemão que viveu no final do século XIX e início do século XX. Suas experiências em radiação eletromagnéticas renderam a ele o primeiro prêmio Nobel em Física, outorgado em 1901. Sua principal descoberta foi a existência do "raio X" e seu uso em aplicações médicas. Em 22 de dezembro de 1895, Röntgen fez um raio X da mão de sua esposa (com um anel em um dos dedos). A descoberta do raio X causou grande alvoroço na época e já em 1896 jornais europeus noticiavam a invenção e as grandes possibilidades de enxergar por dentro dos corpos sem a necessidade de cortá-los. A morte de Röntgen, causada por um certo tipo de câncer, é atribuída às radiações constantes a que esteve exposto durante suas pesquisas científicas.

Röntgen começou a desconfiar da existência de radiações invisíveis quando, nas suas pesquisas, era capaz de medir alterações consideráveis na fluorescência dos objetos quando colocados num tubo de Lenard que era submetido a uma corrente elétrica. Os estudos de Röntgen foram tão precisos que ele pôde inclusive gerar a seqüência que era observada no tubo de Lenard em cada instante de tempo. A fluorescência observada dependia da intensidade da corrente (X) e do tempo em que o tubo era submetido à corrente (Y). Röntgen percebeu que dada a primeira seqüência, a próxima podia ser obtida descrevendo os números da seqüência anterior. Por exemplo: se a primeira seqüência for 2 então a próxima é 12 (ou seja, a seqüência anterior é formada por "um 2"), a seguinte 1112 (ou seja, a seqüência anterior é formada por um 1 e um 2), 3112 (ou seja, a seqüência anterior é formada por três 1 e um 2), e assim por diante.

Além de um cientista brilhante, Röntgen era extremamente organizado. Ele guardava todos os registros de seus experimentos. Infelizmente, com o tempo algumas seqüências foram danificadas e outras perdidas. Sua tarefa é dada uma seqüência, determinar as próximas K seqüências do experimento.

Entrada

Cada instância é composta por uma linha contendo a primeira seqüência do experimento, formada por não mais de 1000 caracteres de 0 a 9, e o número K de seqüências que desejamos gerar (1 ≤ K ≤ 50), respectivamente.

Saída

Para cada instância, imprima a seqüência dada na entrada seguida de K linhas contendo as seqüências na ordem que foram geradas. As seqüências geradas não terão mais do que 2000000 caracteres.

Após cada instância imprima uma linha em branco.

Exemplo de entrada
3
2 5
99 3
000123 3

Exemplo de saída
2
12
1112
3112
132112
1113122112

99
29
1219
11121119

000123
30111213
131031121113
111311101321123113


Adicionado por:Wanderley Guimarăes
Data:2008-10-01
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO PERL6 PY_NBC SCALA TCL
Origem:Primeira Seletiva para Maratona de Programacao IME-USP - 2008

hide comments
2012-09-03 21:59:12 Filipe Ravagnã Piga
Absurdo. Encontrei um algoritmo na internet, que resolve o problema das Sequęncias de Röntgen, e testei ele com os valores máximos, e mesmo após horas executando, o programa năo terminou. Submeti este programa aqui no SPOJ e surpresa, ele foi aceito! Ou seja, os valores máximos dos exercícios năo săo testados!
2012-08-27 02:27:36 Carvalho
leia com calma que é possível entender.
Por exemplo se a entrada fosse com letras acho que é mais compreensível. Veja: se a entrada fosse "a", a próxima string seria "1a", depois "111a", porque tinhamos inicialmente apenas 'um' a , depois um 1 + 1 a, logo = 111a, finalmente 31 + 1a = 311a.
2012-04-06 18:05:49 Kelvin Azevedo Santos [FMUSP]
#Rodrigo: Năo :P
2011-09-25 07:17:17 Rodrigo Roim Ferreira [ITA]
Era pro contexto desse enunciado fazer sentido?
2010-05-16 14:54:18 Piotr KÄ…kol
If anybody wanted that's link to an English equivalent of this task:
http://www.spoj.pl/problems/LOOKSAY

And another one but Your task is to write THE SHORTEST PROGRAM YOU CAN (the shorter Your program is, the more points You get):
http://www.spoj.pl/SHORTEN/problems/LOOK_SAY
(for now record is 39 characters in Perl and 121 in C ;-) )

// Edit: The record of 39 chars was beaten to 38 in Perl and in C the shortest is now 115. ;-)

Last edit: 2011-01-08 13:02:39
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.