ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1023. Пуговицы

Hint to this question
Послано guilty spark 29 авг 2020 11:09
If you pick n-1 as l then the second player will always win, so answer can never be 0
0 means  picked up the first player and 1 means picked up the second;
Case 1: 3 buttons
for i = 1 //doesn't make sense to solve for 1 since its asked to choose >=2
1 2 3
0 1 0 //first player won
for i = 2
1 2 3
0 0 1
0 1 1 // first play wins in each case
Case 2: 4 buttons
for i = 2
1 2 3 4
0 1 1 0
0 1 0 0 //first player wins in both these cases
for i = 3:
1 2 3 4
0 0 0 1
0 1 1 1
0 0 1 1 //second player wins in each case
case 3: 6 buttons (5 and 6 are similar)
1 2 3 4 5 6
for i = 2
0 1 1 0 0 1
0 0 1 0 0 1
0 1 1 0 1 1 //second player is  winning

It's clearly seen that the minimal choice to win is k such that n %(k+1) == 0
since n%((n-1)+1) is always 0, n-1 is always an answer in case no smaller answer exists.