Задача №115145. Модообразная последовательность
Даны два целых числа \(x\) и \(y\). Назовем последовательность \(a\) длины \(n\) модообразной , если \(a_1=x\), и для всех \(1 < i \le n\) значение \(a_{i}\) равно либо \(a_{i-1} + y\), либо \(a_{i-1} \bmod y\). Здесь \(x \bmod y\) обозначает остаток от деления \(x\) на \(y\).
Определите, существует ли модообразная последовательность длины \(n\), сумма элементов которой равна \(S\), и если существует, то найдите любую такую последовательность.
Первая и единственная строка содержит четыре целых числа \(n\), \(x\), \(y\) и \(S\) (\(1 \le n \le 200\,000\), \(0 \le x \le 200\,000\), \(1 \le y \le 200\,000\), \(0 \le S \le 200\,000\)) — длина последовательности, параметры \(x\) и \(y\), и необходимая сумма элементов последовательности.
Если искомая последовательность существует, выведите в первой строке « Yes » (без кавычек). Далее, во второй строке выведите \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) через пробел — элементы последовательности \(a\). Если подходящих последовательностей несколько, выведите любую из них.
Если же последовательность не существует, выведите в единственной строке « No ».
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки « yEs », « yes », « Yes » и « YES » будут приняты как положительный ответ.
Тесты к этой задаче состоят из примеров и \(5\) групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп.
| Доп. ограничения | |||||
| Группа | Баллы | \(n\) | \(S\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия |
| 1 | 15 | \(n \le 15\) | – | 0 | |
| 2 | 15 | \(n \le 100\) | \(S \le 100\) | 0 | |
| 3 | 20 | – | – | – | \(x \lt y\) |
| 4 | 25 | – | \(S \le 3000\) | 0, 2 | |
| 5 | 25 | – | – | 0 – 4 | |
В первом примере условиям удовлетворяет последовательность \([8, 11, 2, 5, 2]\). Таким образом, \(a_1 = 8 = x\), \(a_2 = 11 = a_1 + 3\), \(a_3 = 2 = a_2 \bmod 3\), \(a_4 = 5 = a_3 + 3\), \(a_5 = 2 = a_4 \bmod 3\).
Во втором примере первый элемент последовательности должен равняться \(5\), поэтому последовательность \([2, 2, 2]\) не подходит.
5 8 3 28
Yes 8 11 2 5 2
3 5 3 6
No