repeat

Enunț

Fie $s$ un şir binar (format doar din caracterele 0 şi 1). Se numeşte subsecvenţă a şirului $s$ o succesiune de caractere situate în $s$ pe poziţii consecutive. De exemplu, 101 este o subsecvenţă a şirului 11011. Dacă $x$ este o subsecvenţă a şirului $s$, iar cu $xx$ notăm concatenarea şirului $x$ cu el însuşi, $xx$ se numeşte subsecvenţă repetată în $s$ dacă $xx$ este subsecvenţă a lui $s$. De exemplu 101 este o subsecvenţă repetată a şirului 11011011.

Pentru un şir specificat $s$ putem determina numărul de subsecvenţe repetate distincte. De exemplu, şirul 101110110101 conţine următoarele $6$ subsecvenţe repetate distincte: 10111011, 1010, 0101, 11, 110110, 101101.

Cerință

Dat fiind un număr natural $N$, să se determine un şir binar de lungime $N$ care conţine un număr minim de secvenţe repetate distincte.

Date de intrare

Programul vostru nu va citi date din niciun fişier.

Date de ieșire

Pe fiecare linie a fişierului de ieșire se va afla un şir binar de lungime specificată în tabelul următor, conţinând un număr minim de subsecvenţe repetate sau valoarea $2$ (dacă nu aţi determinat o soluţie pentru valoarea $N$ corespunzătoare liniei).

Punctaj

• Dacă şirul afişat de concurent pe linia $i$ nu este valid (nu este binar sau nu are lungimea specificată) concurentul obţine $0$ puncte pentru acel test.
• În caz contrar, programul de evaluare va determina mai întâi numărul de secvenţe repetate distincte existente în fiecare şir binar valid existent în fişierul de ieşire.
• Pentru fiecare dintre lungimile specificate se va determina numărul minim de subsecvenţe repetate pentru şirurile afişate de concurenţi.
• Să notăm cu $min_i$ numărul minim de subsecvenţe repetate pentru un şir de lungimea corespunzătoare liniei $i$, minim determinat pe toate soluţiile concurenţilor.
• Să notăm cu $nr_i$ numărul de subsecvenţe repetate din şirul afişat de concurent pentru linia $i$.
• Punctajul obţinut de concurent pentru testul de pe linia $i$ este: $\displaystyle 10 \times \left( \frac{min_i}{nr_i} \right)^3$. Punctajul total va fi trunchiat la o zecimală.