시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 0 | 0 | 0 | 0.000% |
U kvadratnu mrežu prosule su se banane. Na raspolaganju nam je majmun kojeg ćemo poslati da ih pokupi. Majmuna bacimo iz helikoptera na neko polje i usmjerimo u jednom od četiri glavna smjera. On napravi korak unaprijed, skrene udesno i dalje se kreće tako da njegova putanja ima oblik spirale.
Slika prikazuje prvi dio majmunove putanje ako ga na početku usmjerimo prema gore. Uočite da se mreža proteže beskonačno u svim smjerovima.
Odredite najmanji broj koraka potreban da majmun pokupi sve banane, ako ga možemo baciti na proizvoljno polje i usmjeriti ga u bilo kojem od četiri smjera. Majmuna ne smijemo baciti na polje na kojem se nalazi banana da se ne posklizne i razbije.
U prvom redu ulaza nalazi se prirodni broj N (1 ≤ N ≤ 100000), broj banana.
U svakom od sljedećih N redova nalaze se koordinate jedne banane. Koordinate će biti prirodni brojevi manji od 108 (sto milijuna). U svakom polju može se nalaziti najviše jedna banana.
Ispišite jedan prirodni broj, najmanji broj koraka potreban da majmun pokupi sve banane.
3 2 3 3 3 3 2
3
4 7 4 6 4 9 5 8 6
9
4 5 5 5 6 5 7 6 7
5