Форум программистов, компьютерный форум CyberForum.ru

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.61
odip
Эксперт C++
 Аватар для odip
7226 / 3288 / 59
Регистрация: 17.06.2009
Сообщений: 14,165
08.01.2010, 15:24     Игра Пуговицы. #1
http://acm.timus.ru/problem.aspx?spa...1023&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-го игрока.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.01.2010, 15:24     Игра Пуговицы.
Посмотрите здесь:

2D игра на C/C++ C++
C++ Игра
C++ Builder Игра на C++
Игра на С++ C++
C++ игра (с++)
Visual C++ Игра на C++
C++ Игра на C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
08.01.2010, 15:27     Игра Пуговицы. #2
В принцыпе, можно было бы свести все к Ним, но я эт делать не умею.. Но по сути, нужно думать по логике, типа мы выиграем, если сделаем ход, который будет проиграшным для в-ого игрока..
odip
Эксперт C++
 Аватар для odip
7226 / 3288 / 59
Регистрация: 17.06.2009
Сообщений: 14,165
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-ой игрок.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
08.01.2010, 15:35     Игра Пуговицы. #4
это и есть сведение к Ним, спасибо
odip
Эксперт C++
 Аватар для odip
7226 / 3288 / 59
Регистрация: 17.06.2009
Сообщений: 14,165
08.01.2010, 15:36  [ТС]     Игра Пуговицы. #5
Вернемся к исходной задаче.
У нас есть K - исходное число камней, при этом изменять его мы не можем.
Наша задача изменить L.
Условие выигрыша: K%(L+1) == 0
Мы перебираем L от 2 до K-1 чтобы было верно условие K%(L+1) == 0
Если мы найдем такое L, то значит это и есть ответ (причем это будет минимальное L).
Если не найдем такое L, то значит вывести 0.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
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;
}
odip
Эксперт C++
 Аватар для odip
7226 / 3288 / 59
Регистрация: 17.06.2009
Сообщений: 14,165
08.01.2010, 15:39  [ТС]     Игра Пуговицы. #7
Кстати по условию игрок всегда может взять L==K-1
Так как K%(K-1+1)=K%K=0, то второй игрок всегда может подобрать L чтобы выиграть.
Программа пишется тривиально.
Если конечно раньше вы решали задачу про камни, то и эта задача решается тривиально.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
08.01.2010, 15:42     Игра Пуговицы. #8
odip, задача с рюкзаком и т.д. - не мой конек..
если не очень затрудняет, можешь посмотреть задачу, называется "квадратная страна"
odip
Эксперт C++
 Аватар для odip
7226 / 3288 / 59
Регистрация: 17.06.2009
Сообщений: 14,165
08.01.2010, 15:43  [ТС]     Игра Пуговицы. #9
Хочешь чтобы я за тебя все задачи там прорешал ?
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
08.01.2010, 15:45     Игра Пуговицы. #10

Не по теме:

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



Добавлено через 1 минуту
odip, решать не обязательно, можно подсказать.. тем более что мне не так важно решить, как понять как решается..
odip
Эксперт C++
 Аватар для odip
7226 / 3288 / 59
Регистрация: 17.06.2009
Сообщений: 14,165
08.01.2010, 15:58  [ТС]     Игра Пуговицы. #11
timus - не знаю
Может с маршрутами что
Сделай: tracert acm.timus.ru

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

Добавлено через 7 минут
Задача "Квадратная страна" Квадратная страна
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
08.01.2010, 16:00     Игра Пуговицы. #12
тимус не хочет никак..
а, у вас ограничение на спасибо в день? тогда ясно..
odip
Эксперт C++
 Аватар для odip
7226 / 3288 / 59
Регистрация: 17.06.2009
Сообщений: 14,165
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 секунды
а, у вас ограничение на спасибо в день? тогда ясно..
Я не знаю, просто предположил.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
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;
}
не канает
odip
Эксперт C++
 Аватар для odip
7226 / 3288 / 59
Регистрация: 17.06.2009
Сообщений: 14,165
09.01.2010, 19:00  [ТС]     Игра Пуговицы. #15
А я сдал
Только написал не так.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.01.2010, 21:46     Игра Пуговицы.
Еще ссылки по теме:

C++ Игра на C++
C++ Игра слов, игра Scrabble
C++ Игра
2Д-игра C++
Игра C++

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

Или воспользуйтесь поиском по форуму:
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
09.01.2010, 21:46     Игра Пуговицы. #16
Цитата Сообщение от outoftime Посмотреть сообщение
FOR(i,1,k)
здесь по сути 2 нужно.., попробуем как-то а то опять тимус висет начал..
Yandex
Объявления
09.01.2010, 21:46     Игра Пуговицы.
Ответ Создать тему
Опции темы

Текущее время: 22:56. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru