Problem H
Leynitölur
Languages
en
is
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 |
875611033061344128 137438953472 8944394323791464 8388608 6 1307674368000 602 1836311903 41835 355687428096000 3628800 451909860726587616 743301543085819453 263747951750360 679891637638612258 724066394573497037 55534064877048198 14544636039226909 192137918101841817 7 264118168634493448 384 251 61305790721611591 832721640469329331 362880 576460752303423488 2750016719520991 420196140727489673 929 6402373705728000 73007772802 288230376151711744 1 28 64 91482563640 0 16777216 806515533049393 207 930 885703806313795871 2674440 3 343059613650 8 848821429864631901 5040 33550336 2 947 204 400763223 108500229861914394 65346306570478875 4 4294967296 137438691328 121645100408832000 603441230355458022 13933569346707 8128 738009091801197773 158 212336130412243110 66368199913921497 179224005103730170 22944749046030949 205043723361104587 42 6227020800 822173150480239530 11130037491592671 72057594037927936 160500643816367088 139583862445 311 556704809728838604 4503599627370496 953467954114363 610 897145272235330422 182829778442895830 38756443662964566 426548945951821605 259695496911122585 129644790 496 150145796978065540 1767263190 144115188075855872 5 87178291200 120 6 8589869056 498522796180270956 541595904581297566 9 |
