Задачка по "Теории игр"

@CF asker · Регистрация: 05.11.2014

Студворк — интернет-сервис помощи студентам

Экономическая игра "П&Т" (http://www.e-olymp.com/ru/problems/148)

Задано два неотрицательных целых числа A и B. Два игрока – Поставщик (П) и Транзитер (Т), ходят по очереди и придерживаясь наилучшей стратегии, играют в игру, в которой П всегда начинает первым. За один ход нужно от большего с чисел вычесть натуральное число, кратное меньшому, получив при этом неотрицательный результат. Проиграл тот, кто не смог сделать ход.

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

Первая строка – количество тестов 1 ≤ N ≤ 10. В последующих N строк по два числа в каждой – значения A и B (A, B < 2·109).

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

В единственной строке последовательность из N чисел 1 или 2, записанных подряд без пробелов, где 1, 2 - номера выигравших игроков (1 – выиграл П, 2 – Т).

Мое решение:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <fstream>
 
using namespace std;
short flag; // answer
 
void f(int a,int b,int c)
{
    if(b==1 && c%2==0)
    {
        flag=1; // end
        return;
    }
    else
        if(b==1 && c%2==1)      
            return;
    
    if(b==0)
        return;
 
    c++;
    int n;
    n=a/b; 
    int a1=a,b1=b;
    a1=a1-n*b1;
    if(a1<b1)
    {
        b1-=a1; a1+=b1; b1=a1-b1;
    }
    f(a1,b1,c);
    
 
    a1=a,b1=b;
    n=a/b-1; 
    if(n>0)
    {
        a1=a1-n*b1;
        if(a1<b1)
        {
            b1-=a1; a1+=b1; b1=a1-b1;
        }
        f(a1,b1,c);
    }
 
}
 
 
int main()
{
    ifstream in("input.txt");
    ofstream out("output.txt");
    int a,b,c=0;
    short t; // test
    in>>t;
    while(t>0)
    {
        flag=2;
        in>>a>>b;
        if(a<b)
        {
            b-=a; a+=b; b=a-b;
        }
        if(a%b==0)
            out<<1;
        else
        {
            f(a,b,c);
            out<<flag;
        }
        t--;        
    }
    return 0;
}

Оно довольно простое, проверка двух вариантов ( (int)n=a/b и n=a/b-1 ) до конца, а остальные варианты аналогичные.
Но результат - 70%. Не могу понять что не засчитывается, даже такой тест не подбирается.
В чем здесь проблема?
Может эту задачу можно и лучше делать не таким способом?

@CF asker · 13.01.2016, 00:41 **[ТС]**

Неужели никто не решал эту задачу с сайта? У нее все же 130 засчитанных решений

Новые блоги и статьи Все статьи Все блоги /
Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .
Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .

@CF asker 0 / 0 / 1 Регистрация: 05.11.2014 Сообщений: 48
	13.01.2016, 00:41 [ТС]
	Неужели никто не решал эту задачу с сайта? У нее все же 130 засчитанных решений 0