Becsületes figyelmeztetés
Google Code Jam: Fair warning
A 2010-es Code Jam selejtező fordulójának második feladata nagy számok aritmetikájával foglalkozott:
Feladat
Bolygónkon - a Jamcode IX-en - három Nagy Esemény történt, 26000, 11000 és 6000 évvel ezelőtt. 4000 év múlva mindegyik Nagy Eseményen annyi idővel leszünk túl, ami 5000 többszöröse. Ez az apokalipszis eljövetelét jelentheti...
Szerencsére Te a Jamcode X bolygó lakója vagy! A Jamcode IX-et elérte végzete,
kevesebb mint egy évvel ezelőtt. De vigyázz! A Jamcode X-re is vonatkozik egy fenyegető profécia: "A Nagy Események első optimális évfordulóján eljön az apokalipszis.
64 bit nem lesz elég a meneküléshez! Figyelmeztettünk..."
A Jamcode X lakói komolyan veszik ezt a figyelmeztetést. Minden Nagy Esemény megtörtént már, és ismert az időpontjuk. A proféciáról a következő elméletet állították fel a bolygó tudósai:
y ≥ 0 év múlva az összes Nagy Esemény óta eltelt idő osztható lesz egy maximális T számmal. Meg kell találnunk a legkisebb y értéket, amire a maximális T előáll, ez lesz az optimális évforduló, amikor eljön a világvége.
Feladatunk a világvége időpontjának meghatározása. De ne feledjük a jóslatot: a 64-bites egészek nem feltétlenül elegendőek a feladat megoldásához!
Bemenet
Az első sor a tesztesetek C száma. A következő C sorban először egy N egész, majd N darab további ti egész van, a Nagy Eseményektől a mai napig eltelt évek száma.
Kimenet
Minden bemenetre meg kell adni a lehetséges legkisebb y értéket, amivel ti + y osztható a lehetséges legnagyobb T egésszel, minden i esetén.
Méretek
1 ≤ C ≤ 100.
ti ≠ tj legalább egy i, j pár esetén.
ti ≠ tj legalább egy i, j pár esetén.
Kis bemenet
2 ≤ N ≤ 3.
1 ≤ ti ≤ 108.
1 ≤ ti ≤ 108.
Nagy bemenet
2 ≤ N ≤ 1000.
1 ≤ ti ≤ 1050.
1 ≤ ti ≤ 1050.
Példa
| Bemenet | Kimenet |
3 3 26000000 11000000 6000000 3 1 10 11 2 800000000000000000001 900000000000000000001 |
Case #1: 4000000 Case #2: 0 Case #3: 99999999999999999999 |