Fişierul intrare/ieşire:bart.in, bart.outSursăad-hoc
AutorclasicaAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.1 secLimită de memorie4096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.inbart.out
IWillNotWasteChalkIWillNotWasteChalkIWillNotWasteChalkIWillNotWIWillNotWasteChalk
abababbabababbabababbabababbabababb
xyzxyzxyxyz
abacabaabac

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici