|
Каноническая последовательность
(Время: 1 сек. Память: 32 Мб Сложность: 50%)
Пусть M и N – различные натуральные числа. Необходимо построить последовательность длиной K. Последовательность целых чисел a1, a2, …, aK называется канонической, если для всех допустимых i выполняются оба условия:
- сумма любых подряд идущих M членов отрицательна: ai + ai+1 + … + ai+M-1 < 0;
- сумма любых подряд идущих N членов положительна: ai + ai+1 + … + ai+M-1 > 0.
Каждый тип условия должен встречаться хотя бы один раз!
Если корректной последовательности длины K не существует, выведите «NO», иначе выведите «YES», а затем в следующей строке единственную каноническую последовательность a1..aK, определённую правилом ниже.
Введём префиксные суммы: S0 = 0, Si = a1 + … + ai (i = 1..K). Среди всех канонических последовательностей длины K выведите ту, у которой вектор (S0, S1, …, SK) минимален в лексикографическом порядке. Т.е. X лучше Y, если существует первый индекс j, для которого X0 = Y0, X1 = Y1, …, Xj-1 = Yj-1, и при этом Xj < Yj.
Входные данные
Входной файл INPUT.TXT содержит три натуральных числа M, N, K (1 ≤ M, N, K ≤ 2×105).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 2 3 | YES
-2 3 -2 |
| 2 | 10 4 11 | YES
0 -3 0 4 0 -3 0 4 0 -3 0 |
| 3 | 3 5 4 | NO |
| 4 | 3 5 5 | YES
2 0 -3 2 0 |
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
