 |
Az I/S. 38. feladat (2019. október) |
I/S. 38. Egy munkahelyen \(\displaystyle N\) ember dolgozik, akiket 0-tól \(\displaystyle (N-1)\)-ig sorszámokkal azonosítunk. Mindenkinek pontosan egy közvetlen főnöke van, kivéve a 0. sorszámú embert, a cégvezetőt. Minden emberre teljesül, hogy ha vesszük a közvetlen főnökét, majd annak a közvetlen főnökét és így tovább, amíg lehet, akkor végül a cégvezetőhöz jutunk. Egy \(\displaystyle A\) sorszámú embernek beosztottja minden olyan ember, ahonnan az előbbi módon, a közvetlen főnökökön végighaladva egy idő után az \(\displaystyle A\) sorszámú emberhez jutunk. Egy \(\displaystyle A\) sorszámú ember tudja kezelni egy \(\displaystyle B\) sorszámú beosztottját, ha a cégnél töltött éveik számának különbsége legfeljebb \(\displaystyle K\). Egy \(\displaystyle A\) sorszámú ember jó főnök, ha minden beosztottját tudja kezelni (ha valakinek nincs beosztottja, akkor jó főnök). Készítsünk programot, amely megadja a jó főnökök számát.
Standard bemenet: az első sor tartalmazza \(\displaystyle N\)-et és \(\displaystyle K\)-t. A következő sor \(\displaystyle {N-1}\) darab számot tartalmaz, az \(\displaystyle i\)-edik szám az \(\displaystyle i\)-edik sorszámú ember közvetlen főnökének sorszámát. A következő sor \(\displaystyle N\) darab számot tartalmaz, az \(\displaystyle i\)-edik szám az \(\displaystyle (i-1)\)-edik sorszámú ember cégnél töltött éveinek számát.
Standard kimenet: a jó főnökök száma.
Korlátok: \(\displaystyle 3\le N\le {10}^{5}\), \(\displaystyle 0\le K\le {10}^{9}\), \(\displaystyle 1\le \text{a}\) cégnél eltölött évek \(\displaystyle \text{száma} \le {10}^{9}\). Időkorlát: 0,3 mp.
Értékelés: a pontok 50%-a kapható, ha \(\displaystyle N\le 1000\).
Példa:
| Bemenet (a / jel sortörést helyettesít) | Kimenet |
| 7 3 2 0 2 0 4 4 6 1 5 7 10 7 8 | 5 |
Beküldendő egy is38.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. november 11-én LEJÁRT.
Statisztika:
12 dolgozat érkezett. 10 pontot kapott: Horcsin Bálint, Szente Péter, Varga 256 Péter. 9 pontot kapott: Gyimesi Péter, Kovács 202 Bertold. 8 pontot kapott: 2 versenyző. 2 pontot kapott: 1 versenyző. 1 pontot kapott: 4 versenyző.
A KöMaL 2019. októberi informatika feladatai