4-й этап Республиканской олимпиады по информатике 2019, 10-11 класс

Есеп F. Оңдаңыз!

Ограничение по времени:

1 second

Ограничение по памяти:

256 megabytes

Барлық сандары теріс емес массивты, Тима жақсы деп есептейді. Тиманың ұзындығы $n$ болатын, бүтін сандардан тұратын $a$ массивы бар. Тима оны жақсы еткісі келеді, сол үшін ол осындай операция істей алады:

• $1 <= i,j <= n, i \ne j, 1 <= x <= 10^9$ және $a_i \ge x$ орындалатын $i,j, x$ сандарын таңдап алып, $a_i$ санынан $x$ санын азайтып, ал $a_j$ санына $x$ қосу. Осы операцияның құны $|i - j| \cdot x$ теңге.

Қалайда аз теңге қолданып, Тиманың массивын жақсы етіңіз.

Формат входного файла

Бірінші жолда екі бүтін сан $n, type (1 <= n <= 3 \cdot 10^5, 0 <= type <= 1)$ енгізіледі. Екінші жолда $n$ бүтін сан $a_1,a_2, ..., a_n(-10^8 <= a_i <= 10^8)$ енгізіледі. $a$ массивын жақсы ете алынуына кепілдік беріледі.

Формат выходного файла

Бірінші жолда массивты жақсы етуге құртылған тенге санын шығарыңыз. Егер $type = 1$ болса, екінші жолда бір бүтін сан $k (0 <= k <= 2 \cdot n)$ — операциялар санын шығарыңыз. Келесі $k$ жолда үш саннан $i,j,x(1 <= i,j <= n, i \ne j, 1 <= x <= 10^9)$ — операциялар сипаттамасын шығарыңыз. Операциялар санын азайтудың қажеті жоқ, бастысы құртылған тенге санын азайтыңыз. Егер $type = 0$ болса, басқа ештеңе шығарудың керегі жоқ.

Система оценки

Есеп сегіз бөлімнен тұрады:

1. Мысалдағы тесттер. 0 ұпайға бағаланады.
2. $n <= 10, type = 0, -1 <= a_i <= 1$. 8 ұпайға есептеледі.
3. $n <= 200, type = 0, -10 <= a_i <= 10, |a_1| + |a_2| + ... + |a_n| <= 400$. 16 ұпайға есептеледі.
4. $n <= 10^5, type = 0, -10^8 <= a_i <= 10^8, a_1 + a_2 + ... + a_n = 0$. 12 ұпайға есептеледі.
5. $n <= 2000, type = 0, -1 <= a_i <= 1$. 15 ұпайға есептеледі.
6. $n <= 3 \cdot 10^5, type = 0, -10^8 <= a_i <= 10^8, a_1 + a_2 + ... + a_n = 1$. 13 ұпайға есептеледі.
7. $n <= 3 \cdot 10^5, type = 0, -10^8 <= a_i <= 10^8$. 15 ұпайға есептеледі.
8. $n <= 3 \cdot 10^5, type = 1, -10^8 <= a_i <= 10^8$. 21 ұпайға есептеледі.

Примеры:

Вход

7 0
1 1 -1 0 -1 1 1

Ответ

2

Вход

4 1
4 -2 -2 1

Ответ

5
3
1 2 2
1 3 1
4 3 1

( Temirlan Satylkhanov )