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 tuturor matricelor pe care le afisati trebuie să fie maxim 1600.
• 1 ≤ T ≤ 500
• 1 ≤ C_i ≤ 66.666.666
• Pentru teste in valoare de 10 puncte, C_i ≤ 800
• Pentru teste in valoare de 30 de puncte, C_i ≤ 50.000
• Pentru teste in valoare de 50 de puncte, C_i ≤ 1.000.000

Exemplu

Cum se trimit solutii?