Fișierul intrare/ieșire | bart.in, bart.out | Sursă | ad-hoc |
---|---|---|---|
Autor | clasică | Adăugată de | Cătălin Frâncu • Catalin.Francu |
Timp de execuție pe test | 0.1 sec | Limită de memorie | 4096 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Bart (clasele 9-10)
Bart Simpson a făcut o nouă poznă. Drept pedeapsă, învățătoarea lui l-a pus să scrie pe tablă, de nenumărate ori, un mesaj. Bart l-a scris de câteva ori, apoi s-a plictisit și a fugit pe geam. Prietenul său, Milhouse, intrând în sala de clasă și uitându-se la tablă, s-a întrebat: ce mesaj a avut Bart de scris?
Ajutați-l pe Milhouse să recupereze mesajul original. Dacă există mai multe variante, Milhouse o vrea pe cea mai scurtă. Ultima repetiție a mesajului poate fi incompletă.
Date de intrare
Fișierul de intrare bart.in conține o singură linie, conținând șirul de pe tablă (N litere mari și mici ale alfabetului latin, urmate de \n).
Date de ieșire
În fișierul de ieșire bart.out se va scrie mesajul cu lungime minimă pe care, dacă îl copiem de un număr (nu neapărat întreg) de ori, obținem șirul de pe tablă.
Restricții
- 1 ≤ N ≤ 500.000
Exemplu
bart.in | bart.out |
---|---|
IWillNotWasteChalkIWillNotWasteChalkIWillNotWasteChalkIWillNotW | IWillNotWasteChalk |
abababbabababbabababbabababb | abababb |
xyzxyzxy | xyz |
abacaba | abac |
Explicație
Pentru al doilea exemplu și abababbabababb, repetat de două ori, produce șirul inițial. Este preferat abababb, repetat de patru ori, pentru că este mai scurt.