Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | miculstring.in, miculstring.out | Sursă | Lot Bistrița Seniori 2026, Baraj 3 |
| Autor | Vlad-Mihai Bogdan | Adăugată de |  Bogdan Vlad-Mihai •bogdanvladmihai |
| Timp execuţie pe test | 2 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Micul String
Se numeşte subsecvenţă a unui şir de caractere s un şir de caractere t cu proprietatea că există doi indici i şi j cu 0 ≤ i ≤ j < |s| astfel încât t = sisi+1si+2…sj.
Pentru un tuplu de şiruri de caractere (s0, s1, s2, …, sK-1) vom defini f(s0, s1, s2, …, sK-1) ca fiind şirul minim lexicografic ce se poate obţine prin următorul procedeu:
- Pentru fiecare şir si, se alege o subsecvenţă nevidă ti a sa;
- Se concatenează t0, t1, t2, …, tK-1, şirul obţinut fiind rezultatul procedeului.
Un şir de caractere a0a1…an-1 este mai mic lexicografic decât un alt şir de caractere b0b1…bm-1 dacă şi numai dacă:
- Există un indice i 0 ≤ i < min(n, m) pentru care a0a1…ai-1 = b0b1…bi-1 şi ai < bi; sau
- n < m şi a0a1…an-1 = b0b1…bn-1.
Cerinţă
Se dau un număr natural N, un şir de caractere de lungime N, notat w, un număr natural K şi un şir de K numere naturale nenule l0, l1, l2, …, lK-1. Să se numere câte tupluri de K şiruri de caractere, (s0, s1, s2, …, sK-1), respectă următoarele condiţii:
- Toate şirurile conţin doar litere mici ale alfabetului englez;
- |si| = li, ∀ 1 ≤ i ≤ K;
- f(s0, s1, s2, …, sK-1) = w.
Deoarece acest număr poate fi mare, se cere restul acestuia la împărţirea prin 998\ 244\ 353.
Detalii de implementare
Concurenţii vor avea de implementat o singură funcţie:
int solve(int N, int K, std::string w, std::vector<int> l);care primeşte ca parametri:
- N, numărul de caractere din şirul w;
- K, numărul de şiruri dintr-un tuplu;
- Şirul w (indexat de la 0);
- l, reprezentând lungimile şirurilor (indexat de la 0).
Funcţia solve va fi apelată o singură dată.
Restricţii
- 1 ≤ K ≤ N ≤ 200
- 1 ≤ li ≤ 200, 0 ≤ i ≤ N - 1
- Şirul w este format doar din litere mici ale alfabetului englez.
- Vom considera wi al i-lea caracter din şirul w.
| # | Punctaj | Restricţii |
|---|---|---|
| 1 | 7 | 1 ≤ K ≤ N ≤ 7, ∑i=0{K-1} li ≤ 8 şi w conţine doar caracterele a, b, c, d |
| 2 | 8 | 1 ≤ K ≤ N ≤ 25 şi li = 3, ∀ 0 ≤ i < N |
| 3 | 11 | K = 2 |
| 4 | 14 | 1 ≤ K ≤ N ≤ 120, 1 ≤ li ≤ 120 şi wi ≤ wi+1, ∀ 0 ≤ i < N - 1 (şirul w este crescător) |
| 5 | 23 | 1 ≤ K ≤ N ≤ 90 şi 1 ≤ li ≤ 90, ∀ 0 ≤ i < N |
| 6 | 21 | 1 ≤ K ≤ N ≤ 150 şi 1 ≤ li ≤ 150, ∀ 0 ≤ i < N |
| 7 | 16 | Fără restricţii suplimentare |
Exemple
| Fişier de intrare | Fişier de ieşire |
|---|---|
| 4 3 babz 1 2 1 | 1 |
| 4 3 babz 1 3 1 | 26 |
| 6 4 abcbzz 3 3 3 3 | 1849 |
Explicaţii
Pentru primul exemplu, singurul tuplu valid este ("b", "ab", "z").
