Carlos spędza wakacje, badając zduplikowane ciągi binarne. Zduplikowany ciąg binarny to niepusty ciąg $T$ taki, że:
- $T$ zawiera tylko znaki 0 i 1 (czyli $T$ jest ciągiem binarnym).
- $T$ można zapisać w postaci $T = \overline{UU}$, gdzie $U$ jest dowolnym ciągiem binarnym, a operacja $\overline{ab}$ oznacza konkatenację ciągów $a$ i $b$ (czyli zapisanie ich jeden po drugim jako pojedynczy ciąg).
Na przykład, 0000 oraz 011011 są zduplikowanymi ciągami binarnymi, ale 01, 0110 oraz 000 nie są.
Zdefiniujmy siłę ciągu binarnego $S$ jako liczbę różnych spójnych zduplikowanych podciągów obecnych w $S$. Dwa podciągi uważa się za różne, jeśli różnią się co najmniej jednym znakiem.
To zadanie składa się z dwóch części, z których każde podzadanie jest powiązane z Częścią I lub Częścią II. Podzadania można rozwiązywać w dowolnej kolejności; w szczególności nie jest wymagane ukończenie całej Części I przed przystąpieniem do Części II.
Część I
Carlos przesyła Ci ciąg binarny $S$, a Twoim zadaniem jest obliczenie jego siły.
Szczegóły implementacji
Powinieneś zaimplementować następującą procedurę:
int count_duplicated(std::string S)- $S$: ciąg binarny o długości $N$.
- Ta procedura jest wywoływana dokładnie raz dla każdego przypadku testowego.
Procedura powinna zwrócić liczbę całkowitą $K$, będącą liczbą różnych spójnych zduplikowanych podciągów obecnych w $S$.
Ograniczenia
- $4 \leq N \leq 100$
- $S[i]$ jest równe 0 lub 1 dla każdego $i$ takiego, że $0 \leq i < N$.
Podzadania
| Podzadanie | Punkty | Dodatkowe ograniczenia |
|---|---|---|
| 1 | 6 | $N = 4$ |
| 2 | 9 | Brak dodatkowych ograniczeń. |
Przykład
Przykład 1
Rozważ następujące wywołanie:
count_duplicated("0101")Istnieje tylko jeden zduplikowany podciąg binarny w $S$, którym jest 0101. Dlatego procedura powinna zwrócić 1.
Przykład 2
Rozważ następujące wywołanie:
count_duplicated("0000")Istnieją dwa zduplikowane podciągi binarne w $S$: 00 oraz 0000. Stąd procedura powinna zwrócić 2.
Zauważ, że chociaż podciąg 00 występuje w $S$ trzy razy, w ostatecznym wyniku jest liczony tylko raz.
Część II
Carlos zastanawia się, jaka może być minimalna i maksymalna siła ciągu binarnego $S$.
Twoim zadaniem jest skonstruowanie ciągów binarnych o długości 100, które zawierają jak najmniej lub jak najwięcej zduplikowanych podciągów. Otrzymasz punkty w oparciu o liczbę zduplikowanych podciągów.
Podzadania
Ta część składa się z 2 podzadań typu "output-only" z częściową punktacją.
| Podzadanie | Punkty | Ograniczenie |
|---|---|---|
| 3 | 25 | Zminimalizuj siłę $S$. |
| 4 | 60 | Zmaksymalizuj siłę $S$. |
Szczegóły implementacji
Dla każdego podzadania powinieneś:
- przesłać plik wyjściowy składający się z ciągu binarnego o długości 100, lub
- zwrócić ciąg binarny w swoim programie do wywołania procedury sprawdzającej (grader).
Każdy plik wyjściowy musi być w następującym formacie:
S
Aby skonstruować wymagane ciągi binarne w swoim programie rozwiązującym, powinieneś zaimplementować następujące procedury:
std::string find_weakest()- Jeśli w Twoim zgłoszeniu dostarczono plik wyjściowy dla Podzadania 3, ta procedura nie będzie wywoływana.
- W przeciwnym razie procedura jest wywoływana w Podzadaniu 3 dokładnie raz.
Procedura powinna zwrócić ciąg binarny $S$ o długości $N = 100$ o minimalnej sile.
std::string find_strongest()- Jeśli w Twoim zgłoszeniu dostarczono plik wyjściowy dla Podzadania 4, ta procedura nie będzie wywoływana.
- W przeciwnym razie procedura jest wywoływana w Podzadaniu 4 dokładnie raz.
Procedura powinna zwrócić ciąg binarny $S$ o długości $N = 100$ o maksymalnej sile.
Podzadania
Jeśli Twoje wyjście nie jest zgodne z ograniczeniami opisanymi w szczegółach implementacji, wynik Twojego rozwiązania dla tego podzadania wyniesie 0 (zgłoszone jako Output isn't correct w systemie CMS).
Niech $K$ oznacza siłę ciągu w Twoim wyjściu dla danego podzadania.
W Podzadaniu 3 Twój wynik jest obliczany zgodnie z poniższą tabelą:
| Warunek | Punkty |
|---|---|
| $20 < K$ | 0 |
| $4 < K \leq 20$ | $21 - K$ |
| $K = 4$ | 20 |
| $K = 3$ | 25 |
W Podzadaniu 4 Twój wynik jest obliczany zgodnie z poniższą tabelą:
| Warunek | Punkty |
|---|---|
| $K \leq 50$ | 0 |
| $50 < K \leq 80$ | $K - 50$ |
| $80 < K \leq 83$ | $30 + 5 \cdot (K - 80)$ |
| $K = 84$ | 60 |
Przykład
Części I i II używają tego samego przykładowego programu sprawdzającego (grader), przy czym rozróżnienie między dwiema częściami jest określone przez pierwszą linię wejścia.
Wejście 1
1 S
Wyjście 1
K
Wejście 2
2 T
Tutaj $T$ jest albo ciągiem weakest, albo ciągiem strongest.
Wyjście 2
S
Zauważ, że wyjście przykładowego gradera jest zgodne z wymaganym formatem plików wyjściowych w Części II.