z-rings
Za 8. rođendan, mali Z je od tata Duleta dobio mapu na kojoj je označeno gde se krije gusarsko blago. Kada je napunio 18 godina, Z se otisnuo u svet, i spletom neverovatnih okolnosti uspeo da pronađe pećinu sa blagom.
Kada je ušao unutra, imao je šta da vidi. Gomilu zlatnog prstenja rasutog po podu pećine. Prstenovi su svi iste širine, ali različite debljine (medju prstenjem može biti i jednakih). Ali da bi se nešto blaga ostavilo i za neke buduće avanturiste, tu je bila i poruku da kada bude napuštao pećinu, sa sobom može izneti samo jedan prsten i da će ljuta guja na izlazu iz pećine proveriti koliko je prstenova mali Z poneo sa sobom. Tražeći najveći prsten, mali Z je primetio da su oni perfektno izradjeni, i da ako se lepo uklope jedan u drugi (kada je spoljašnji poluprecnik jednog jednak unutrašnjem poluprečniku drugog), tada oni deluju kao jedan, i da ljuta guja sa svojom dioptrijom +5 to ne može primetiti.
Znajući da je cena jednog prstena srazmerna njegovoj debljini, mali Z je odlučio da sačini prsten najveće moguće debljine, od onog prstenja iz pećine.
U redovima od 2 do N+1, nalaze se po dva cela broja Ri_u i Ri_s , koji predstavljaju unutrašnji i spoljašnji poluprečnik i-tog prstena. (0 < Ri_u < Ri_s <= 2000000000).
10
1 3
1 5
2 3
3 9
5 6
7 10
7 11
6 8
2 3
10 11Izlaz:
8Objašnjenje: sem pojedinačne debljine prstenova, mali Z može da sastavi
kombinovanjem 1-3 sa 3-9 (1-9);
kombinovanjem 2-3 sa 3-9 (2-9);
kombinovanjem 1-5 sa 5-6 i sa 6-8 (1-8);
kombinovanjem 7-10 sa 10-11 (7-11);
Od svih njih najdeblji daje prva kombinacija, koja ima debljinu 9-1=8.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.