Fişierul intrare/ieşire: | bilete.in, bilete.out | Sursă | Lista lui Francu |
Autor | Catalin Francu | Adăugată de | |
Timp execuţie pe test | 0.025 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Bilete
Intr-o mare metropola a unei tari din SE Europei inca se circula fara sa se plateasca biletele... Biletele de autobuz din orasul respectiv au o grila de N x N patratele, dintre care aparatele de taxat composteaza exact K patratele. Biletul poate fi introdus in aparat numai cu un capat (celalalt capat fiind prins in cotor), dar poate fi introdus fie pe fata, fie pe dos. In acest fel, unele din configuratiile posibile de K gauri in grila de N x N sunt oglindiri stanga - dreapta ale altor configuratii. Pentru N = 3 si K = 2, biletele de mai jos sunt oglindiri unul pentru celalalt (patratelele negre se considera compostate):
Un blatist inveterat face colectie de bilete perforate si doreste sa catalogheze toate configuratiile posibile de gauri, ignorand insa oglindirile (pentru ca teoretic reprezinta aceeasi configuratie). In acest scop, el codifica fiecare configuratie printr-un sir de forma l1c1l2c2...lkck, unde (li, ci) sunt coordonatele gaurii a i-a relativ la coltul din stanga-sus al biletului. Gaurile sunt deci enumerate de la stanga la dreapta si de sus in jos. Daca blatistul intalneste doua configuratii care sunt una oglindirea celeilalte, dintre cele doua el va clasifica numai pe cea care este minim lexicografica. De exemplu, dintre cele doua bilete de mai sus, el il va pastra pe cel cu codul 1123, pentru ca, alfabetic, este mai mic.
Cerinta
Sa se tipareasca in ordine lexicografica (alfabetica) codurile biletelor pe care le catalogheaza blatistul.
Date de Intrare
Pe prima linie a fisierului de intrare bilete.in se vor afla doua numere naturale N si K, dimensiunea unui bilet, respectiv numarul de gauri pe care le poate da compostorul din orice autobuz al metropolei. Cele doua numere sunt despartite de exact un spatiu.
Date de Iesire
Fisierul de iesire bilete.out va contine toate configuratiile posibile care sunt pastrate de catre blatist, ordonate alfabetic.
Restrictii
- 1 ≤ N ≤ 9
- 1 ≤ K ≤ 3
- Orice tentativa de a nu plati bilet se sanctioneaza cu amenda
Exemplu
bilete.in | bilete.out |
---|---|
3 2 | 1112 1113 1121 1122 1123 1131 1132 1133 1221 1222 1231 1232 2122 2123 2131 2132 2133 2231 2232 3132 3133 |