| Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
AL_03_02 - Najdłuższy spójny podciąg ciągu binarnego |
Najdłuższy spójny podciąg ciągu binarnego
Jaką długość ma najdłuższy spójny podciąg ciągu binarnego zawierający co najwyżej k jedynek?
Wejście
W pierwszym wierszu znajduje się liczba d zestawów testowych (0<d<=5).
Każdy zestaw składa się z dwóch wierszy. W pierwszym wierszu dane są dwie liczby całkowite: n, k (1<n<=500000, k<=10000, k<n), gdzie liczba n oznacza długość ciągu binarnego. W wierszu drugim znajduje się ciąg binarny o długości n.
Wyjście
Na wyjściu należy wypisać d wierszy, w każdym jedna liczba będąca odpowiedzią na pytanie postawione w zadaniu.
Przykład
Wejście
3
10 1
0101000001
12 2
010110101001
15 3
101000011100100
Wyjście
7
6
9
| Dodane przez: | Mariusz Śliwiński |
| Data dodania: | 2012-12-13 |
| Limit czasu wykonania programu: | 1s |
| Limit długości kodu źródłowego | 50000B |
| Limit pamięci: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Języki programowania: | All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14-CLANG COBOL COFFEE D-CLANG D-DMD ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG R RACKET RUST SCM qobi CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |
| Pochodzenie: | ALGOLIGA |