Codah ClubTrain. Submit. Improve.
Sign in
English
#0000C0

z-rings

Kicsi Z nyolcadik születésnapjára kapott egy titkos térképet, melyen fel van tüntetve, hova rejtették el a kalózok a kincset. Mikor betöltötte 18. életévét, kicsi Z felkerekedet és számos izgalmas kaland után megtalálta a kincsesbarlangot.


Amikor belépett, elállt szeme-szája! A barlang padlóját szinte belepte a sok-sok aranygyűrű, a kalózok kincse. A gyűrűk - fekvő helyzetbe hozva - mind egyforma magasak voltak, de falvastagságuk különböző is lehetett. A barlangban egy szigorú utasitást talált, mely szerint aki a barlangból kilép, az csak egy gyűrűt vihet magával, s ezt kilépéskor egy könyörtelen marcona kalóz szigorúan fogja ellenőrizni. Kicsi Z el is kezdte keresni a legnagyobb gyűrűt és az alapos vizsgálódás során felfigyelt arra, hogy ha egy gyűrű külső átmérője megegyezik egy másik belső átmérőjével, akkor a kisebbik tökéletesen belesimitható a belsőbe és a két gyűrű végül is egynek tűnik olyannyira, hogy a turpisságot még a kijáratnál őrködő kalóz sem veszi észre!


Mivel a gyűrű értéke arányos vastagságával, kézenfekvő, hogy célszerű a gyűrűket a lehetőség szerint szorosan egybeillesztve a lehető legvastagabb gyűrűt összeállitani. Persze az sem kizárt, hogy valamely gyűrű már maga vastagabb mint azok, melyeket esetleg egymásbacsúsztatással létre lehet hozni...


InputA standard bemenő egység első sorában áll az N szám, amely megadja, hány gyűrű van a barlangban (1 <= N <= 100000).
A 2-tól az N+1-dik sorig minden sorban két-két szám van Ri_b és Ri_k , melyek rendre az i-dik gyűrű belső illetve külső sugara. (0 < Ri_u < Ri_s <= 2000000000). Az összeillesztés tehát a kisebb gyűrű külső sugarának és a nagyobb gyűrű belső sugarának enyenlőségén múlik.

OutputA standard kimenő egység egyetlen sorába ki kell irni azt az egész számot, amely az adott gyűrűkből összeállitható legvastagabb gyűrű falvastagságát adja.

Bemenet:
10
1 3
1 5
2 3
3 9
5 6
7 10
7 11
6 8
2 3
10 11
Kimenet:
8
Magyarázat: Az adott gyűrűk saját vastagságai mellett kicsi Z még a következőket tudja összeállitani:
Összekombinálható 1-3 a 3-9 -el (1-9);
Összekombinálható 2-3 a 3-9 -el (2-9);
Összekombinálható 1-5 az 5-6 -tal és a 6-8 -cal (1-8);
Összekombinálható 7-10 a 10-11 -el (7-11);
Mindezek közül a legvastagabb az első kombináció, melynek falvastagsága 9-1=8.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.