Задача №114683. Прыжки по шкафам
В доме Кроша стояло \(n\) шкафов в линию, \(i\)-й шкаф имел высоту \(h_i\). Недавно Крош переехал, но не смог перевезти с собой те самые шкафы. Ему хочется купить \(n\) новых шкафов, чтобы те были как можно больше похожи на старые.
Крош не помнит конкретные высоты шкафов, но для каждой тройки подряд идущих шкафов он знает разность высот между самым высоким и самым низким из тройки. Иначе говоря, если последовательность высот шкафов была \(h_1, h_2, \ldots, h_n\), то Крош помнит величины \(w_i = \max(h_{i}, h_{i + 1}, h_{i + 2}) - \min(h_{i}, h_{i + 1}, h_{i + 2})\) для \(1 \leq i \leq n - 2\).
В новый дом Крош хочет купить \(n\) шкафов, так чтобы всё было как прежде — все значения \(w_i\) должны сохраниться. Помогите Крошу понять, какие шкафы ему следует купить и в какой последовальности поставить, или определите, что он что-то перепутал, и такой последовательности шкафов не может быть.
В первой строке даны два целых числа \(n\), \(C\) (\(3 \leq n \leq 10^6, 0 \leq C \leq 10^{12}\)) — количество шкафов и ограничение на \(w_i\).
Вторая строка содержит \(n - 2\) целых чисел \(w_1, w_2, \ldots, w_{n - 2}\) (\(0 \leq w_i \leq C\)).
Если не существует возможности купить \(n\) шкафов, удовлетворяющих условиям, в единственной строке выведите « No ».
Иначе в первой строке выведите « Yes », после чего во второй строке выведите \(n\) целых чисел \(h'_1, h'_2, \ldots, h'_n\) (\(0 \le h'_i \le 10^{18}\)) — высоты шкафов для покупки.
Можно показать, что если существует какое-то решение, то оно существует и при заданных ограничениях на высоты.
Если корректных решений несколько, выведите любое из них.
Рассмотрим первый пример:
- \(w_1 = \max(4, 8, 8) - \min(4, 8, 8) = 8 - 4 = 4\)
- \(w_2 = \max(8, 8, 16) - \min(8, 8, 16) = 16 - 8 = 8\)
- \(w_3 = \max(8, 16, 20) - \min(8, 16, 20) = 20 - 8 = 12\)
- \(w_4 = \max(16, 20, 4) - \min(16, 20, 4) = 20 - 4 = 16\)
- \(w_5 = \max(20, 4, 0) - \min(20, 4, 0) = 20 - 0 = 20\)
Также корректным был бы, например, ответ с высотами: \(0, 1, 4, 9, 16, 25, 36\)
Тесты к этой задаче состоят из десяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов всех необходимых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования
| Группа | Баллы | Доп. ограничения | Необх. группы | Комментарий | |
| \(n\) | \(C\) | ||||
| 0 | 0 | — | — | — | Тесты из условия. |
| 1 | 5 | \(n \leq 20\) | \(C \leq 20\) | \(0\) | |
| 2 | 7 | \(n \leq 200\) | \(C \leq 200\) | \(0,1\) | |
| 3 | 13 | \(n \leq 2\,000\) | \(C \leq 2\,000\) | \(0\)–\(2\) | |
| 4 | 5 | \(n \leq 100\,000\) | \(C \leq 20\) | \(0,1\) | |
| 5 | 5 | \(n \leq 20\) | \(C \leq 100\,000\) | \(0,1\) | |
| 6 | 5 | \(n \leq 50\) | — | \(0,1,5\) | |
| 7 | 15 | \(n \leq 2\,000\) | — | \(0\)–\(3,5,6\) | |
| 8 | 10 | \(n \leq 100\,000\) | \(C \leq 100\,000\) | \(0\)–\(5\) | |
| 9 | 15 | \(n \leq 100\,000\) | — | \(0\)–\(8\) | Offline-проверка. |
| 10 | 20 | — | — | \(0\)–\(9\) | Offline-проверка. |
7 20 4 8 12 16 20
Yes 4 8 8 16 20 4 0
11 10 5 7 2 3 4 5 2 1 8
Yes 1 1 6 8 6 5 2 0 0 1 8
6 9 1 6 9 0
No