Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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:

Az S. 138. feladat értékelése még nem fejeződött be.


A KöMaL 2019. novemberi informatika feladatai