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.
Precizare: Când Mihai alege aleator un substring nevid acesta procedează astfel: alege 2 poziţii (start, end) aleator din mulţimea 
iar substringul ales 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
- Se garanteză că cel puţin un substring este duplicat
Exemplu
| strdup.in | strdup.out |
|---|---|
| 3 A 010 aaab | 0/1 |
Explicaţie
Pentru primul test, Mihai poate alege un singur substring nevid "A" dar acesta nu este duplicat. Prin urmare, probabilitatea este 0 si se afi
