Hide

Problem H
Leynitölur

Jón litli er með lista af 100 uppáhalds tölunum sínum, allt heiltölur á bilinu $0$ upp í $10^{18}$. Honum er mjög annt um þessar tölur, og vill ekki að neinn komist að því hverjar tölurnar eru. Hann hefur því ákveðið að dulkóða tölurnar sínar, og gerir það á eftirfarandi hátt:

  1. Hann tekur tölu $x$ úr listanum sínum.

  2. Hann margfaldar $x$ með tölunni $230\, 309\, 227$ og leggur svo töluna $68\, 431\, 307$ við útkomuna. Hann deilir svo útkomunni með $2^{64}$, og kallar afganginn úr deilingunni $y$.

  3. Hann gleymir nú tölunni $x$, og geymir í staðinn $y$ sem er dulkóðaða talan.

Hann gerði þetta við allar tölurnar í listanum sínum, og er því núna með 100 dulkóðaðar tölur. En hann gleymdi mikilvægasta hlutanum: hann veit ekki hvernig hann getur afkóðað dulkóðuðu tölurnar sínar. Getur þú hjálpað honum?

Inntak

Inntakið inniheldur hundrað heiltölur, sem hver er dulkóðuð tala, ein á hverri línu.

Úttak

Skrifið út eina línu fyrir hverja dulkóðaða heiltölu í inntakinu. Þessi lína á að innihalda afkóðuðu töluna, sem er heiltala á milli $0$ og $10^{18}$, eða töluna $0$ ef þið vitið ekki hver afkóðaða talan er. Þið megið gera ráð fyrir að það sé nákvæmlega ein tala á milli $0$ og $10^{18}$ sem er afkóðuð útgáfa af samsvarandi tölu í inntakinu. Þ.e. ef hún er dulkóðuð, þá fæst samsvarandi tala í inntakinu.

Stigagjöf

Lausin verður keyrð á lista af 100 dulkóðuðum tölum. Listinn er alltaf sá sami, og er sá sem er sýndur hér fyrir neðan. Lausnin fær 1 stig fyrir hverja tölu sem hún nær að afkóða.

Jón gaf ykkur aukalega eftirfarandi upplýsingar um upprunalega listann af tölunum:

  • 10 tölur eru mjög litlar ($< 10$)

  • 10 tölur eru nokkuð litlar ($< 1000$)

  • 7 tölur eru “Perfect tölur”

  • 10 tölur eru “Factorial tölur”

  • 10 tölur eru á forminu $2^ n$

  • 10 tölur eru “Fibonacci tölur”

  • 10 tölur eru “Catalan tölur”

  • 10 tölur eru “Motzkin tölur”

  • 10 tölur eru “Triangular tölur”

  • 13 tölur eru mjög stórar ($< 10^{18}$)

Útskýring á sýnidæmi

Í sýnidæminu er gefinn listi af 100 dulkóðuðum tölum sem lausnin ykkar verður prófuð á. Úttakið í sýnidæminu gefur dæmi um hvað lausnin ykkar gæti skrifað út. Þar eru allar tölurnar, nema þrjár, $0$.

Á línu 5 í úttakinu skilaði lausnin tölunni $6$. Prufum að dulkóða þessa tölu:

  1. Margföldum $6$ með tölunni $230\, 309\, 227$ og fáum $1\, 381\, 855\, 362$.

  2. Leggjum svo töluna $68\, 431\, 307$ við útkomuna, og fáum $1\, 450\, 286\, 669$.

  3. Framkvæmum svo deilinguna $1\, 450\, 286\, 669 / 2^{64}$ og fáum út $0$ með afganginn $1\, 450\, 286\, 669$.

  4. Afgangurinn $1\, 450\, 286\, 669$ er því dulkóðaða útgáfan af tölunni $6$.

Ef við skoðum nú línu 5 í inntakinu, þá er það einmitt talan $1\, 450\, 286\, 669$ sem var dulkóðaða talan sem Jói litli vildi afkóða. Svarið $6$ er því rétt, og lausnin fær eitt stig fyrir þessa tölu. Það vill líka svo til að talan $6$ er einmitt bæði “Perfect tala” og lítil tala ($< 10$).

