Fişierul intrare/ieşire:sir9.in, sir9.outSursăLot Alba Iulia 2004
AutorNistor Eugen MotAdăugată defanache99Constantin-Buliga Stefan fanache99
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.insir9.out
8
A
B
B
A
B
A
A
B
13
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?