Замок
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Замок имеет форму большого квадрата, составленного из `N`x`N` маленьких квадратиков. Внешние
квадратики являются башнями, именно они играют основную роль в защите замка от неприятеля.
Например, если замок имеет размер 4x4, то у него 12 башен (смотрите второй рисунок, башни
на нем выделены серым цветом).
Замок охраняет `K` полков, которые необходимо разместить по башням. В одной башне можно
разместить несколько полков, но при этом в каждой башне должен находиться хотя бы один полк,
иначе неприятель легко захватит эту башню. Если все башни защищены, то неприятель выбирает
для атаки одну из четырех сторон замка, которую защищает наименьшее число полков (то есть
суммарное число полков во всех башнях данной стороны квадрата минимально).
Определите, как нужно разместить полки для наилучшей защиты замка.
Первая строка входных данных содержит число `N` – размер замка (`2\ ≤\ N\ ≤\ 100`). Вторая строка
входных данных содержит число `K` – количество полков, охраняющих замок (`0\ ≤\ K\ ≤\ 1000`).
Выведите единственное число – количество полков на наименее укрепленной стороне замка при
наилучшем размещении полков. Если имеющихся полков недостаточно для защиты всех башен,
выведите число 0.
В первом примере башни четыре, а полков – пять, поэтому на
одну из башен можно поставить два полка, но все равно найдется сторона, которую
защищает всего два полка.
Во втором примере можно расположить полки так, что
каждую сторону будет защищать 5 полков.
Защитить каждую сторону не менее, чем
шестью полками не удастся.
Источник: Московская олимпиада школьников по информатике, 2011/12 учебный год