| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 34 | 20 | 13 | 52.000% |
Ciąg liczb naturalnych nazywamy stabilnym, jeśli każde dwa jego kolejne elementy mają największy wspólny dzielnik (NWD) większy od 1.
Przykładowo ciąg (5, 15, 9, 21, 14) jest stabilny, ponieważ NWD(5, 15) = 5 > 1, NWD(15, 9) = 3 > 1, NWD(9, 21) = 3 > 1 oraz NWD(21, 14) = 7 > 1. Za to bardzo podobny ciąg siedmioelementowy (5, 15, 7, 9, 21, 8, 14) stabilny nie jest, bo np. NWD(15, 7) = 1.
Mając dany ciąg liczb naturalnych, usuń z niego niektóre elementy (być może zero) tak, aby pozostały ciąg był stabilny. Zrób to tak, żeby jak najwięcej elementów pozostało w ciągu. Jako odpowiedź wypisz numery pozostawionych elementów, czyli ich pozycje w wejściowym ciągu. Na przykład z ciągu (2, 5, 6, 3) można pozostawić trzy elementy: pierwszy, trzeci i czwarty.
W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N (1 ≤ N ≤ 30 000) określająca liczbę elementów ciągu.
W drugim (ostatnim) wierszu wejścia znajduje się ciąg N liczb naturalnych Ai (1 ≤ Ai ≤ 108), pooddzielanych pojedynczymi odstępami. Są to elementy danego ciągu.
W pierwszym wierszu wyjścia należy wypisać jedną liczbę naturalną R – największą liczbę elementów, które można pozostawić z wejściowego ciągu tak, aby otrzymać ciąg stabilny. W drugim wierszu wyjścia należy wypisać rosnący ciąg Rliczb naturalnych – numery elementów, które należy pozostawić. Jeśli istnieje więcej niż jedna prawidłowa możliwość pozostawienia R elementów, możesz wypisać dowolną z nich.
Elementy wejściowego ciągu numerowane są kolejnymi liczbami naturalnymi od 1 do N włącznie.
7 5 15 7 9 21 8 14
5 1 2 4 5 7
Wyjaśnienie do przykładu: Jest to przykład opisany w treści zadania.
9 6 3 3 10 5 5 14 7 7
5 1 4 7 8 9
Wyjaśnienie do przykładu: Możemy się przekonać, że jeżeli pozostawimy 3 lub 5, to długość ciągu nie będzie mogła przekroczyć 4. Z drugiej strony wszystkie pozostałe elementy tworzą ciąg stabilny, dlatego odpowiedzią w pierwszym wierszu wyjścia jest 5.
5 1 1 1 1 1
1 1
Wyjaśnienie do przykładu: Jako że NWD(1, 1) = 1, to jedynym stabilnym ciągiem jest ten złożony z pojedynczego elementu. Stąd odpowiedź w pierwszym wierszu wyjścia to 1. Zauważ też, że w drugim wierszu wyjścia prawidłową odpowiedzią jest dowolna liczba między 1 a 5.