Игра Пуговицы.

@odip · Регистрация: 17.06.2009

Студворк — интернет-сервис помощи студентам

http://acm.timus.ru/problem.as... &locale=ru

Правила игры очень просты. Перед двумя играющими находится кучка из K пуговиц. Играющие по очереди берут пуговицы из кучки, причем за один ход каждый из них может взять от 1 до L пуговиц. Выигрывает тот из спортсменов, которому удастся взять последнюю пуговицу.
Правила олимпийских соревнований будут лишь немного сложнее обычных. Тот из игроков, которому по жребию выпадает делать первый ход, получает возможность собственноручно назначить число K, руководствуясь в своём выборе только ограничениями 3 ≤ K ≤ 100 000 000 (именно столько пуговиц заготовлено для олимпийского турнира). Тот из игроков, который будет ходить вторым, выбирает, в свою очередь, число L, которое должно отвечать условию 2 ≤ L < K.

Задача
На вашу команду возлагается очень ответственная задание: необходимо написать программу, которая помогала бы второму игроку делать свой выбор. Другими словами, по заданному числу пуговиц в кучке K, необходимо определить такое число L, которое гарантирует победу второму игроку при наилучшей игре обеих сторон.
Так, например, если в кучке всего три пуговицы, то победу второму игроку обеспечивает выбор L = 2. В самом деле, если первый игрок своим ходом заберёт одну пуговицу, то второй сможет выиграть, взяв обе оставшихся пуговицы и, напротив, если первый возьмет две пуговицы, то второй победит, взяв последнюю.

Исходные данные
Вход для этой задачи состоит из одной строки, в которой записано единственное число K — количество пуговиц в кучке, выбранное первым игроком.

Результат
На выход следует записать единственное целое число L — максимальное количество пуговиц, которое можно взять за один ход — обеспечивающее победу второму игроку. Если таких чисел несколько, то следует вывести наименьшее из них. Если таких чисел нет, то следует вывести число 0.

Добавлено через 4 минуты
На самом деле это усложнение задачи про камни.
Есть 15 камней. Два игрока. За один раз можно брать до 3 камней.
Выигрывает тот, кто может взять последний.
Какая наилучшая стратегия 1-го игрока и 2-го игрока.

@outoftime · 08.01.2010, 15:27

В принцыпе, можно было бы свести все к Ним, но я эт делать не умею.. Но по сути, нужно думать по логике, типа мы выиграем, если сделаем ход, который будет проиграшным для в-ого игрока..

@odip · 08.01.2010, 15:34 **[ТС]**

Все гораздо проще.
Сначала разберем задачу про камни.
Разделим камни на кучки по 4 камня
15=3+4+4+4
Оптимальная стратегия 1-го игрока:
1-ый ход: взять 3 камня
Для 2-го игрока останутся кучки по 4 камня
Следующие ходы 1-го игрока:
Если 2-ой игрок берет 1 камень, то 1-ый берет 3
Если 2-той берет 2, то 1-ый берет 2
Если 2-ой берет 3, то 1-ый берет 1
То есть если 2-ой игрок берет I камней, то 1-ый игрок берет (4-I) камней.
Нетрудно видеть: чтобы ни делал 2-ой игрок, то 1-ый все равно берет последний камень.

Добавлено через 2 минуты
Если в задаче для камней мы можем менять начальное число камней.
Пусть начальное кол-во камней - N.
А брать мы можем от 1 до M камней.
В нашем случае N=15, M=3
Если мы можем изменять N, то мы видим, что
если N%4 != 0, то выигрывает 1-ый игрок
Но если N%4 == 0, то выигрывает 2-ой игрок
Например при N==12 выигрывает 2-ой игрок.

В общем случае очевидно что при N%(M+1) == 0 выигрывает 2-ой игрок.

@outoftime · 08.01.2010, 15:35

это и есть сведение к Ним, спасибо

@odip · 08.01.2010, 15:36 **[ТС]**

Вернемся к исходной задаче.
У нас есть K - исходное число камней, при этом изменять его мы не можем.
Наша задача изменить L.
Условие выигрыша: K%(L+1) == 0
Мы перебираем L от 2 до K-1 чтобы было верно условие K%(L+1) == 0
Если мы найдем такое L, то значит это и есть ответ (причем это будет минимальное L).
Если не найдем такое L, то значит вывести 0.

@outoftime · 08.01.2010, 15:38

ты динамить умеешь?

Добавлено через 2 минуты

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
 
#define FOR(i,a,b) for (int i(a),_b(b); i < _b; ++i)
 
using namespace std;
 
int main()
{
    int k;
    cin >> k;
    FOR(i,1,k)
        if (!(k%(i+1)) )
        {
            cout << i << endl;
            return 0;
        }
    cout << '0' << endl;
    return 0;
}

@odip · 08.01.2010, 15:39 **[ТС]**