Á línu 38 í úttakinu skilaði lausnin tölunni $42$. Prufum að dulkóða þessa tölu:

  1. Margföldum $42$ með tölunni $230\, 309\, 227$ og fáum $9\, 672\, 987\, 534$.

  2. Leggjum svo töluna $68\, 431\, 307$ við útkomuna, og fáum $9\, 741\, 418\, 841$.

  3. Framkvæmum svo deilinguna $9\, 741\, 418\, 841 / 2^{64}$ og fáum út $0$ með afganginn $9\, 741\, 418\, 841$.

  4. Afgangurinn $9\, 741\, 418\, 841$ er því dulkóðaða útgáfan af tölunni $42$.

En ef við skoðum nú línu 38 í inntakinu, þá var það talan $68\, 431\, 307$ sem Jói litli vildi afkóða. Svarið $42$ er því ekki rétt, og lausnin fær ekki stig fyrir þessa tölu.

Á línu 40 í úttakinu skilaði lausnin tölunni $806\, 515\, 533\, 049\, 393$. Prufum að dulkóða þessa tölu:

  1. Margföldum $806\, 515\, 533\, 049\, 393$ með tölunni $230\, 309\, 227$ og fáum $185\, 747\, 968\, 980\, 098\, 654\, 649\, 211$.

  2. Leggjum svo töluna $68\, 431\, 307$ við útkomuna, og fáum $185\, 747\, 968\, 980\, 098\, 723\, 080\, 518$.

  3. Framkvæmum svo deilinguna $185\, 747\, 968\, 980\, 098\, 723\, 080\, 518 / 2^{64}$ og fáum út $10\, 069$ með afganginn $7\, 702\, 901\, 917\, 247\, 859\, 014$.

  4. Afgangurinn $7\, 702\, 901\, 917\, 247\, 859\, 014$ er því dulkóðaða útgáfan af tölunni $806\, 515\, 533\, 049\, 393$.

Ef við skoðum nú línu 40 í inntakinu, þá er það einmitt talan $7\, 702\, 901\, 917\, 247\, 859\, 014$ sem var dulkóðaða talan sem Jói litli vildi afkóða. Svarið $806\, 515\, 533\, 049\, 393$ er því rétt, og lausnin fær eitt stig fyrir þessa tölu. Það vill líka svo til að talan $806\, 515\, 533\, 049\, 393$ er einmitt “Fibonacci tala”.

Sample Input 1 Sample Output 1
18223710894738859083
13206715060184165835
10185240380512959299
1931973892517323
1450286669
6021567682509141451
138714585961
422919574979260288
9635054942852
14552931137501048267
835746191368907
8770042884959775595
6164323997686895178
16905399806933083155
1311420849701858561
14908754392032399994
12890726524107255501
1180101699970319594
15800253748647522238
1680595896
11695533784197154595
88507174475
57876047284
3783748257302582136
2545702210039907996
83574680725067
6341068275406089675
3713883211570731520
16300997420262959118
214025703190
3698343441921813963
16814363719088675361
12393906174592036299
298740534
6517089663
14808221835
2622534442265585971
68431307
3863947716603339
7702901917247859014
47742441296
214256012417
2809041190924859584
615948277489187
759358988
5222818139880373393
1910905123
7910173006526044074
1160826935387
7726952018181579
529049761
218171269276
47051513615
92299468167589928
17357274356146956201
7414039778265390868
989668215
989170598000471499
13206654686002163147
14928293174154046923
18303861531118430445
17742860839300167228
1872021828363
11308186127620784250
36457289173
5883968300900284717
15319152107597547134
9473861667483854665
3981937021227917058
17960730271744214948
9741418841
1434140347029352907
5718061173776289753
9221431121542298880
7710162562126720459
12843829917114508059
13700707387741159706
71694600904
12137560070380009487
15469864720086085067
2426027911978121844
140557059777
15930479467699770909
16819631862868750397
11399132061084986557
4008544522317321026
3457167503216882366
29858391437908637
114301807899
9593390538144192759
407017019262885437
15420325124185009611
1219977442
1631220783811782091
27705538547
1450286669
1978326102387011019
1594237062672645103
11887301847946087637
2141214350
0
0
0
0
6
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
42
0
806515533049393
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

Please log in to submit a solution to this problem

Log in