Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
MWP5_2E - Ciąg |
Twoim zadaniem jest określić maksymalną możliwą długość ciągu wygenerowanego poprzez wielokrotne użycie n różnych elementów otrzymanych na wejściu. Ciąg musi spełniać wyłącznie jeden warunek: dowolne kolejne n pozycji ciągu musi składać się z dokładnie n różnych elementów.
Aby nieco dokładniej wyjaśnić dosyć zawile opisany problem poniżej przedstawione zostało rozwiązanie drugiego zestawu z danych przykładowych: 3 3 2 1 (jako elementy ciągu wyłącznie dla zilustrowania problemu użyte zostały liter A, B oraz C).
Dysponując trzema literami A, dwoma literami B oraz jedną literą C, najdłuższy ciąg spełniający wymaganie aby dowolne kolejne trzy pozycje składały się z dokładnie trzech różnych elementów to: ABCAB, odpowiedź zatem wynosi 5.
Wejście
W pierwszej linii wejścia znajduje się liczba t (1 ≤ t ≤ 500) określająca ilość zestawów danych. Każdy zestaw mieści się w jednej linii i składa się z liczby n (2 ≤ n ≤ 1000) określającej ile różnych elementów występować będzie w ciągu i następujących po niej n liczb (i-ta liczba określa ile i-tych elementów jest do dyspozycji).
Wyjście
Na wyjściu należy w oddzielnej linii dla każdego zestawu danych wypisać jedną liczbę określającą maksymalną możliwą długość ciągu spełniającego wymóg opisany w treści zadania.
Przykład
Wejście:
3 4 6 4 5 2 3 3 2 1 2 4 2
Wyjście:
11 5 5
Dodane przez: | Maciej Boniecki |
Data dodania: | 2013-03-15 |
Limit czasu wykonania programu: | 0.300s |
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 |