Zoznam úloh

2. Odkiaľ vyraziť

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

Úloha

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

Formát vstupu

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.

Formát výstupu

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.

Príklad

Vstup

4
3 5
15 1
2 1
7 20

Výstup

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.

Vstup

6
1 10
11 20
30 5
2 6
5 5
1 4

Výstup

3
Pre odovzdávanie sa musíš prihlásiť.
Trojsten

Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.

Kontakt
Ďalšie projekty