Nosaukums
Seifa atvēršana (safe)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
50%

Definīcija

Seifa atslēgas mehānisms sastāv no N vienādiem diskiem, kas sadalīti 10000000 vienādos sektoros, kuri sanumurēti ar naturāliem skaitļiem no 1 līdz 10000000 pēc kārtas pulksteņrādītāja virzienā.

Diski ir izvietoti uz kopīgas ass viens virs otra. Sākumā visi diski ir pagriezti tā, ka sektori ar vienādiem numuriem atrodas tieši viens virs otra.

Katram diskam viens sektors ir izgriezts, kuru sauc par caurumu. Lai seifu atvērtu, diski ir jāpagriež tā, lai visi caurumi atrastos viens virs otra.

Katru disku vienā sekundē var pagriezt par vienu sektoru vienā virzienā (pulksteņa vai pretēji pulksteņa rādītāja virzienam).

Uzrakstiet programmu, kas nosaka mazāko laiku, kāds nepieciešams seifa atvēršanai!

 


Ievaddatu raksturojums

Teksta faila safe.in pirmajā rindā dota naturāla skaitļa N(disku skaits, 2 ≤N≤100000) vērtība.

Katrā no nākošajām N rindām dots pa vienam naturālam skaitlim - tā sektora, kurš ir caurums, numuram.

Faila i+1-ajā rindā ir skaitlis Pi, 1≤Pi ≤1000000, ja i-tajā diskā caurums ir sektorā Pi.

 


Izvaddatu raksturojums

Teksta faila safe.out vienīgajā rindā jāizvada seifa atvēršanai mazākais nepieciešamais laiks sekundēs.

Piezīme: Pievērsiet uzmanību šī skaitļa iespējamajai vērtībai!

 


Piezīmes

Uzdevums izmantots Horvātijas informātikas olimpiādē 2002.gadā


Paraugdati

Stdin
4
9999999
7
16
9999995
Stdout
29

Stdin
3
5
17
7
Stdout
12

Stdin
4
1
2500001
5000000
7500002
Stdout
9999998

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.