Nové počítače sú drahé. Našťastie môžeme Kupovať Staré Počítače, a tak ušetriť veľa peňazí. Tie sa vždy zídu na ďalšie počítače. Ralbo listuje stránkami svojho obľúbeného bazárového portálu a značí si výhodné ponuky.
Dotykový displej, dotyk nefunguje… cena 30€… ako zadarmo, displej opravím aj keby nechcem… intel i5, ôsma generácia, windows 11… úbohé stvorenie, to je snáď týranie starých procesorov…
Po hodinách strávených vyberaním kandidátov na vzkriesenie najlepším operačným systémom sa Ralbo konečne dostáva k plánovaniu cesty. Už už hádže adresy do máp, keď si na stránke všimne neznáme tlačítko.
Bazár má novú experimentálnu funkciu. Tak toto je isto navibekódené, pomyslí si. Pre zadané inzeráty vám poskyne palivo, ktoré presne vystačí na navštívenie všetkých miest a návrat do prvého. Má to ale malý háčik, nie z každého mesta vystačí benzín v nádrži do ďalšieho. Kupujúci si musí rozumne vybrať, kde chce svoju cestu začať. Taktiež vaše auto má trošku väčšiu spotrebu ako zvyčajné autá.
Dostanete zoznam staníc, ktoré sú v jednom kruhu. Pre každú stanicu číslo $c$ a $d$, kapacitu danej stanice - koľko litrov v nej vieme natankovať paliva a vzdialenosť od nasledujúcej stanice v km. Zoznam staníc tvorí uzavretý okruh (z $n$-tej stanice sa ide opäť do 1. stanice). Naše auto má spotrebu 1 l/km. Súčet palív a vzdialeností je rovnaký. Vašou úlohou je určiť, v ktorej stanici musíme začať, aby sme okruh prešli celý. Začíname s prázdnou nádržou. Kapacita nádrže nie je obmedzená.
V prvom riadku vstupu je číslo $n$ ($1 \leq n \leq 10^9$) udávajúce počet staníc.
Nasledujúcich $n$ riadkov obsahuje dvojicu čísel $c$ a $d$ oddelených medzerou.
| Sada | 1 | 2 |
|---|---|---|
| $1 \leq n \leq$ | $10^3$ | $10^8$ |
| $1 \leq s \leq$ | $10^9$ | $10^{12}$ |
Kde $s$ je súčet paliva = súčet vzdialeností.
Poznámka: Pri programovaní v C++ sa súčet paliva v druhej sade nemusí zmestiť do 32-bitového intu.
Vypíšte jedno číslo, udávajúce poradové číslo stanice, v ktorej musíme začať. Stanice sú číslované od 1 v poradí zo vstupu.
4
3 5
15 1
2 1
7 20
2
Ak začneme na druhej stanici, natankujeme si 15 litrov benzínu. To nám vystačí až po 4. stanicu, pričom po ceste môžeme postupne dotankovávať palivo, vďaka čomu vieme prejsť až do 1. stanice. Keď tam natankujeme zvyšné 3 litre paliva, v nádrži nám zostane presne 5 litrov, čo nám stačí na návrat do 2. stanice, kde sme začínali.
6
1 10
11 20
30 5
2 6
5 5
1 4
3
Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Programátorská súťaž pre základoškolákov
Materiály a úlohy na výučbu programovania
Intenzívny programátorský zážitok v lete