BARMAN
Limit pamięci: 64 MB
Profesor Bajtych jest bajtnistrem Arytmetycznych Rzędów Modulo Arbitralne N.
Rzędem liczby modulo nazywamy najmniejsze takie ,
że jest podzielne przez .
Pracownicy Bajtnisterstwa zmuszeni są do grania w trudną grę w celu określenia ich pensji.
Celem tej gry jest zapewnienie, by tylko osoby dobrze znające się na rzeczy zarabiały największe pieniądze.
Bajtych wybiera ciąg liczb i .
Pracownik dostaje do swojej wiadomości jedynie rzędy modulo .
Może on poprosić Bajtycha o wykonanie co najwyżej operacji polegających na tym,
że przemnaża się wszystkie liczby w pewnym spójnym podciągu przez jakąś liczbę
.
Bajtych płaci pracownikowi tyle B$, ile wynosi rząd sumy modulo
po wykonaniu wszystkich operacji.
Po kilku miesiącach urzędnicy BARMAN zorientowali się, że Bajtych jest bardzo zachłanny.
W rzeczywistości wybiera on liczby i dopiero po tym, jak
dostanie wszystkie operacje.
Twoim zadaniem jest napisanie programu, który zasugeruje, jakie operacje należy
wykonać, by Bajtych musiał nam zapłacić jak najwięcej.
Zadanie
Napisz program, który:
- wczyta opis ciągu ze standardowego wejścia,
- znajdzie optymalny ciąg operacji,
- wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu podana jest jedna liczba .
Drugi wiersz zawiera liczb , .
Liczba jest rzędem modulo .
Wyjście
Wynikiem ma być opis ciągu operacji.
W pierwszym wierszu ilość operacji .
W każdym z następnych wierszy należy podać trzy liczby ,
i , gdzie .
Oznaczają one, że -ta operacja polega na pomnożeniu wszystkich liczb od
do przez .
Przykład
Dla danych wejściowych:
3
6 10 15
poprawną odpowiedzią jest:
3
2 3 6
1 1 5
3 3 5
Autor zadania: Jakub Pawlewicz.