Задача №1873. Аттракцион
В парке поставили экспериментальную модель аттракциона. Посетители рассаживаются по местам, затем аттракцион запускают, и посетители с головокружительной скоростью носятся по причудливым траекториям. К сожалению, аттракцион не всегда работает: иногда он ломается, и все, кто в этот момент был на аттракционе, уходят недовольными и больше в парк не приходят. Было установлено, что аттракцион ломается тогда и только тогда, когда на нём катается не меньше, чем \(x\) человек, для некоторого неизвестного заранее, но фиксированного целого числа \(x\) (\(1 \le x \le n\), где \(n\) — общее число мест на аттракционе).
Хозяин парка аттракционов — циничный человек, и он не очень расстроится, если несколько посетителей будут недовольны поломками на аттракционе. Гораздо больше его заботит расход электроэнергии, требуемой для запуска аттракциона. Количество энергии, требуемое для однократного запуска аттракциона, постоянно и не зависит от количества занятых мест и от того, случится ли при работе аттракциона поломка.
Хозяин парка хочет сделать как можно меньше запусков аттракциона, прежде чем ему станет известно, чему в точности равно число \(x\). В его власти количество посетителей при каждом новом запуске аттракциона. Однако хозяин парка знает, что, если в ходе его экспериментов недовольных окажется больше, чем \(k\) человек, они соберутся вместе и напишут жалобу в министерство. Конечно, для хозяина парка такой поворот событий совершенно неприемлем.
Примерьте на себя шкуру холодного расчётливого циника и посчитайте, какое минимальное количество запусков потребуется для решения поставленной задачи.
В первой строке входного файла записаны через пробел два целых числа \(n\) и \(k\) — количество мест на аттракционе и максимальное возможное количество недовольных (\(1 \le n \le 600\), \(0 \le k \le 10^9\)).
В выходной файл выведите единственное число — минимальное количество запусков аттракциона, которое потребуется совершить, чтобы узнать число \(x\) и сделать не более \(k\) человек недовольными. Если решить задачу невозможно, выведите вместо этого \(-1\).
В первом примере сначала следует запустить аттракцион с двумя посетителями. Если он сломается, во второй запуск следует посадить на аттракцион одного человека. В случае поломки всего недовольных будет трое и станет известно, что \(x = 1\). В случае успешного запуска недовольных будет двое и мы узнаем, что \(x = 2\).
Если же с двумя посетителями аттракцион не сломался, запустим его для трёх человек. При поломке будет три недовольных и \(x = 3\). При успешном запуске недовольных нет и из условия \(1 \le x \le 4\) получаем, что \(x = 4\).
Определить \(x\) быстрее, чем за два запуска, в первом примере не удастся.
Во втором примере невозможно посадить на аттракцион более двух человек, из-за чего оказывается, что случаи \(x = 3\) и \(x = 4\) неразличимы.
Подзадача 1 (30 баллов): \( n \le 150\)
Подзадача 2 (30 баллов): \( n \le 475\)
Подзадача 3 (20 баллов): \( n \le 590\)
Подзадача 4 (20 баллов): \( n \le 600\)
4 3
2
4 2
-1