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. 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