Sim-4-2 | Florinel

This was the problem page during the contest. Access the current page here.
Time limit: 0.3s Memory limit: 256MB Input: Output:

Foarte lung, Florinel Coman... Hai, Florineeeeeel!

Cerință

Paul este un băiat aparte, care tot ce face este să se uite la anime și fotbal. Recent, a observat că a ajuns să cunoască tainele desenelor animate japoneze atât de bine încât în sfârșit acestea pot fi utilizate într-un mod productiv; anume, vrea să își regizeze propriul său anime.

Anime-ul lui Paul vizează calificarea României la Campionatul European de Fotbal din 2024. Ca atare, personajele principale sunt 2n+12n + 1 echipe de fotbal numerotate de la 11 la 2n+12n + 1. Întrucât este la începutul conceperii scenariului și încă nu știe cum se va clasa România la Europene, Paul începe prin a scrie despre etapa grupelor. Toate aceste 2n+12n + 1 echipe de fotbal aparțin aceleiași grupe --- cea din care face parte România, desigur.

Paul a uitat faptul că orice meci de fotbal din fazele de calificare are și un meci de retur aferent; astfel, el va scrie câte un singur episod pentru fiecare pereche de două echipe. Deoarece Paul a uitat că pot să existe remize, fiecare meci din anime se va încheia prin victoria uneia dintre echipe, neexistând opțiunea unei remize. În total, Paul va scrie N(2N+1)N \cdot (2 \cdot N + 1) episoade.

Un anime nu este complet fără un rating, iar Paul își dorește ca anime-ul său să aibă un rating cât mai slab și o poveste cât mai inconsistentă, deoarece, cunoaștem cu toții că cele mai bune anime-uri se află mereu la coada clasamentului. Astfel, inconsistența scenariului este definită ca numărul de triplete de echipe distincte (i,j,k)(i, j, k) pentru care, în scenariul lui Paul, echipa ii va câștiga împotriva echipei jj, echipa jj va câștiga împotriva echipei kk, și echipa kk va câștiga împotriva echipei ii.

Ajutați-l pe Paul să scrie cel mai slab anime posibil, spunându-i cum ar trebui să se termine fiecare episod!

Formal, fie nn un număr natural. Afișați o matrice binară (o matrice ce conține valori de 00 sau 11) cu 2n+12n + 1 rânduri și 2n+12n + 1 coloane, care respectă următoarele proprietăți:

  • A[i][j]A[j][i]A[i][j] \neq A[j][i] pentru oricare iji \neq j;
  • numărul de triplete (i,j,k)(i, j, k) cu ijki \neq j \neq k, pentru care A[i][j]=A[j][k]=A[k][i]=1A[i][j] = A[j][k] = A[k][i] = 1, este maxim.

Date de intrare

Pe prima linie se află un singur numâr întreg nn.

Date de ieșire

Se vor afișa 2n+12n + 1 rânduri. Pe al ii-lea rând se va găsi un șir de caractere de lungime 2n+12n + 1, reprezentând concatenarea valorilor de pe al ii-lea rând din matricea AA.

Restricții și precizări

Pentru toate testele, 1n1 0001 \leq n \leq 1\ 000. Mai apoi, pentru 4242 de puncte, se garanteaza ca n100n \leq 100.

Pentru fiecare test, soluția voastră va fi punctată în funcție de soluția optimă. Fie SoS_{o} numărul maxim de triplete și ScS_{c} numărul de triplete din soluția dată pe un anumit test. Notăm cu x=Sc/Sox = S_{c}/S_{o}. Punctajul obținut pe acel test este:

punctajtestmin(2e2xe2+ex+1×(0.8x400+0.2x),1) \displaystyle punctaj_{test} \cdot min\left(\frac{2e^{2x}}{e^2 + e^{x + 1}} \times ( 0.8 x^{400} + 0.2 x), 1\right)

Exemplu

stdin

1

stdout

001
100
010

Log in or sign up to be able to send submissions!