Pentru a îmbunătăţi aptitudinile logico-matematice ale elevilor săi, profesorul Vasile a implementat un joc.
Pe ecranul principal al jocului se afişează un şir de scaune, numerotate de la stânga spre dreapta începând cu , pe fiecare scaun fiind așezat câte un copil. Fiecare copil poartă un tricou pe care este scris, de asemenea, câte un număr de la la . Numerele de pe tricouri sunt distincte și sunt scrise pe spate, deci nu sunt vizibile.
Scopul jocului este de a descoperi numărul scris pe tricoul fiecărui copil. Pentru aceasta, pe ecran mai este afişat un triunghi de numere , care ne dă informaţii ajutătoare. Triunghiul arată ca o matrice în care liniile sunt numerotate de sus în jos de la la , iar coloanele de la stânga la dreapta de la 1 la . Numărul scris în triunghi pe linia şi coloana () reprezintă numărul scaunului pe care stă copilul având cel mai mic număr pe tricou dintre toţi copiii situaţi pe scaune cu numere cuprinse între şi (inclusiv şi ). Observaţi că poziţiile din triunghi de pe linia şi coloana cu nu sunt completate.
Numim soluţie o succesiune de numere naturale distincte cuprinse între 1 şi care ar putea fi scrise, în ordine, de la stânga la dreapta, pe tricourile celor copii, astfel încât informaţiile din triunghiul de numere să fie corecte.
Două soluţii sunt considerate distincte dacă există cel puţin un copil pentru care numărul scris pe tricoul său în cele două soluţii diferă.
Cerință
Cunoscând numărul de copii şi triunghiul de numere:
- determinați o soluţie posibilă; dacă există mai multe soluţii posibile se va afişa cea mai mică din punctul de vedere lexicografic;
- determinați numărul de soluţii posibile.
Date de intrare
Fişierul de intrare joc.in
conţine pe prima linie numărul natural reprezentând cerinţa care trebuie să fie rezolvată ( sau ). Pe linia a doua se află numărul natural cu semnificația din enunț. Pe următoarele linii se află numerele din triunghi. Pe linia dintre cele sunt scrise numere separate prin câte un spaţiu, reprezentând numerele de pe linia din triunghi, situate pe coloanele , .
Date de ieșire
Fişierul de ieşire joc.out
conţine o singură linie.
Dacă linia conţine numere naturale distincte cuprinse între 1 şi , separate prin câte un spaţiu, reprezentând soluţia cea mai mică din punct de vedere lexicografic determinată pentru cerința 1.
Dacă linia conţine numărul de soluţii posibile determinat pentru cerința 2.
Restricții și precizări
- Spunem că șirul , , este mai mic din punctul de vedere lexicografic decât șirul , , dacă există (), astfel încât , pentru orice şi .
- Se garantează că, pentru datele de test, există cel puțin o soluție.
# | Scor | Restricții |
---|---|---|
1 | 9 | , |
2 | 9 | , |
3 | 22 | , |
4 | 24 | , |
5 | 36 | , fără restricții suplimentare |
Exemplul 1
joc.in
1
3
1 2 2
2 2
3
joc.out
2 1 3
Explicație
O soluţie posibilă este .
- Pe secvenţa de scaune copilul cu număr minim pe tricou este pe scaunul .
- Pe secvenţa de scaune copilul cu număr minim pe tricou este pe scaunul .
- Pe secvenţa de scaune copilul cu număr minim pe tricou este pe scaunul .
- Pe secvenţa de scaune copilul cu număr minim pe tricou este pe scaunul .
- Pe secvenţa de scaune copilul cu număr minim pe tricou este pe scaunul .
- Pe secvenţa de scaune copilul cu număr minim pe tricou este pe scaunul .
O altă soluţie posibilă este , dar este mai mică din punct de vedere lexicografic.
Exemplul 2
joc.in
2
3
1 2 2
2 2
3
joc.out
2