Feladat: S.138 Korcsoport: - Nehézségi fok: -
Füzet: 2019/november, 489 - 490. oldal  PDF  |  MathML 
Témakör(ök): Nehezebb feladat, Számítástudomány

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

H. G. Tannhaus lakásán N darab perc- és óramutatós óra található a falon. Az órákat 1-től N-ig indexeljük. Az i-edik óra percmutatója mi, óramutatója hi hosszú. Tannhaus N napig vizsgálja az órákat. Az i-edik nap egy tetszőleges időpontjában felírja az i-edik óra két mutatója végpontjának távolságát egy lapra; mindegyik számot külön lapra. Azonban Tannhaus néhány távolságot (bár lehet, hogy egyet sem) elszámolt. Sőt a lapok még össze is keveredtek és nem lehet tudni, hogy melyik nap melyik lapra írt. Tudjuk az órák mutatóinak hosszát, valamint hogy a lapokon milyen számok vannak (az összekeveredést követően). Adjuk meg, hogy maximum hány mérést végezhetett el jól Tannhaus.
Bemenet: az első sor tartalmazza az N számot. A következő sor N darab számot tartalmaz: az i-edik szám az mi. Az ezt követő sor ugyancsak N darab számot tartalmaz: az i-edik szám a hi. A bemenet utolsó sora N számot tartalmaz: az i-edik szám a keveredés után az i-edik lapon levő szám.
Kimenet: a program adjon meg egyetlen számot, a maximális helyes mérések számát.
Példa:

 
Bemenet  (a /  jel sortörést helyettesíti)Kimenet   5   4   3 4 1 5 1   4 4 1 10 8   10 2 16 6 5   
 

Korlátok: 3N105, 1mutató hossz, mérési érték (mind egész számok)109. Időkorlát: 0,3 mp.
Értékelés: a pontok 50%-a kapható, ha N1000.
Beküldendő egy s138.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható.