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. 93. feladat (2014. november)

S. 93. Adott \(\displaystyle N\le 100\; 000\) sportoló, akik egy tréningen vesznek részt. Mindenkinek körbe kell bicikliznie egy tavat, majd rögtön utána át kell rajta evezni (oda-vissza), ebben a sorrendben. Sajnos az egyesület nem túl gazdag, ezért mindössze egyetlen bicikli, és egyetlen csónak áll rendelkezésükre. Így egyszerre legfeljebb egy ember biciklizhet, és egy evezhet. Tudják minden sportolóról, hogy hány órába telik körbebiciklizni, és hány órába telik átevezni a tavat. Szeretnék a tréninget mihamarabb befejezni, kérdés, hogy ez hány órát vesz összesen igénybe.

A program olvassa be a standard input első sorából \(\displaystyle N\)-et, majd a következő \(\displaystyle N\) sorból a \(\displaystyle b_i\), \(\displaystyle e_i\) szóközzel elválasztott óraszámokat, melyek a biciklizési, illetve evezési időt jelentik. Írja a standard output első és egyetlen sorába a minimális óraszámot, amennyi idő alatt teljesíthető mindenkinek a tréning.

Magyarázat: a helyes sorrend: 3, 1, 2.

Pontozás és korlátok: A programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 1 pontot ér. A programra akkor kapható meg a további 9 pont, ha bármilyen hibátlan bemenetet képes megoldani az 1 mp futásidőkorláton belül.

Beküldendő egy tömörített s93.zip állományban a program forráskódja (s93.pas, s93.cpp, ...) az .exe és más, a fordító által generált állományok nélkül, valamint a program rövid dokumentációja (s93.txt, s93.pdf, ...), amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.

(10 pont)

A beküldési határidő 2014. december 10-én LEJÁRT.


A megoldás igencsak egyszerű, ám nem könnyű rájönni. Rendezzük sorba a sportolókat: először jöjjenek azok, akik szigorúan gyorsabban eveznek, mint bicikliznek, evezési idő szerint növekvő sorrendben. Utána a maradék biciklizési idő szerint csökkenő sorrendben. Erről még be is kell bizonyítani, hogy tényleg ez a helyes sorrend. Ezt pedig úgy tehetjük meg, ha kiszámoljuk, hogy ha felcserélünk sportolókat, akkor valóban több idő alatt készülnek el.


Statisztika:

14 dolgozat érkezett.
10 pontot kapott:Alexy Marcell.
9 pontot kapott:Fuisz Gábor.
7 pontot kapott:1 versenyző.
3 pontot kapott:4 versenyző.
2 pontot kapott:3 versenyző.
1 pontot kapott:4 versenyző.

A KöMaL 2014. novemberi informatika feladatai