Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
`N` паломников после совместного путешествия к пирамидам Джелибейби сидят за круглым столом.
Во время поездки они делали какие-то платежи как за себя, так и за других членов группы. У каждого
есть некоторая сумма денег, оставшаяся после поездки, и каждый подсчитал, какая сумма должна получиться, если
бы он платил только за себя. Вместо того, чтобы прямо передать деньги друг другу,
паломники рассчитали среднее арифметическое `S` для сумм, оставшихся у них после поездки, и пытаются
перераспределить деньги нужным образом, используя только следующую операцию по передаче денег.
Пусть у `i`-го человека текущая сумма денег равна `a_i`. Если `a_i\ >\ S`, то `i`-й человек должен
передать соседу слева сумму `a_i\ -\ S` и такую же сумму соседу справа. Если `a_i\ <\ S`, то `i`-й человек должен
забрать у сосед слева сумму `S\ -\ a_i` и такую же сумму у соседа справа.
Напишите программу, которая определит, смогут ли паломники получить нужные конечные суммы, используя
указанную операцию, и каким образом. Допускается, что при выполнении плана передачи денег у человека
может получаться на руках отрицательная или дробная сумма денег.
Формат ввода
В первой строке ввода содержится одно целое число `N` (`3\ ≤\ N\ ≤\ 1000`) – количество паломников.
Во второй строке содержится `N` целых чисел `a_i` в диапазоне от 0 до 1000 – начальные суммы денег у паломников
в порядке обхода стола по часовой стрелке. В третьей строке содержится `N` целых чисел `b_i` в диапазоне
от 0 до 1000 – конечные суммы денег у паломников в том же порядке. Гарантируется, что сумма `a_i` равна сумме `b_i`.
Формат вывода
Если перераспределение денег возможно, то в первой строке вывести сообщение YES, во второй строке
вывести количество операций по передач денег, в третьей строке – номера паломников, которые
должны выполнять передачу. Нумерация паломников начинается с 1. Можно вывести любой план
выполнения операций, не обязательно самый кратчайший.
Если перераспределение денег невозможно, то в первой строке вывести сообщение NO.
Пример ввода
3
1 2 3
3 1 2