Кстати по условию игрок всегда может взять L==K-1
Так как K%(K-1+1)=K%K=0, то второй игрок всегда может подобрать L чтобы выиграть.
Программа пишется тривиально.
Если конечно раньше вы решали задачу про камни, то и эта задача решается тривиально.

@outoftime · 08.01.2010, 15:42

odip, задача с рюкзаком и т.д. - не мой конек..
если не очень затрудняет, можешь посмотреть задачу, называется "квадратная страна"

@odip · 08.01.2010, 15:43 **[ТС]**

Хочешь чтобы я за тебя все задачи там прорешал ?

@outoftime · 08.01.2010, 15:45

Не по теме:

odip, ты не знаешь из-за чего могут быть такие лаги:
1) не грузится тимус (может быть их серв, но это отпадает, т.к. у вас все ок);
2) пропала кнопка спасибо.

Добавлено через 1 минуту
odip, решать не обязательно, можно подсказать.. тем более что мне не так важно решить, как понять как решается..

@odip · 08.01.2010, 15:58 **[ТС]**

timus - не знаю
Может с маршрутами что
Сделай: tracert acm.timus.ru

Спасибо - может есть ограничение на Спасибо
У тебя только в этой теме пропало или в других тоже ?
Ты много Спасибо сегодня сказал

Добавлено через 7 минут
Задача "Квадратная страна" Квадратная страна

@outoftime · 08.01.2010, 16:00

тимус не хочет никак..
а, у вас ограничение на спасибо в день? тогда ясно..

@odip · 08.01.2010, 16:04 **[ТС]**

Кстати провайдер у этого acm.timus.ru - криворукий.
Вот маршрут с двух разных мест.

...
6 ttk-1-gw.ebr.runnet.ru (194.85.43.54) 87.069 ms 86.117 ms 87.177 ms
7 usu.ebr.runnet.ru (194.85.43.6) 88.337 ms 87.361 ms 88.437 ms
8 10.255.27.1 (10.255.27.1) 86.854 ms 88.417 ms 89.337 ms
9 * * *
10 * * *
11 * * *

...
6 m9-1-gw.msk.runnet.ru (194.85.40.213) 55.938 ms 56.245 ms 55.456 ms
7 ttk-1-gw.ebr.runnet.ru (194.85.43.54) 81.452 ms 80.238 ms 79.950 ms
8 usu.ebr.runnet.ru (194.85.43.6) 79.438 ms 79.716 ms 80.850 ms
9 10.255.27.1 (10.255.27.1) 80.553 ms 79.677 ms 81.524 ms
10 * * *
11 * * *

10.255.27.1 - внутренний адрес, не должен светиться в Internet.

Добавлено через 24 секунды

а, у вас ограничение на спасибо в день? тогда ясно..

Я не знаю, просто предположил.

@outoftime · 08.01.2010, 21:34

сейчас тимум уже пашет и "спасибо" появились) только не везде..

Добавлено через 2 минуты
odip, вот правда что странно, что решение типа

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
 
#define FOR(i,a,b) for (int i(a),_b(b); i < _b; ++i)
 
using namespace std;
 
int main()
{
        int k;
        cin >> k;
        FOR(i,1,k)
                if (!(k%(i+1)) )
                {
                        cout << i << endl;
                        return 0;
                }
        cout << '0' << endl;
        return 0;
}

не канает

@odip · 09.01.2010, 19:00 **[ТС]**

А я сдал

Только написал не так.

@outoftime · 09.01.2010, 21:46

Сообщение от outoftime

FOR(i,1,k)

здесь по сути 2 нужно.., попробуем как-то а то опять тимус висет начал..

Новые блоги и статьи Все статьи Все блоги /
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ
Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .	Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164

	Игра Пуговицы. 08.01.2010, 15:24. Показов 7410. Ответов 15 Метки нет (Все метки) http://acm.timus.ru/problem.as... &locale=ru Правила игры очень просты. Перед двумя играющими находится кучка из K пуговиц. Играющие по очереди берут пуговицы из кучки, причем за один ход каждый из них может взять от 1 до L пуговиц. Выигрывает тот из спортсменов, которому удастся взять последнюю пуговицу. Правила олимпийских соревнований будут лишь немного сложнее обычных. Тот из игроков, которому по жребию выпадает делать первый ход, получает возможность собственноручно назначить число K, руководствуясь в своём выборе только ограничениями 3 ≤ K ≤ 100 000 000 (именно столько пуговиц заготовлено для олимпийского турнира). Тот из игроков, который будет ходить вторым, выбирает, в свою очередь, число L, которое должно отвечать условию 2 ≤ L < K. Задача На вашу команду возлагается очень ответственная задание: необходимо написать программу, которая помогала бы второму игроку делать свой выбор. Другими словами, по заданному числу пуговиц в кучке K, необходимо определить такое число L, которое гарантирует победу второму игроку при наилучшей игре обеих сторон. Так, например, если в кучке всего три пуговицы, то победу второму игроку обеспечивает выбор L = 2. В самом деле, если первый игрок своим ходом заберёт одну пуговицу, то второй сможет выиграть, взяв обе оставшихся пуговицы и, напротив, если первый возьмет две пуговицы, то второй победит, взяв последнюю. Исходные данные Вход для этой задачи состоит из одной строки, в которой записано единственное число K — количество пуговиц в кучке, выбранное первым игроком. Результат На выход следует записать единственное целое число L — максимальное количество пуговиц, которое можно взять за один ход — обеспечивающее победу второму игроку. Если таких чисел несколько, то следует вывести наименьшее из них. Если таких чисел нет, то следует вывести число 0. Добавлено через 4 минуты На самом деле это усложнение задачи про камни. Есть 15 камней. Два игрока. За один раз можно брать до 3 камней. Выигрывает тот, кто может взять последний. Какая наилучшая стратегия 1-го игрока и 2-го игрока. 0

