Az I/S. 24. feladat (2018. február)

I/S. 24. Egy hosszú alagútban egy vágányon közlekedhetnek a vonatok egy irányban. Az érkező vonatok nem egyforma hosszúak és gyorsak, ezért az alagúton különböző idő alatt érnek át. A vonatok adott időpontban jönnek az érkezési oldalon és az alagúton való áthaladás után azonnal továbbhaladnak. Az alagútban egyszerre csak egy vonat tartózkodhat, tehát amikor az átjutott, akkor indulhat a következő. Az érkezési oldalon lévő vonatoknak így általában várakozniuk kell. Az alagút mindkét oldalán elegendő számú vágány van, tehát az érkezési oldalon megoldott a vonatok várakoztatása, illetve az alagúton történő átjutás után a kilépő vonatok megfelelő irányban való továbbhaladása. Így elvileg csak az alagút foglaltsága miatt kell várni, minden más vonatmozgás elhanyagolható ideig tart, és nem okoz fönnakadást.

A forgalomirányítók feladata megadni, hogy mikor melyik vonat haladjon át az alagúton. Ismerik minden vonat érkezési idejét, illetve tudják, hogy mennyi idő alatt halad át az alagúton. Úgy döntöttek, hogy a vonatok összes várakozási idejét minimalizálják, és ez alapján határozzák meg a vonatok áthaladási sorrendjét. Készítsünk programot, amely megoldja a forgalomirányítást.

A program standard bemenete az adott időszakban érkező vonatok \(\displaystyle N\) száma, majd a következő \(\displaystyle N\) sorban az \(\displaystyle i\)-edik vonat \(\displaystyle t_i\) érkezési és \(\displaystyle h_i\) áthaladási ideje található perc mértékegységben. Az adatok az érkezési idő szerinti sorrendben vannak. A program adja meg a standard kimenet első sorában a legkevesebb összes várakozási időt, majd a második sorában a vonatok áthaladási sorrendjét a sorszámuk fölsorolásával.

Példa (az újsor karaktereket / jelöli):

Korlátok: \(\displaystyle 2 \le N \le 1000\), \(\displaystyle 1\le t_i, h_i \le 10^5\), egész számok.

É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 N\) érték esetén ad helyes eredményt 1 másodpercen belül.

Beküldendő egy is24.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ő 2018. március 12-én LEJÁRT.

A feladatot \(\displaystyle N \le 10\) nagyságú bemenetekre sikerült megoldani.

Mintamegoldásként Horcsin Bálint, 9. osztályos budapesti versenyző munkáját (IS24.cpp), valamint Ürmössy Dorottya, 9. osztályos budapest diák munkáját adjuk közre(Program.cs).

Statisztika:

4 dolgozat érkezett.
10 pontot kapott:	Horcsin Bálint, Kiss Gergely, Ürmössy Dorottya.
9 pontot kapott:	Gáspár Attila.

A KöMaL 2018. februári informatika feladatai