Fişierul intrare/ieşire:nop.in, nop.outSursăAlgoritmiada 2015 Runda Finala
AutorMihai CalanceaAdăugată dea_h1926Heidelbacher Andrei a_h1926
Timp execuţie pe test0.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.innop.out
2
1
2
1 1
1
3 3
111
101
111
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?