Задача №113643. Делёж яблок
Осенью в одной провинциальной средневековой общине на юго-востоке Уэльса проходит делёж собранного урожая яблок. Эта община имеет внутреннюю иерархию, согласно которой каждый из n человек имеет ранг, являющийся целым положительным числом от 1 до n , причём все люди имеют разные ранги.
Процесс дележа урожая проходит следующим образом:
- Все члены общины в произвольном порядке встают в круг, в центре которого находится куча с собранным урожаем.
- Затем выбирается человек, который будет брать полагающуюся ему часть урожая первым.
- Этот человек подходит к куче и набирает в свой мешок количество яблок, равное его рангу.
- Затем в соответствии с тем же правилом набирает урожай человек, находящийся по правую руку от первого, затем следующий за ним и так далее, пока урожай не закончится. При этом возможно, что до одного и того же человека очередь брать яблоки будет доходить несколько раз.
- Если в куче осталось меньше яблок, чем ранг очередного подошедшего к ней человека, то этот человек берёт все оставшиеся яблоки.
Вам стало интересно, насколько данная процедура дележа яблок является честной. Определите, какое минимальное количество яблок может оказаться у человека после участия в описанной процедуре.
В единственной строке находится два целых числа n и k ( 3 ≤ n ≤ 10 000 , 1 ≤ k ≤ 10 9 ) — число людей и число яблок соответственно.
Выведите единственное целое число — минимальное количество яблок, которые могут оказаться у человека в результате описанной процедуры.
В первом примере община состоит из трёх людей, а урожай состоит из восьми яблок. Рассмотрим, например, следующий порядок рангов: 3, 1, 2.
- На первом шаге человек с рангом 3 берёт себе три яблока.
- На втором шаге человек с рангом 1 берёт себе одно яблоко.
- На третьем шаге человек с рангом 2 берёт себе два яблока.
- На четвёртом шаге человек с рангом 3 берёт себе последние два яблока в куче.
Таким образом, человеку с рангом 1 достанется одно яблоко. С другой стороны, вне зависимости от порядка людей в кругу каждому человеку достанется хотя бы одно яблоко, потому что первых шести яблок хватит на всех троих людей при любом порядке раздачи. Значит, минимальное возможное количество яблок у человека будет равно одному.
Во втором примере урожай состоит из одного-единственного яблока. В этом случае при любом порядке людей в кругу и любом выборе начинающего человека единственное яблоко достанется начинающему, а двум оставшимся людям яблок не достанется совсем. Значит, минимальное возможное количество яблок у человека будет равно нулю.
3 8
1
3 1
0