Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
MWP5_2C - Przemytnicy |
Na granicy polsko-ukraińskiej rozwinął się na szeroką skalę nowy niepokojący proceder - przemyt liczb. Każdy z przemytników może jednorazowo zabrać ze sobą tylko jedną liczbę, toteż całymi dniami kursują piechotą raz w jedną, a raz w drugą stronę całe rzesze ludzi żądnych zysku. O ile przemyt zwykłej liczby jest uznawany za mało szkodliwy społecznie i celnicy na ogół przymykają na niego oko, o tyle przemyt liczby pierwszej to poważne wykroczenie karane z całą surowością.
Siatka przemytników liczb pierwszych, na całe szczęście, jest już dosyć mocno rozpracowana i służby celne mają w niej swoich tajnych agentów. Tajni agenci nie marnują czasu i właśnie dostarczyli listę zawierającą liczby jakie przemycane będą jutro przez granicę. Z listy jasno wynika, że szykowana jest duża partia liczb pierwszych i celnicy szykują w związku z tym operację zakrojoną na szeroką skalę. Ich plan jest prosty - n celników wyskoczy ze swojej budki w najlepszym do tego momencie i złapie n kolejnych przemytników - każdy łapie tylko jednego, co ostatecznie jest nawet logiczne... Plan ma tylko jeden mały feler - celnicy nie mają pojęcia, który moment będzie najlepszy i ilu przemytników z liczbami pierwszymi uda im się zatrzymać. Pomóż im, napisz program, który na podstawie kolejnych liczb jakie przemycane będą jutro przez granicę ustali ile maksymalnie liczb pierwszych zatrzyma n-ta liczba celników, jeżeli rozpoczną operację w najlepszym do tego momencie.
Wejście
W pierwszej linii wejścia znajduje się liczba t (1 ≤ t ≤ 1000) określająca ilość zestawów danych. Każdy zestaw składa się z dwóch linii. Pierwsza z nich zawiera liczby m (1 ≤ m ≤ 1000) oraz n (1 ≤ n ≤ 100) oznaczające odpowiednio liczbę przemytników jaka przejdzie jutro przez granicę oraz liczbę celników jaka będzie uczestniczyć w akcji. Druga linia zawiera m liczb z zakresu od 0 do 106 - są to przemycane liczby (k-ta osoba przemyca k-tą liczbę).
Wyjście
Na wyjściu należy w oddzielnej linii dla każdego zestawu danych wypisać jedną liczbę - określającą ilu przemytników liczb pierwszych uda się zatrzymać w trakcie akcji.
Podsumowując dla danych wczytanych na wejściu należy wyznaczyć ile liczb pierwszych maksymalnie może znaleźć się w podciągu spójnym o długości nie przekraczającej n.
Przykład
Wejście:
2 8 4 3 8 6 5 4 4 7 7 9 5 9 6 12 7 4 5 3 2 4
Wyjście:
2 4
Dodane przez: | Maciej Boniecki |
Data dodania: | 2013-03-15 |
Limit czasu wykonania programu: | 0.5s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM64 SCM qobi |
Pochodzenie: | V Mistrzostwa WWSI w Programowaniu |