Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | meneaito.in, meneaito.out | Sursă | FMI No Stress 3 |
Autor | Alexandru Cazacu | Adăugată de | Cazacu Alexandru •katakuna |
Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Meneaito
Pentru că a stat prea mult la festivitatea de premiere a concursului No Stress, Mihaiţa a întarziat şi a pierdut inceputul balului. Darnic din fire, el vrea sa-şi imparta premiul castigat, o doza de bere, cu prietena sa. Ajuns in club, Mihăiţa observă câteva lucruri ciudate.
Putem să ne imaginam Barletto ca fiind o matrice patratică de dimensiune NxN, având intrarea pe poziţia (1, 1). Prietena lui Mihăiţa stă la masa artiştilor, pe poziţia (N, N). Pe fiecare coloană i, 2 ≤ i ≤ N-1 se află câte un petrecăreţ care dansează meneaito. Mihăiţa cunoaşte pentru fiecare petrecăreţ de pe linia i, poziţia iniţială în care se află (A[i], i), şi că acesta danseaza doar pe coloana sa, intre poziţiile (A[i], i) şi (B[i], i) în modul urmator : în fiecare secundă se mişcă câte o casuţă, în acelaşi sens până întălneşte unul din capătul spaţiului în care poate să danseze, moment în care îşi schimbă sensul. Mihăiţă poate să arunce bere prietenei sale într-un moment de timp t, dacă nici un petrecăreţ nu se află în acel moment pe una din poziţiile (i, i), 2 ≤ i ≤ N-1. Deoarece Mihăiţă nu este foarte răbdător, el se hotăraşte că dacă nu reuşeşte sa i-o dea prietenei sale in 200 000 de secunde o să bea singur berea si o să plece acasă.
Să se afişeze momentul de timp în care Mihăiţă poate arunca berea, sau -1 in cazul în care Mihăiţă se plictiseşte şi pleacă acasă.
Date de intrare
Fişierul de intrare meneaito.in conţine pe prima linie un număr natural N, dimensiunea clubului Barletto. Pe următoarele două linii se află N-2 numere, reprezentând poziţiile descrise de A, respectiv B.
Date de ieşire
În fişierul de ieşire meneaito.out va conţine un singur număr întreg, timpul minim cerut sau -1.
Restricţii
- 1 ≤ N ≤ 200 000
- 1 ≤ A[i] ≤ B[i] ≤ 200 000
- Mihăiţă intră în club la momentul de timp 0
Exemplu
meneaito.in | meneaito.out |
---|---|
5 2 2 2 3 4 5 | 3 |
Explicaţie
...