Ctrl K

Гонка из общей кучки чисел

Средняя
Двое играют в такую игру. На столе лежат карточки с числами от 1 до top, каждая по одной. Игроки ходят по очереди: берут любую оставшуюся карточку и прибавляют её число к общей сумме (в начале сумма равна 0). Взятая карточка из игры уходит. Выигрывает тот, после чьего хода сумма впервые станет не меньше goal. Оба играют наилучшим образом. Верните True, если первый игрок может гарантировать себе победу, иначе False. Если карточки кончились, а сумма так и не дошла до goal, победителя нет — это тоже False. Если goal равен 0, первый игрок считается победителем сразу.
Пример 1
top=5, goal=6 → False

Что бы ни взял первый игрок (от 1 до 5), до 6 остаётся от 1 до 5, и второй берёт одно из ещё свободных чисел, которое добивает сумму. Первый проигрывает.

Пример 2
top=6, goal=6 → True

Первый игрок сразу берёт 6 и выигрывает.

Пример 3
top=4, goal=11 → False

Сумма всех чисел 1 + 2 + 3 + 4 = 10 < 11: до цели не дойдёт никто, и первый не выигрывает.

Ограничения
  • 1 ≤ top ≤ 20
  • 0 ≤ goal ≤ 300
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСамая дешёвая корзина с наборами СредняяГруппы с равными суммами СредняяБери из любой кучки СредняяМеньше всего прямых через точки СредняяПроизведения без квадратов Средняя
загружаем Python…
Вход
top=5, goal=6
Ожидается
False

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 78 тестов на сервере, включая скрытые.