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

C++

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

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

08.01.2010, 15:24. Просмотров 2899. Ответов 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++):

Как сделать так, чтобы при нажатии на кнопку "Новая игра" игра начиналась заново? - C++ Builder
Как сделать так, чтобы при нажатии на кнопку &quot;Новая игра&quot; игра начиналась заново? unit1.cpp void __fastcall TForm1::N1Click(TObject...

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

Игра - C++
Есть вопрос, но не знаю даже как правильно спросить. Написал логику игры &quot;Змейка&quot;. Теперь переношу на WinApi (писал на консоль). ...

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

Игра - C++
Помогите решить следующую задачу: Написать программу, которая отгадывает задуманное число в интервале за n вопросов типа &quot;Ваше число,...

игра (с++) - C++
Здравствуйте! Нужно составить игру про шарики. Если в линии встречаются 3 или больше одинаковых цветов шарико, то нужно этот ряд шаров...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
outoftime
║XLR8║
509 / 431 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
08.01.2010, 15:27 #2
В принцыпе, можно было бы свести все к Ним, но я эт делать не умею.. Но по сути, нужно думать по логике, типа мы выиграем, если сделаем ход, который будет проиграшным для в-ого игрока..
odip
Эксперт С++
7157 / 3297 / 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║
509 / 431 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
08.01.2010, 15:35 #4
это и есть сведение к Ним, спасибо
odip
Эксперт С++
7157 / 3297 / 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║
509 / 431 / 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
Эксперт С++
7157 / 3297 / 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║
509 / 431 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
08.01.2010, 15:42 #8
odip, задача с рюкзаком и т.д. - не мой конек..
если не очень затрудняет, можешь посмотреть задачу, называется "квадратная страна"
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
08.01.2010, 15:43  [ТС] #9
Хочешь чтобы я за тебя все задачи там прорешал ?
outoftime
║XLR8║
509 / 431 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
08.01.2010, 15:45 #10

Не по теме:

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



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

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

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

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

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

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

Игра на С++ - C++
Ну в общем нужна вам или нет, но всё равно выложу:) Это крестики-нолики. #include &lt;graphics.h&gt; #include &lt;stdlib.h&gt; #include...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
09.01.2010, 19:00
Ответ Создать тему
Опции темы

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