| Fişierul intrare/ieşire: | nop.in, nop.out | Sursă | Algoritmiada 2015 Runda Finala |
| Autor | Mihai Calancea | Adăugată de |  Heidelbacher Andrei •a_h1926 |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
NumberOfPaths
Fie A o matrice binară cu N linii şi M coloane. Se numeşte drum "dreapta-jos" orice succesiune de celule (x0, y0), (x1, y1) ... (x(k - 1), y(k - 1)) cu proprietatea că oricare ar fi 1 ≤ i ≤ k - 1, x(i) = x(i - 1) + 1 şi y(i) = y(i - 1) sau x(i) = x(i - 1) si y(i) = y(i - 1) + 1. Câte drumuri "dreapta-jos" există care încep în colţul din stânga sus, se termină în colţul dreapta jos şi conţin doar celule de tip 1?
Glumim. Această problemă este mult prea cunoscută. Atât de cunoscută încât de-a lungul istoriei Comisiile au dezvoltat o precizie remarcabilă în alcătuirea testelor de acest tip. Mai exact, dându-se un număr natural C, Comisia poate să producă o matrice de dimensiuni rezonabile pentru care răspunsul la întrebarea de mai sus este exact C. Spoiler alert, asta trebuie să faceţi şi voi!
Date de intrare
Fişierul de intrare nop.in va conţine numărul de teste T. Urmează T linii, fiecare conţinând câte un număr natural C, numărul de drumuri necesare pentru testul respectiv.
Date de ieşire
În fişierul de ieşire nop.out se vor afla matricele soluţie pentru fiecare din cele T teste. Pentru fiecare test se vor afişa numărul de linii N şi numărul de coloane M ale matricei. Vor urma N linii de câte M caractere, fără spaţii, fiecare de tip 0 sau 1.
Restricţii
- Numărul de celule (N x M) al fiecarei matrice pe care o afisati trebuie să fie maxim 1600.
- 1 ≤ T ≤ 500
- 1 ≤ Ci ≤ 66.666.666
- Pentru teste in valoare de 10 puncte, Ci ≤ 800
- Pentru teste in valoare de 30 de puncte, Ci ≤ 50.000
- Pentru teste in valoare de 50 de puncte, Ci ≤ 1.000.000
Exemplu
| nop.in | nop.out |
|---|---|
| 2 1 2 | 1 1 1 3 3 111 101 111 |
