0

Добрый день еще раз! Попробовал решить задачу на тему "игра Баше" как сразу столкнулся с проблемой при тестировании. Вот здесь можно прочитать условие задачи: http://www.e-olimp.com/problems/1005

Children of a match is not a toy!

On the table there are N matches. They play two, take turns. A player may take no more than M matches, but not less than one. Took away the last match wins.

Who will win in the regular game - the first or second player?

Input

In the first line is the number of T - the number of test cases. In the following T lines are two numbers, separated by a space: N - number of matches in the pile and M - the maximum allowed for the capture of one move.

1 ≤ T ≤ 100, 1 ≤ N, M ≤ 2·109.

Output

In a single line display a sequence of ones and twos T, 1 - for the case if the right wins the first game and, respectively, 2 - if the player wins the second.

Вот код задачи:

 #include <iostream>

using namespace std;

int main()
{
    int T; // кол-во тестов
    cin >> T;
    int n,m; // кол-во спичек в пучке; макс.кол-во спичек, разрешенное за 1 ход
    int sum; // сюда мы складываем все кол-во спичек и далее оперируем этой суммой
    for (int i = 0; i < T; ++i) // цикл для кол-ва заданых тестов
        {
            cin >> n >> m; // вводим
            int sum = n; // буду постоянно отнимать нужное кол-во спичек за ход
            int igrok = 0; // счетчик, который определяет какой игрок походил
            while ( sum > 0 ) // второй цикл - пока сумма всех спичек больше нуля игра будет продолжаться, иначе игра закончится и кто-то выйграет
                {
                    int lol = 0; // ромежуточное значение (для суммы), где хранится кол-во спичек, которые убираеются из кучи
                    if (sum % m+1 == 0) {sum -= m; igrok++; } // если кратно m+1: тогда из суммы вычитаем любое кол-во спичек (в данном случе - максимум)
                    else { lol = sum % m+1; sum -= lol; igrok++; } // иначе: находим промежут.значение и вычитаем его из общ.суммы
                    //igrok++;
                }
            if (igrok % 2 == 0) {cout << 2;} // если igrok кратно двум - выйграл второй игрок
            else {cout << 1;} // иначе: выйграл первый
        }
}

А вот тест к задаче: Входные данные :

2
7 3
8 3

Выходные данные:

12

А у меня выходит в ответе :

11

Прошу помочь с решением!

1 ответ 1

6

такие задачи решаются без цикла. Стратегия обычно простая. Если число нацело делиться на кол-во спичек за ход+1, тогда выиграет второй. Если нет, то первый берет остаток и выиграет. Поэтому, алгоритм решения на самом то деле очень простой - прочитать два числа (пусть это будет a и b) и вывести a % (b +1) != 0?1:2;

Решение в лоб:

#include <iostream>

int main()
{
    int n, a, b;
    std::cin >> n;
    for (int i = 0; i < n; i++) {
      std::cin >> a >> b;
      int r = a % (b + 1);
      std::cout << (r==0?2:1);
    }
    std::cout << std::endl;
    return 0;
}
6
  • Спасибо за решение. Хотя оно и очень простое, но его нужно знать, что бы решить задачу :) Только у меня вопрос: что значит строка: "std::cout << (r==0?2:1)" я понял, что это краткая запись: if-else, но мне не совсем ясно само условие. Почему r сравнивается с нулем?
    – hamsternik
    5 авг 2013 в 12:54
  • и все-таки на счет моего кода: что же там неверно - почему он выдает неверный ответ!? Я вроде все проверил - все правильно...
    – hamsternik
    5 авг 2013 в 12:55
  • ок, перепишу его сложнее if (r == 0) std::cout << "2"; else std::cout << "1"; Почему сравниваю с нулем? проверка на остаток. Если a % b == 0, то это значит, что a делится нацело на b. Для решения олимпиадных задач это нужно знать. По поводу Вашего кода. С квадратичной сложностью разбираться сложно. Поэтому, я просто рекомендую его выбросить, учитывая, что для этой задачи известна выигрышная стратегия.
    – KoVadim
    5 авг 2013 в 12:56
  • Подождите, может я чего-то не понял, но мне казалось,что условие "if (r == 0)" и "if (r % 2 == 0)" отличаются друг от друга. Разве нет? Как я вижу, в первом случае мы просто сравниваем полученное число с нулем, во втором же варианте: сравниваем остаток с нулем. Поправьте, если я что-то не то сказал
    – hamsternik
    6 авг 2013 в 10:59
  • просто потерялся %2 при переносе.
    – KoVadim
    6 авг 2013 в 11:26

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.