| Автор: | M. Sporyshev, A. Zhikhareva | Ограничение времени: | 1 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
| Выходной файл: | output.txt | |||
| Максимальный балл: | 100 |
В лаборатории стоит необычная конструкция из N одинаковых цилиндрических сосудов, выстроенных в ряд.
В i-й сосуд налито ai миллилитров жидкости.
За один шаг можно перелить любое количество жидкости из одного сосуда в одного или обоих его соседей слева и справа в любой пропорции. Количество жидкости во всех сосудах после каждого шага должно оставаться целочисленным.
Требуется написать программу, выполняющую минимально необходимое количество вышеописанных шагов, чтобы уравнять количество жидкости во всех сосудах.
Первая строка входного файла содержит целое число N.
Вторая строка содержит N целых чисел ai. Гарантируется, что общее количество жидкости делится на N.
Первая строка выходного файла должна содержать целое число S — минимальное число шагов.
Следующие S строк содержат по три целых числа I, L, R — индекс сосуда, начиная с 1, увеличение уровня в соседнем слева сосуде, увеличение уровня в соседнем справа сосуде соответственно.
Если решений несколько, выведите любое из них.
1 ≤ N ≤ 105
0 ≤ ai ≤ 109
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены. Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи. По запросу сообщается результат окончательной проверки на каждом тесте.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи |
|---|---|---|---|
| N | |||
| 1 | 25 | 1 ≤ N ≤ 10 | |
| 2 | 15 | 1 ≤ N ≤ 100 | 1 |
| 3 | 20 | 1 ≤ N ≤ 1000 | 1,2 |
| 4 | 40 | 1 ≤ N ≤ 100000 | 1,2,3 |
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 |
|
|
| 2 |
|
|