NézetNyomtat

Becsületes figyelmeztetés
Címkék > Feladat

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.
titj legalább egy i, j pár esetén.

Kis bemenet

2 ≤ N ≤ 3.
1 ≤ ti ≤ 108.

Nagy bemenet

2 ≤ N ≤ 1000.
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

Tesztadatok