Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.85/26: Рейтинг темы: голосов - 26, средняя оценка - 4.85
Эксперт С++
7175 / 3234 / 79
Регистрация: 17.06.2009
Сообщений: 14,164
1

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

08.01.2010, 15:24. Показов 5110. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.01.2010, 15:24
Ответы с готовыми решениями:

Как сделать так, чтобы при нажатии на кнопку "Новая игра" игра начиналась заново?
Как сделать так, чтобы при нажатии на кнопку &quot;Новая игра&quot; игра начиналась заново? unit1.cpp void...

Игра слов, игра Scrabble
Задание: Создать программу для решения задачи построения слова из некоторого множества букв (игра...

Про пуговицы
в коробке 6 черных р 4 белых пуговицы. наугад берут две. какова вероятность того, чтоьони...

Бюджет 4500 гр. Конфигурация работа в Office, AutoCAD, игра Assassin, онлайн игра World of Tanks
Собираю компьютер для сестры. Основные требования: работа в Microsoft Office, AutoCAD, игра...

15
║XLR8║
1209 / 911 / 270
Регистрация: 25.07.2009
Сообщений: 4,370
Записей в блоге: 5
08.01.2010, 15:27 2
В принцыпе, можно было бы свести все к Ним, но я эт делать не умею.. Но по сути, нужно думать по логике, типа мы выиграем, если сделаем ход, который будет проиграшным для в-ого игрока..
0
Эксперт С++
7175 / 3234 / 79
Регистрация: 17.06.2009
Сообщений: 14,164
08.01.2010, 15:34  [ТС] 3
Все гораздо проще.
Сначала разберем задачу про камни.
Разделим камни на кучки по 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
║XLR8║
1209 / 911 / 270
Регистрация: 25.07.2009
Сообщений: 4,370
Записей в блоге: 5
08.01.2010, 15:35 4
это и есть сведение к Ним, спасибо
0
Эксперт С++
7175 / 3234 / 79
Регистрация: 17.06.2009
Сообщений: 14,164
08.01.2010, 15:36  [ТС] 5
Вернемся к исходной задаче.
У нас есть K - исходное число камней, при этом изменять его мы не можем.
Наша задача изменить L.
Условие выигрыша: K%(L+1) == 0
Мы перебираем L от 2 до K-1 чтобы было верно условие K%(L+1) == 0
Если мы найдем такое L, то значит это и есть ответ (причем это будет минимальное L).
Если не найдем такое L, то значит вывести 0.
0
║XLR8║
1209 / 911 / 270
Регистрация: 25.07.2009
Сообщений: 4,370
Записей в блоге: 5
08.01.2010, 15:38 6
ты динамить умеешь?

Добавлено через 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;
}
0
Эксперт С++
7175 / 3234 / 79
Регистрация: 17.06.2009
Сообщений: 14,164
08.01.2010, 15:39  [ТС] 7
Кстати по условию игрок всегда может взять L==K-1
Так как K%(K-1+1)=K%K=0, то второй игрок всегда может подобрать L чтобы выиграть.
Программа пишется тривиально.
Если конечно раньше вы решали задачу про камни, то и эта задача решается тривиально.
0
║XLR8║
1209 / 911 / 270
Регистрация: 25.07.2009
Сообщений: 4,370
Записей в блоге: 5
08.01.2010, 15:42 8
odip, задача с рюкзаком и т.д. - не мой конек..
если не очень затрудняет, можешь посмотреть задачу, называется "квадратная страна"
0
Эксперт С++
7175 / 3234 / 79
Регистрация: 17.06.2009
Сообщений: 14,164
08.01.2010, 15:43  [ТС] 9
Хочешь чтобы я за тебя все задачи там прорешал ?
0
║XLR8║
1209 / 911 / 270
Регистрация: 25.07.2009
Сообщений: 4,370
Записей в блоге: 5
08.01.2010, 15:45 10

Не по теме:

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



Добавлено через 1 минуту
odip, решать не обязательно, можно подсказать.. тем более что мне не так важно решить, как понять как решается..
0
Эксперт С++
7175 / 3234 / 79
Регистрация: 17.06.2009
Сообщений: 14,164
08.01.2010, 15:58  [ТС] 11
timus - не знаю
Может с маршрутами что
Сделай: tracert acm.timus.ru

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

Добавлено через 7 минут
Задача "Квадратная страна" Квадратная страна
0
║XLR8║
1209 / 911 / 270
Регистрация: 25.07.2009
Сообщений: 4,370
Записей в блоге: 5
08.01.2010, 16:00 12
тимус не хочет никак..
а, у вас ограничение на спасибо в день? тогда ясно..
0
Эксперт С++
7175 / 3234 / 79
Регистрация: 17.06.2009
Сообщений: 14,164
08.01.2010, 16:04  [ТС] 13
Кстати провайдер у этого 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 секунды
а, у вас ограничение на спасибо в день? тогда ясно..
Я не знаю, просто предположил.
0
║XLR8║
1209 / 911 / 270
Регистрация: 25.07.2009
Сообщений: 4,370
Записей в блоге: 5
08.01.2010, 21:34 14
сейчас тимум уже пашет и "спасибо" появились) только не везде..

Добавлено через 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;
}
не канает
0
Эксперт С++
7175 / 3234 / 79
Регистрация: 17.06.2009
Сообщений: 14,164
09.01.2010, 19:00  [ТС] 15
А я сдал
Только написал не так.
0
║XLR8║
1209 / 911 / 270
Регистрация: 25.07.2009
Сообщений: 4,370
Записей в блоге: 5
09.01.2010, 21:46 16
Цитата Сообщение от outoftime Посмотреть сообщение
FOR(i,1,k)
здесь по сути 2 нужно.., попробуем как-то а то опять тимус висет начал..
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.01.2010, 21:46

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Игра в «Одиннадцать предметов», игра Баше.
прошу помощи в создании программы! Разработать программную модель следующей игры двух...

Существует ли игра такая игра?
Всем привет. Существует ли такая игра, где, допустим, мы находимся на космическом корабле, в...

Игра
Помогите решить следующую задачу: Написать программу, которая отгадывает задуманное число в...

2D игра
Народ подскажите что сейчас актуально ? Как я понял XNA загнулся , ему на смену пришел MonoGame ,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
16
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.