- 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.