Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | strdup.in, strdup.out | Sursă | Romanian Collegiate Programming Contest 2019 |
Autor | Sebastian Pirtoaca | Adăugată de | RCPC2019 •RCPC2019 |
Timp execuţie pe test | 0.1375 sec | Limită de memorie | 1536 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Siruri duplicat
Mihai are un şir de caractere de lungime N format din litere mici şi mari ale alfabetului Englez şi cifre. Acesta definieşte un substring (e.g. caractere aflate pe poziţii consecutive) ca fiind duplicat, dacă substring-ul apare de cel putin 2 ori in şirul iniţial, la poziţii diferite. Mai mult, Mihai defineşte valoarea unui şir de caractere astfel: probabilitatea ca alegând aleator un substring nevid, acesta să fie duplicat. Să se găsească valoarea unui şir de caractere dat. Rezultatul se va afişa sub forma unei fracţii ireductibile.
Când Mihai alege aleator un substring nevid acesta procedează astfel: alege 2 poziţii (start, end) aleator din mulţimea iar substringul este cel aflat între poziţiile start şi end (considerând indexare de la 1 la N).
Date de intrare
Fişierul de intrare strdup.in conţine pe prima linie numărul de teste T. Pe următoarele T linii se va găsii câte un şir de caractere format din litere mici şi mari + cifre.
Date de ieşire
În fişierul de ieşire strdup.out se vor scrie T fracţii pe câte un rând, sub forma <numărător>/<numitor> (fără alte spaţii suplimentare), reprezentând probabilitatea ca alegând aleator un substring nevid, acesta să fie duplicat.
Restricţii şi precizări
- $ 1 ≤ T ≤ 5 $
- $ 1 ≤ N ≤ 1500 $
- Când Mihai alege aleator un substring nevid acesta procedează astfel:
Exemplu
strdup.in | strdup.out |
---|---|
This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...