Fişierul intrare/ieşire:strdup.in, strdup.outSursăRomanian Collegiate Programming Contest 2019
AutorSebastian PirtoacaAdăugată deRCPC2019RCPC2019 RCPC2019
Timp execuţie pe test0.275 secLimită de memorie1536 kbytes
Scorul tăuN/ADificultateN/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 \{(i, j) | 1 <= i <= j <= N\}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
  • 2 ≤ N ≤ 1000
  • Se garanteză că cel puţin un substring este duplicat;
  • Atenţie la limita de memorie!

Exemplu

strdup.instrdup.out
2
00
aaab
2/3
1/2

Explicaţie

Pentru primul test, Mihai poate alege 3 substring-uri nevide identificate de poziţiile: (1, 1) - "0", (1, 2) - "00" şi (2, 2) - "0". Dintre acestea, 2 sunt duplicat - ambele "0". Prin urmare, rezultatul este 2/3.

Pentru al doilea test, Mihai poate alege 10 substring-uri diferite. Dintre acestea, cele duplicate sunt:
* (1, 1) - "a"
* (1, 2) - "aa" pentru că mai apare şi pe (2, 3);
* (2, 2) - "a"
* (2, 3) - "aa"
* (3, 3) - "a"
Probabilitatea ca substring-ul să fie duplicat este 5/10 = 1/2 (fracţia trebuie afişată in formă ireductibilă!).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?