@outoftime ║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,360 Записей в блоге: 5
	08.01.2010, 15:27
	В принцыпе, можно было бы свести все к Ним, но я эт делать не умею.. Но по сути, нужно думать по логике, типа мы выиграем, если сделаем ход, который будет проиграшным для в-ого игрока.. 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	08.01.2010, 15:34 [ТС]
	Все гораздо проще. Сначала разберем задачу про камни. Разделим камни на кучки по 4 камня 15=3+4+4+4 Оптимальная стратегия 1-го игрока: 1-ый ход: взять 3 камня Для 2-го игрока останутся кучки по 4 камня Следующие ходы 1-го игрока: Если 2-ой игрок берет 1 камень, то 1-ый берет 3 Если 2-той берет 2, то 1-ый берет 2 Если 2-ой берет 3, то 1-ый берет 1 То есть если 2-ой игрок берет I камней, то 1-ый игрок берет (4-I) камней. Нетрудно видеть: чтобы ни делал 2-ой игрок, то 1-ый все равно берет последний камень. Добавлено через 2 минуты Если в задаче для камней мы можем менять начальное число камней. Пусть начальное кол-во камней - N. А брать мы можем от 1 до M камней. В нашем случае N=15, M=3 Если мы можем изменять N, то мы видим, что если N%4 != 0, то выигрывает 1-ый игрок Но если N%4 == 0, то выигрывает 2-ой игрок Например при N==12 выигрывает 2-ой игрок. В общем случае очевидно что при N%(M+1) == 0 выигрывает 2-ой игрок. 0

@outoftime ║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,360 Записей в блоге: 5
	08.01.2010, 15:35
	это и есть сведение к Ним, спасибо 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	08.01.2010, 15:36 [ТС]
	Вернемся к исходной задаче. У нас есть K - исходное число камней, при этом изменять его мы не можем. Наша задача изменить L. Условие выигрыша: K%(L+1) == 0 Мы перебираем L от 2 до K-1 чтобы было верно условие K%(L+1) == 0 Если мы найдем такое L, то значит это и есть ответ (причем это будет минимальное L). Если не найдем такое L, то значит вывести 0. 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	08.01.2010, 15:39 [ТС]
	Кстати по условию игрок всегда может взять L==K-1 Так как K%(K-1+1)=K%K=0, то второй игрок всегда может подобрать L чтобы выиграть. Программа пишется тривиально. Если конечно раньше вы решали задачу про камни, то и эта задача решается тривиально. 0

@outoftime ║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,360 Записей в блоге: 5
	08.01.2010, 15:42
	odip, задача с рюкзаком и т.д. - не мой конек.. если не очень затрудняет, можешь посмотреть задачу, называется "квадратная страна" 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	08.01.2010, 15:43 [ТС]
	Хочешь чтобы я за тебя все задачи там прорешал ? 0

@outoftime ║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,360 Записей в блоге: 5
	08.01.2010, 15:45
	Не по теме: odip, ты не знаешь из-за чего могут быть такие лаги: 1) не грузится тимус (может быть их серв, но это отпадает, т.к. у вас все ок); 2) пропала кнопка спасибо. Добавлено через 1 минуту odip, решать не обязательно, можно подсказать.. тем более что мне не так важно решить, как понять как решается.. 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	08.01.2010, 15:58 [ТС]
	timus - не знаю Может с маршрутами что Сделай: tracert acm.timus.ru Спасибо - может есть ограничение на Спасибо У тебя только в этой теме пропало или в других тоже ? Ты много Спасибо сегодня сказал Добавлено через 7 минут Задача "Квадратная страна" Квадратная страна 0

@outoftime ║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,360 Записей в блоге: 5
	08.01.2010, 16:00
	тимус не хочет никак.. а, у вас ограничение на спасибо в день? тогда ясно.. 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	09.01.2010, 19:00 [ТС]
	А я сдал Только написал не так. 0