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:
-
Hann tekur tölu $x$ úr listanum sínum.
-
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$.
-
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:
-
Margföldum $6$ með tölunni $230\, 309\, 227$ og fáum $1\, 381\, 855\, 362$.
-
Leggjum svo töluna $68\, 431\, 307$ við útkomuna, og fáum $1\, 450\, 286\, 669$.
-
Framkvæmum svo deilinguna $1\, 450\, 286\, 669 / 2^{64}$ og fáum út $0$ með afganginn $1\, 450\, 286\, 669$.
-
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:
-
Margföldum $42$ með tölunni $230\, 309\, 227$ og fáum $9\, 672\, 987\, 534$.
-
Leggjum svo töluna $68\, 431\, 307$ við útkomuna, og fáum $9\, 741\, 418\, 841$.
-
Framkvæmum svo deilinguna $9\, 741\, 418\, 841 / 2^{64}$ og fáum út $0$ með afganginn $9\, 741\, 418\, 841$.
-
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:
-
Margföldum $806\, 515\, 533\, 049\, 393$ með tölunni $230\, 309\, 227$ og fáum $185\, 747\, 968\, 980\, 098\, 654\, 649\, 211$.
-
Leggjum svo töluna $68\, 431\, 307$ við útkomuna, og fáum $185\, 747\, 968\, 980\, 098\, 723\, 080\, 518$.
-
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$.
-
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 |