Bile14

Time limit: 0.3s Memory limit: 16MB Input: bile14.in Output: bile14.outPoints by default: 10p

Ionuț tocmai a împlinit 14 ani și a primit cadou de ziua lui un set de NN bile de biliard numerotate de la 11 la NN și un aparat de fotografiat. Bilele sunt așezate într-o ordine oarecare.

Fiind pasionat de matematică, el își imaginează un joc alcătuit din KK pași. El vrea ca, la finalul jocului, bilele să fie așezate într-o anumită ordine cerută de fratele său, conform regulilor jocului:

  • La primul pas, Ionuț așază bilele de biliard pe masă într-o ordine oarecare și fotografiază așezarea acestora. El va avea nevoie de fotografia facută pe toată durata jocului.
  • Apoi, parcurge cei K1K - 1 pași rămași. La fiecare pas, toate bilele sunt repoziționate. Astfel, pentru a determina ce bilă trebuie pusă pe o anumită poziție ii, cu 1iN1 \le i \le N, Ionuț caută în fotografie ce bilă se afla pe poziția ii, la începutul jocului. Fie QQ numărul de pe acea bilă. Ionuț va pune acum pe poziția ii bila ce, la pasul anterior, se afla pe poziția QQ.

Cerință

Ionuț își propune să afle care sunt toate modalitățile posibile de așezare inițială a bilelor astfel încât, în urma parcurgerii pașilor jocului, bilele să fie așezate în ordinea dorită de fratele său.

Date de intrare

Pe prima linie a fișierului de intrare bile14.in se vor afla două numere naturale în această ordine:

  • NN - numărul de bile pe care le are Ionuț;
  • KK - numărul de pași pe care îi va avea jocul.

Pe cea a doua linie a fișierului se vor găsi NN numere naturale separate prin câte un spațiu, reprezentând ordinea bilelor cerută de fratele lui Ionuț.

Date de ieșire

Fișierul de ieșire bile14.out va conține mai multe șiruri, fiecare pe câte o linie, afișate în ordine lexicografică.
Fiecare șir va fi alcătuit din NN numere naturale separate prin câte un spațiu.
Fiecare dintre aceste șiruri reprezintă o posibilă așezare inițială a bilelor care, în urma parcurgerii pașilor jocului, va conduce la ordinea dorită de fratele lui Ionuț.

Restricții și precizări

  • N9N \le 9
  • 2K1092 \le K \le 10^9
  • Va exista întotdeauna cel puțin o modalitate de așezare a bilelor ce va conduce la ordinea dorită.
  • Se oferă 10 puncte din oficiu.
# Punctaj Restricții
1 20 2K202 \le K \le 20
2 70 Fără restricții suplimentare

Exemplu

bile14.in

5 3
1 2 3 5 4

bile14.out

1 2 3 5 4
2 3 1 5 4
3 1 2 5 4 

Explicație

Cele trei șiruri obținute reprezintă toate modalitățile posibile de a așeza inițial bilele astfel încât, în urma jocului, să se ajungă la șirul dat de fratele lui Ionuț.

Pentru primele două soluții din exemplul de mai sus, jocul se desfășoară astfel:

Se observă că, pentru cele două soluții explicate, s-a afișat șirul determinat de numerele bilelor pe linia numită Așezarea inițială (După Pasul 1) și s-a ajuns, pe ultima linie, la șirul inițial, aflat în fișierul de intrare.

Log in or sign up to be able to send submissions!