Fişierul intrare/ieşire: | decodare.in, decodare.out | Sursă | ad-hoc |
Autor | Cristian Francu, Victor Manz | Adăugată de | |
Timp execuţie pe test | 0.1 sec | Limită de memorie | 10000 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Decodare
Fie trei numere naturale N, K şi D. Considerăm toate şirurile descrescătoare de lungime K formate cu numere din mulţimea {1, 2, ..., N} pentru care diferenţa între oricare doi termeni consecutivi este cel puţin D. Ordonăm aceste şiruri în ordine lexicografică şi codificăm fiecare şir prin numărul lui de ordine, începând cu 1. Dându-se M coduri C1, C2, ..., CM, să se decodifice şi să se tipărească şirurile corespunzătoare.
Date de intrare
Fişierul de intrare decodare.in conţine pe prima linie numerele N, K, D şi M, în această ordine. Pe linia a doua se află cele M coduri, separate prin spaţii.
Date de ieşire
În fişierul de ieşire decodare.out se vor scrie cele M şiruri corespunzătoare, în ordinea dată de codurile de intrare. Fiecare şir va fi scris pe o linie separată, cu elementele separate prin spaţii.
Restricţii
- 1 ≤ K ≤ N ≤ 1.000
- (K - 1) * D < N (se poate întotdeauna genera cel puţin un şir cu proprietăţile date)
- 1 ≤ M ≤ 10
- 1 ≤ Ci ≤ TOTAL, unde 1 ≤ i ≤ M iar TOTAL este numărul total de şiruri cu proprietăţile date
- 1 ≤ Ci ≤ 1015
Exemplu
decodare.in | decodare.out | explicaţie |
---|---|---|
7 3 2 3 1 6 10 | 5 3 1 7 4 1 7 5 3 | Există 10 şiruri cu proprietăţile date, respectiv: 5 3 1 6 3 1 6 4 1 6 4 2 7 3 1 7 4 1 7 4 2 7 5 1 7 5 2 7 5 3 |