 |
Az S. 120. feladat (2017. november) |
S. 120. Egy különös autóbusz különc utasok elszállításán dolgozik. A megállókban utasok várakoznak, mindegyikben legalább egy. Néhány megálló között közvetlen buszközlekedés van, tehát a busz más megállók érintése nélkül halad közöttük. Bármely két megálló között pontosan egy útvonal van. Az utasok azért különcök, mert az odaérkező buszra a várakozók közül mindig pontosan egy száll föl. A busz is különös, mert útja során nem halad át olyan megállón, amelyben már nincs várakozó. Nincs menetrend, a buszvezető feladata, hogy a megállókat olyan sorrendben érintse, hogy a lehető legtöbb utast tudja fölvenni.
A megállókat 1-től kiindulva pozitív egészekkel azonosítjuk, az utolsó megálló sorszáma \(\displaystyle M\). Az autóbusz kezdetben az 1-es megállóban tartózkodik, és induláskor fölvesz egy embert. Minden megállóról tudjuk, hogy milyen más megállókkal van közvetlen buszkapcsolatban. Kezdetben minden megállóban legalább egy, legföljebb \(\displaystyle U\) utas várakozik, akik türelmesen várják a buszt, nem hagyják el a megállót. Az autóbusz az utasok összegyűjtése után az 1-es megállóba tér vissza.
A program standard bemenete \(\displaystyle M\) és \(\displaystyle U\), majd a következő \(\displaystyle M\) sor mindegyikében az adott megállóban várakozó utasok száma, utána az adott sorszámú megállóból közvetlen buszjárattal elérhető megállók sorszáma szerepel. A program standard kimenete legyen a legtöbb fölvehető utas száma.
Példak:
| Bemenet egyes újsor karaktereket / jellel helyettesítettünk | Kimenet |
| 12 10 / 3 2 3 6 7 / 6 1 / 2 1 4 / 5 3 / 4 6 / 4 5 1 9 10 11 4 1 8 / 6 7 12 / 6 6 / 5 6 / 2 6 / 3 8 | 26 |
Korlátok: \(\displaystyle 2 \le M \le 100\,000\), \(\displaystyle 1 \le U \le 30\).
Értékelés: a megoldás lényegét leíró dokumentáció 1 pontot ér. További 9 pont kapható arra a programra, amely a korlátoknak megfelelő bemenetekre helyes kimenetet ad 1 másodperc futásidő alatt. Részpontszám kapható arra a programra, amely csak kisebb \(\displaystyle M\) és \(\displaystyle U\) érték esetén ad helyes eredményt 1 másodpercen belül.
Beküldendő egy s120.zip tömörített állományban a megoldást leíró dokumentáció és a program forráskódja.
(10 pont)
A beküldési határidő 2017. december 11-én LEJÁRT.
Mintamegoldásként három versenyző munkáját mutatjuk be:
Gáspár Attila, Miskolc, 12. osztály: s120ga.txt, s120ga.cpp
Horcsin Bálint, Budapest, 9. osztály: s120hb.txt, s120hb.java, grafhb.png
Kiss Gergely, Budapest, 11. osztály: s120kg.txt, s120kg.cpp
A megoldások helyességét az alábbi tesztállományokkal vizsgáltuk: teszek és kimenetek (170MB)
Statisztika:
9 dolgozat érkezett. 10 pontot kapott: Gáspár Attila, Horcsin Bálint, Janzer Orsolya Lili, Kiss Gergely. 9 pontot kapott: Vári-Kakas Andor. 2 pontot kapott: 3 versenyző. 1 pontot kapott: 1 versenyző.
A KöMaL 2017. novemberi informatika feladatai