- Nosaukums
- Kāršu jaukšana (kartis)
- Laika limits
- 1.00s
- Atmiņas limits
- 256.0 MB
- Grūtība
-
60%
Definīcija
Alisei un Robertam ir kāršu kava ar N kārtīm, kuras numurētas ar naturāliem skaitļiem no 1 līdz N tā, ka nav divu kāršu ar vienādiem numuriem. N ir nepāra skaitlis. Bez tam Aliksei un Robertam ir arī kāršu kavas jaukšanas mašīna.
Kāršu kavas jaukšanas mašīna var sajaukt jebkuru kāršu kavu (kārtis tajā var būt patvaļīgā secībā), veicot dubultās sajaukšanas operāciju: visām pozīcijām i, 1<=i<=N, ja kārts i-tajā pozīcijā ir j un kārts j-tajā pozīcijā ir k, tad pēc kavas sajaukšanas i-tajā pozīcijā būs kārts k.
Alise un Roberts spēlē spēli. Alise vispirms uzraksta visus skaitļus no 1 līdz N patvaļīgā secībā a1,a2,....,aN. Tad viņa saliek kārtis tā, ka ai-tajā pozīcijā ir kārts ar numuru ai+1 visiem i:1<=i<=N-1, bet aN-tajā pozīcijā ir kārts ar numuru a1.
Tādējādi, kārtis ir saliktas secībā x1,x2,....,xN, kur xi ir kārts i-tajā pozīcijā.
Pēc tam Alise pēc kārtas veic S dubultās sajaukšanas operācijas lietojot augstāk aprakstīto kāršu kavas jaukšanas mašīnu. Jaukšanas rezultātā kārtis kavā ir secībā p1,p2,....,pN. Šo kavu Alise iedod Robertam un pasaka viņam arī skaitli S. Roberta uzdevums ir noteikt kāršu secību x1,x2,....,xN kādā Alise bija kārtis salikusi sākumā pirms jaukšanas mašīnas izmantošanas.
Ievaddatu raksturojums
Ievaddatu pirmā rinda satur divus naturālu skaitļu N(1<=N<=1000) un S(1<=S<=1000) vērtības, kas atdalītas ar tukšumsimbolu.
Nākošajās N faila rindas apraksta kāršu kārtību kavā pēc jaukšanas mašīnas izmantošanas. Faila i+1-ajā rindā ir dota skaitļa pi (skaitļa, kas atrodas i-tajā vietā pēc visām dubultās jaukšanas operācijām) vērtība.
Izvaddatu raksturojums
Izvaddatiem jāsatur tieši N rindas un jāapraksta kāršu secība kavā pirms Alise izmantoja jaukšanas mašīnu.
Katram i, 1<=i<=N faila i-tajā rindā jābūt skaitļa xi (skaitļa, kas atrodas i-tajā vietā pirms visām dubultās jaukšanas operācijām) vērtībai.
Piezīmes
Uzdevums izmantots Centrāleiropas valstu informātikas olimpiādē 1998.gadā.
Paraugdati
Stdin
7 4 6 3 1 2 4 7 5
Stdout
4 7 5 6 1 2 3
Stdin
5 2 4 1 5 3 2
Stdout
2 5 4 1 3
Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.