 |
Az S. 138. feladat (2019. november) |
S. 138. H.\(\displaystyle \,\)G. Tannhaus lakásán \(\displaystyle N\) darab perc- és óramutatós óra található a falon. Az órákat 1-től \(\displaystyle N\)-ig indexeljük. Az \(\displaystyle i\)-edik óra percmutatója \(\displaystyle m_{i}\), óramutatója \(\displaystyle h_{i}\) hosszú. Tannhaus \(\displaystyle N\) napig vizsgálja az órákat. Az \(\displaystyle i\)-edik nap egy tetszőleges időpontjában felírja az \(\displaystyle 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 \(\displaystyle N\) számot. A következő sor \(\displaystyle N\) darab számot tartalmaz: az \(\displaystyle i\)-edik szám az \(\displaystyle m_{i}\). Az ezt követő sor ugyancsak \(\displaystyle N\) darab számot tartalmaz: az \(\displaystyle i\)-edik szám a \(\displaystyle h_{i}\). A bemenet utolsó sora \(\displaystyle N\) számot tartalmaz: az \(\displaystyle i\)-edik szám a keveredés után az \(\displaystyle 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:
Korlátok: \(\displaystyle 3\le N\le {10}^{5}\), \(\displaystyle 1\le \text{mutató}\) hossz, mérési érték (mind egész \(\displaystyle \text{számok)}\le {10}^{9}\). Időkorlát: 0,3 mp.
Értékelés: a pontok 50%-a kapható, ha \(\displaystyle N\le 1000\).
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ó.
(10 pont)
A beküldési határidő 2019. december 10-én LEJÁRT.
Statisztika:
8 dolgozat érkezett. 10 pontot kapott: Horcsin Bálint, Varga 256 Péter. 7 pontot kapott: 1 versenyző. 5 pontot kapott: 1 versenyző. 3 pontot kapott: 1 versenyző. 2 pontot kapott: 3 versenyző.
A KöMaL 2019. novemberi informatika feladatai