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

C++

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.61
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
#1

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

08.01.2010, 15:24. Просмотров 2850. Ответов 15
Метки нет (Все метки)

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     Игра Пуговицы.
Посмотрите здесь:

Игра - C++
Доброе время суток! Хочу написать свою первую, простую игру на С++. Посоветуйте с чего начать.

2D игра в С++ - C++ Builder
У меня вопрос по поводу работы с 2d графикой в С++ Я учусь на программиста и в этом году решил выбрать на курсовую работу игру. Игра...

Игра на C++ - C++
Здравствуйте! Интересует такой вопрос: При знаниях: Переменные, условия, циклы, функции, библиотеки в языке C++, можно ли создать...

Игра - C++
Создать программу со структурой player. Структура должна содержать поля level - для сохранения уровня игрока (начальное значение 1), ХР -...

Игра - C++ Builder
Я написал игру на 6 билдере . Всё вроде работает нром , но проблемка есть , никак не могу разобраться что не тка с выводом . Кто может мне...

Игра на C++ - Visual C++
Помогите написать игру на Visual C++! Нужна очень простенькая игра, можно с псевдографикой)) Заранее спасибо!

Игра на C++ - C++ Builder
Помогите, надо любую написаную игру в С++ (что-то в роде карт)ну кароче говоря несложную ...если есть у кого скиньте код пож....

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
outoftime
║XLR8║
506 / 428 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
08.01.2010, 15:27     Игра Пуговицы. #2
В принцыпе, можно было бы свести все к Ним, но я эт делать не умею.. Но по сути, нужно думать по логике, типа мы выиграем, если сделаем ход, который будет проиграшным для в-ого игрока..
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 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-ой игрок.
outoftime
║XLR8║
506 / 428 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
08.01.2010, 15:35     Игра Пуговицы. #4
это и есть сведение к Ним, спасибо
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 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.
outoftime
║XLR8║
506 / 428 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
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
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
08.01.2010, 15:39  [ТС]     Игра Пуговицы. #7
Кстати по условию игрок всегда может взять L==K-1
Так как K%(K-1+1)=K%K=0, то второй игрок всегда может подобрать L чтобы выиграть.
Программа пишется тривиально.
Если конечно раньше вы решали задачу про камни, то и эта задача решается тривиально.
outoftime
║XLR8║
506 / 428 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
08.01.2010, 15:42     Игра Пуговицы. #8
odip, задача с рюкзаком и т.д. - не мой конек..
если не очень затрудняет, можешь посмотреть задачу, называется "квадратная страна"
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
08.01.2010, 15:43  [ТС]     Игра Пуговицы. #9
Хочешь чтобы я за тебя все задачи там прорешал ?
outoftime
║XLR8║
506 / 428 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
08.01.2010, 15:45     Игра Пуговицы. #10

Не по теме:

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



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

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

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

2D игра на C/C++ - C++
Вообщем задача не из простых (лично для меня) , т.к. что-то могу , а чему-то мне нужно научиться . В институте задали курсовую работу -...

Простая игра 3D на C++ - C++
Здравствуйте! Я бы хотел попробовать написать простенькую 3D игру на C++. Физический движок мне не нужен, так как физики там сложной не...

Игра пятнашки - C++
Игра пятнашки в которой передвижение пустой клетки выполняется с помошью стрелочек

Игра восьмерки - C++
Доброго времени суток! Дали задание найти решение игры восьмерки (как пятнашки только меньше) Исходное поле типа: 3 4 6 1 0 2 8 9 7...

Игра Лабиринт - C++
В лабиринте средством перемещения так сказать &quot;персонажа&quot; являются стрелки.Помогите пожалуйста сделать так чтобы стена была стеной...


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

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

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