| Fişierul intrare/ieşire: | sir9.in, sir9.out | Sursă | Lot Alba Iulia 2004 |
| Autor | Nistor Eugen Mot | Adăugată de |  Constantin-Buliga Stefan •fanache99 |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Sir9
Se consideră un şir c 1 c 2 ...c n format din n caractere din mulţimea {A, B}.
Concatenăm şirul cu el însuşi şi obţinem un şir de lungime 2n.
Pentru un indice k ( 1≤k≤2n ) considerăm subsecvenţele de lungime cel mult n, care se termină pe poziţia k, iar dintre acestea fie s (k) subsecvenţa cea mai mică în ordine lexicografică.
Determinaţi indicele k pentru care s (k) are lungimea cea mai mare.
Date de intrare
Pe prima linie a fişierului de intrare sir9.in se găseşte numărul natural n, reprezentând lungimea şirului. Pe următoarele n linii se află în ordine caracterele şirului (câte un caracter pe o linie).
Date de ieşire
Prima linie a fişierului de ieşire va conţine numărul natural k. În caz că există mai multe valori pentru k se va alege cea mai mică.
Restricţii
- 1 ≤ n ≤ 30 000
Exemplu
| sir9.in | sir9.out |
|---|---|
| 8 A B B A B A A B | 13 |
