Одиннадцатиклассник Кирилл увлекается современными технологиями, в частности, загадочным разделом информатики «machine learning» (машинное обучение). Сейчас он собирается решать задачи на построение и обучение нейросетей.
Самая простая нейросеть представляется в виде n слоев нейронов. Первый — это «входной» слой, на который подаются параметры изучаемого объекта, n-ый — это «выходной» слой, итоговые значения в нейронах которого — реакция сети на объект (ответ). Остальные, промежуточные слои, пронумерованы от 2 до (n - 1) и призваны производить «мыслительный процесс». При этом для любого 1 ≤ i ≤ n - 1, каждый нейрон i-го слоя и каждый нейрон (i + 1)-го связаны.
Заметим, что в условиях нашей задачи сеть может не иметь промежуточных слоев, более того, входной слой может являться и выходным одновременно.
Кирилл хочет построить сеть мощности как минимум k. Он еще не очень разбирается в новой теме, но считает, что мощность нейросети — суммарное количество путей из вершин входного слоя в вершины выходного слоя. Мы будем считать только такие пути, которые включают в себя по одной вершине из каждого слоя.
Также Кирилл точно знает, что чем больше в сети нейронов, тем медленнее она обрабатывается, а значит, что из всех сетей мощности больше либо равной k он хочет построить ту, которая содержит минимальное количество нейронов.
Напишите программу, которая по количеству слоев и требуемой мощности поможет Кириллу найти минимальное необходимое число нейронов.
На вход даются 2 целых числа: n — количество слоев, и k — требуемая мощность нейросети (1 ≤ n ≤ 105, 0 ≤ k ≤ 1018).
Необходимо вывести одно число — минимальное необходимое число нейронов.
2 6
5
3 17
8
2 89
19
Заметим, что k может выходить за ограничения стандартных 4 байтовых типов языков программирования. Для работы с большими целыми числами в языке Pascal предусмотрен тип int64, а в C++ — тип long long.
Один из возможных вариантов сети для первого теста приведен на иллюстрации выше. Конфигурация сети: три входных вершины и две выходных, всего ровно 6 путей.
Возможная сеть для теста 2 изображена ниже. Также на рисунке выделен один из рассматриваемых путей. Заметим, что несмотря на наличие в данной сети целых 18 путей, невозможно составить сеть из меньшего количества вершин, удовлетворяющую условиям.
Каждый день студент Олег добирается на учебу в город Долгопрудный через железнодорожный переезд.
Для обеспечения безопасности пассажиров при движении по дороге к переезду действуют следующие правила.
- Скорость всех движущихся транспортных средств на расстоянии не более S метров от переезда не должна превышать V1 м/c.
- Все транспортные средства на расстоянии не более S метров от переезда обязаны остановиться при закрытии переезда и продолжить движение только после его открытия.
Олег хочет приехать в институт как можно раньше,поэтому он может использовать и альтернативный способ передвижения, а именно — его собственные ноги, на которых он передвигается со скоростью V2 м/c.
Автобусная остановка Олега находится ровно в S метрах от переезда и он начинает свой путь в институт в момент времени 0. Также, в момент времени 0 к остановке подходит автобус Олега.
Переезд закрывается, как только на него прибывает электричка, и открывается сразу после её отбытия. Современные технологии позволили добиться того, чтобы переезд открывался и закрывался мгновенно.
Профессионализм водителя автобуса позволяет ему мгновенно разгоняться и тормозить до любой скорости. Водитель автобуса также хочет проехать переезд как можно быстрее, так что автобус всегда будет двигаться с максимально допустимой скоростью V1 м/c.
Напишите программу, которая поможет Олегу выбрать наиболее быстрый способ преодоления переезда: пешком или на автобусе. Над переездом есть пешеходный мост, поэтому Олег может преодолеть переезд пешком даже есть он закрыт, при этом время прохождения по мосту считается пренебрежительно малым (равно нулю). Также Олег не может выходить из автобуса после того, как сел в него, чтобы не нарушать правила высадки пассажиров.
В первой строке даны целые числа S, V1 и V2 (1 ≤ S, V1, V2 ≤ 109) — расстояние до переезда, скорость езды на автобусе и скорость ходьбы пешком.
Во второй строке дано целое число n (0 ≤ n ≤ 105) — количество электричек в расписании. В следующих n строках идет описание электричек — пары чисел: li, ri (0 ≤ li < ri ≤ 109), где li — время прибытия, а ri — время отъезда электрички с переезда. Заметим, что до окончания li-ой секунды, автобус двигается, как и во время (ri + 1)-ой, если, конечно, время отхода одной электрички не совпадает с временем прихода другой.
Гарантируется, что отрезки времени нахождения электричек на переезде не пересекаются (однако могут касаться, например: (l1, r1) = (1, 2), (l2, r2) = (2, 3)).
Один способ считается лучше другого, если количество необходимых секунд для него, округленных вверх, меньше количество необходимых секунд для другого способа, тоже округленного вверх.
Если перейти переезд пешком лучше, чем ехать на автобусе, то выведите в качестве первой строки «WALK», во всех остальных случаях выведите «BUS» (без кавычек).
Второй строкой выведите количество необходимых секунд, округленное вверх.
Гарантируется, что решение, которое работает в том случае, когда li, ri ≤ 106, наберет не менее, чем 40 баллов.
20 5 1
3
0 10
12 14
40 100
BUS
16
20 2 1
3
6 12
13 15
16 19
WALK
20