| 2020-2021 ICPC NERC (NEERC), North-Western Russia Regional Contest (Northern Subregionals) |
|---|
| Закончено |
Натан владеет магазином, который продает сувенирные нунчаки с уникальным дизайном. Нунчаки - это традиционное оружие боевых искусств, состоящее из двух палок, соединенных цепью. В дизайне Натана каждая палка инкрустирована $$$n$$$ драгоценными камнями, расположенными в ряд. Эти камни могут быть кварцевыми или ониксовыми, и они создают красивый черно-белый узор. По эстетическим причинам Натан продает только нунчаки с точно $$$k$$$ ониксами на обеих палках в сумме. Например, вот один из возможных дизайнов для $$$n=4$$$ и $$$k=5$$$.
Недавно Натан решил, что было бы хорошо иметь возможность продавать нунчаки с любым возможным дизайном. Но для этого ему потребуется иметь нунчаки с каждым возможным дизайном на складе, а количество возможных дизайнов огромно!
Таким образом, Натан решил пойти на компромисс. У него будет несколько палок на складе. Когда клиент заказывает определенный дизайн, Натан возьмет две палки со склада и соединит их цепью. Палки симметричны, и Натан может соединить цепь с любого конца палки. Например, если $$$n=3$$$ и $$$k=2$$$, и у Натана есть следующие палки на складе:
Тогда он может сделать нунчаки с любым возможным дизайном. Например, если клиент заказывает нунчаки с таким дизайном:
То Натан может сделать их из палок 1 и 3.
Теперь Натан задается вопросом: какое минимальное количество палок ему следует иметь на складе, чтобы иметь возможность сделать нунчаки с любым возможным дизайном? Помогите ему найти это число.
На вход подаются два целых числа $$$n$$$ и $$$k$$$ ($$$1\le n\le 50$$$; $$$0\le k\le 2\cdot n$$$).
Выведите одно целое число: минимальное количество палок, которое Натан должен иметь на складе.
3 2
7
4 1
3
5 0
2
50 50
626155273417404
| Название |
|---|


