Между домами

Решение этой задачи очень простое: если 𝑘>𝑠
 или 𝑘⋅(𝑛−1)<𝑠
, ответ «NO». Иначе давайте 𝑘
 раз повторим следующую операцию: пусть 𝑑𝑖𝑠𝑡
 равно 𝑚𝑖𝑛(𝑛−1,𝑠−𝑘+1)
 (мы должны жадно уменьшать оставшуюся дистанцию, но мы также должны помнить о количестве переходов, которое нам необходимо совершить). Перейдем к любому возможному дому, находящемуся на дистанции 𝑑𝑖𝑠𝑡
 от текущего дома (также надо не забывать вычитать 𝑑𝑖𝑠𝑡
 из 𝑠
).

Доказательство факта, что мы всегда можем пойти к дому на дистанции 𝑑𝑖𝑠𝑡
, очень простое: один из возможных ответов (который получается при помощи алгоритма, описанного выше) будет выглядеть как какое-то количество переходов дистанции 𝑛−1
, (возможно) один переход случайной дистанции, меньшей 𝑛−1
, и какое-то количество переходов дистанции 1
. Первая часть ответа может быть получена, если мы стоим около самого левого или самого правого дома, вторая и третья части всегда могут быть получены, потому что расстояния, которые мы будем проходить в каждом из таких ходов, будут меньше 𝑛−1
.

Асимптотика решения 𝑂(𝑘)
.

def step(cur, x):
    if(cur - x > 0):
        return cur - x
    else:
        return cur + x



n, k, s = map(int, input().split())
cur = 1

if(k > s or k * (n - 1) < s):
    print('NO')
else:
    print('YES')
    while(k > 0):
        l = min(n - 1, s - (k - 1))
        cur = step(cur, l)
        print(cur, end = ' ')
        s -= l
        k -= 1