Pagini recente » Rezultatele filtrării | Rezultatele filtrării | Rezultatele filtrării | Rezultatele filtrării | Diferente pentru problema/strdup intre reviziile 6 si 18
Diferente intre titluri:
Diferente intre continut:
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 <tex>\{(i, j) | 1 <= i <= j <= N\}</tex>iar substringul este cel aflat între poziţiile *start* şi *end* (considerând indexare de la *1* la *N*).
Precizare: Când Mihai alege aleator un substring nevid acesta procedează astfel: alege 2 poziţii (start, end) aleator din mulţimea <tex>\{(i, j) | 1 <= i <= j <= N\}</tex>iar substringul ales este cel aflat între poziţiile *start* şi *end* (considerând indexare de la *1* la *N*).
h2. Date de intrare
h2. Restricţii şi precizări
* $ 1 ≤ T ≤ 5 $
* $ 1 ≤ N ≤ 1500 $
* Când Mihai alege aleator un substring nevid acesta procedează astfel:
* $1 ≤ T ≤ 5$
* $2 ≤ N ≤ 1000$
* Se garanteză că cel puţin un substring este duplicat;
* Atenţie la limita de memorie!
h2. Exemplu
table(example). |_. strdup.in |_. strdup.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
00
aaab
| 2/3
1/2
|
h3. 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ă!).
== include(page="template/taskfooter" task_id="strdup") ==
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.