Nosaukums
Pārmijnieks (parmijas)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
100%

Definīcija

Pilsētas tramvaju depo atrodas ārpus pilsētas un no tā uz pilsētu ved viens sliežu ceļš. Katru rītu noteikts tramvaju skaits no depo izbrauc uz līnijas, bet vakarā atgriežas tajā. Pavisam depo ir 2n tramvaji, kas sanumurēti ar naturāliem skaitļiem no 1 līdz 2n pēc kārtas. Katram tramvajam depo ēkā ir noteikta vieta - tramvajs ar mazāku numuru atrodas ēkā vairāk pa kreisi. Depo shēma pie n=3 ir redzama zīmējumā.

Ar taisnes nogriežņiem ir attēloti sliežu posmi, bet katram no shēmā redzamajiem aplīšiem atbilst vienkārša pārmija, kas katru brīdi var būt ieslēgta vienā no diviem stāvokļiem - "pa kreisi" vai "pa labi" kā redzams zīmējumā.

Pārmijas depo teritorijā ir izkārtotas n līmeņos - pirmajā līmenī ir viena pārmija, otrajā līmenī divas, n-tajā līmenī 2n-1 pārmija. Katra i-tā līmeņa pārmija (1<i<n) savieno vienu i-1-ā līmeņa pārmiju ar divām i+1-ā līmeņa pārmijām. Katra n-tā līmeņa pārmija savieno kādu n-1-ā līmeņa pārmiju ar diviem depo nodalījumiem, bet pirmā līmeņa pārmija savieno divas otrā līmeņa pārmijas ar ceļu uz pilsētu. Lai tramvajs varētu izbraukt uz līnijas, visām pārmijām no depo attiecīgā nodalījuma līdz ceļam uz pilsētu jābūt pārslēgtajām pareizajos stāvokļos. Tā piemēram, lai uz līnijas varētu izbraukt 4.tramvajs, attiecīgajām otrā un trešā līmeņa pārmijām jābūt pārslēgtām pa labi, bet pirmā līmeņa pārmijai - pa kreisi kā redzams zīmējumā.

Katru rītu pirms tramvaju izlaišanas uz līnijas visas pārmijas atrodas stāvoklī "pa kreisi". Pārmiju korekta pārslēgšana ir pārmijnieka Jāņa ziņā. Jānim tiek paziņots, kuri tramvaji no rīta ir jāizlaiž uz līnijas un Jānim ir jāizvēlas to izbraukšanas secība un jānodrošina pārmiju pareiza pārslēgšana. Jānis ir ievērojis, ka kopējais pārmiju pārslēgšanu skaits var būt atkarīgs no tā, kādā secībā tramvaji tiek izlaisti uz līnijas. Tā, piemēram, ja uz līnijas ir jāizlaiž tikai 4. un 5. tramvajs, tad, izlaižot tos tieši šādā secībā, būs nepieciešamas 3 pārslēgšanas, bet pretējā (vispirms 5., tad 4.) - četras pārslēgšanas. Jānis ir sapratis, ka nepieciešams izstrādāt datorprogrammu, kas patvaļīgai n vērtībai un dotiem tramvaju numuriem noteiktu mazāko pārmiju pārslēgšanu skaitu, kas jāveic, lai visi norādītie tramvaji tiktu izlaisti uz līnijas. Uzrakstiet šādu datorprogrammu!


Ievaddatu raksturojums

Ievaddatu pirmajā rindā doti divi naturāli skaitļi n (1≤n≤30) un m (1≤m≤min(2n,3000)), kas atdalīti ar tukšumsimbolu. n ir pārmiju līmeņu skaits, bet m - uz līnijas izlaižamo tramvaju skaits. Katrā no nākošajām m faila rindām dots pa vienam naturālam skaitlim - tramvaja numuram, kas jāizlaiž uz līnijas. Visi dotie tramvaju numuri savā starpā ir atšķirīgi.


Izvaddatu raksturojums

Izvaddatu vienīgajā rindā jāizvada viens vesels nenegatīvs skaitlis - mazākais nepieciešamais pārmiju pārslēgšanu skaits.


Piezīmes

Uzdevums izmantots Latvijas 16.informātikas olimpiādē 2003.gadā.


Paraugdati

Stdin
3 2
5
4
Stdout
3

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