Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.94/18: Рейтинг темы: голосов - 18, средняя оценка - 4.94
 Аватар для Хадукен
1 / 1 / 5
Регистрация: 01.08.2016
Сообщений: 71

Антагонистические игры двух лиц, програмама не проходит 3 тест

07.08.2016, 14:22. Показов 3731. Ответов 11

Студворк — интернет-сервис помощи студентам
Задача:
Кликните здесь для просмотра всего текста
Теория игр

(Время: 1 сек. Память: 16 Мб Сложность: 28%)
Одним из интересных объектов, изучаемых в теории игр, являются так называемые антагонистические игры двух лиц. Такие игры характеризуются множеством X стратегий первого игрока, множеством Y стратегий второго игрока и функцией выигрыша K(x, y) (x из X, y из Y). Если множества стратегий X и Y конечны, то такую игру принято называть матричной, так как функцию выигрыша K в этом случае удобно задавать матрицей.

Рассмотрим матричную игру, в которой X = {1,…,n}, Y = {1,…,m}. Матрицу выигрышей обозначим символом K. Нижним значением игры назовем число maxi=1..nminj=1..m Kij . Верхним значением игры назовем число minj=1..mmaxi=1..n Kij. Отметим также, что игры, у которых нижнее и верхнее значение совпадают, называются играми с седловой точкой.

Задана матрица выигрышей K для некоторой матричной игры. Найдите ее верхнее и нижнее значение.

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

Первая строка входного файла INPUT.TXT содержит целые числа n и m (1 ≤ n,m ≤ 100). Далее следуют n строк по m чисел в каждой. j-ое число i-ой строки равно Kij . Все Kij по модулю не превосходят 1000.

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

В выходной файл OUTPUT.TXT выведите нижнее и верхнее значение игры через пробел.
Пример
input.txt
3 3
4 -1 -3
-2 1 3
0 2 -3

output.txt
-2 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
#include <iostream>
 
using std::cout;
using std::cin;
 
int main()
{
    int n,m,h,a,b,c,d;
        //h-очередной элемент, a-максимум в строке, b-минимум в строке
        //c-минимум в столбце из максимумов в строках
        //d-максимум в столбце из минимумов в строках
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>a;
        b=a;
        for(int j=1;j<m;j++)
        {
            cin>>h;
            if (h>a) a=h;
            if (h<b) b=h;
        }
        if (i==0) {c=a;d=b;}
        else 
        {
            if (c>a) c=a;
            if (d<b) d=b;
        }
    }
    cout<<d<<" "<<c;
    return 0;
}
Программа не проходит третий тест. Не могу понять в чем причина. Скорее всего, я неверно понял суть задачи. Помогите понять условие задачи!

Добавлено через 6 минут
В решении я не использую массив, потому что без него программа работает эффективнее(правда ведь?).
0
Лучшие ответы (1)
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
07.08.2016, 14:22
Ответы с готовыми решениями:

Тест на интеллект. Спорим, вы не угадаете больше 25 известнейших лиц?!
http://www.aif.ru/contestappl/kartina

X,y,z не проходит 9 тест
Однажды, посетив магазин канцелярских товаров, Вася купил X карандашей, Y ручек и Z фломастеров. Известно, что цена ручки на 2 рубля больше...

Не проходит тест
Не проходит тест на соответствие. Вроде пишет, что Результат Сообщение: Ошибка в Assert.AreEqual. Ожидается: &lt;System.String&gt;....

11
 Аватар для HenryDukart
125 / 125 / 44
Регистрация: 05.10.2013
Сообщений: 462
07.08.2016, 15:09
Хадукен, очень трудно понять ваш код с такими именами переменных.

Нижнее значение — это в каждой строке выбираете минимальный элемент и из них берете максимальный.
Верхнее — в каждом столбце находите максимальный и из них берете минимальный.

Если нижнее значение можно найти без дополнительного массива, то для верхнего уж придется завести.
1
 Аватар для avgoor
1550 / 877 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
07.08.2016, 15:33
Цитата Сообщение от HenryDukart Посмотреть сообщение
можно найти без дополнительного массива, то для верхнего уж придется завести
Это еще почему?
0
 Аватар для Хадукен
1 / 1 / 5
Регистрация: 01.08.2016
Сообщений: 71
07.08.2016, 15:35  [ТС]
Сделал более понятные переменные:
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
#include <iostream>
 
using std::cout;
using std::cin;
 
int main()
{
    int n,m,h,max1,min1,max2,min2;
        //h-очередной элемент, max1-максимум в строке, min1-минимум в строке
        //max2-минимум в столбце из максимумов в строках
        //min2-максимум в столбце из минимумов в строках
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>max1;
        min1=max1;
        for(int j=1;j<m;j++)
        {
            cin>>h;
            if (h>max1) max1=h;
            if (h<min1) min1=h;
        }
        if (i==0) {max2=max1;min2=min1;}
        else 
        {
            if (max2>max1) max2=max1;
            if (min2<min1) min2=min1;
        }
    }
    cout<<min2<<" "<<max2;
    return 0;
0
 Аватар для HenryDukart
125 / 125 / 44
Регистрация: 05.10.2013
Сообщений: 462
07.08.2016, 15:45
Цитата Сообщение от avgoor Посмотреть сообщение
Это еще почему?
Потому что файл считывается построчно.
0
 Аватар для Хадукен
1 / 1 / 5
Регистрация: 01.08.2016
Сообщений: 71
07.08.2016, 15:49  [ТС]
Мне точно известно, что задача может быть решена за один просмотр.
0
 Аватар для HenryDukart
125 / 125 / 44
Регистрация: 05.10.2013
Сообщений: 462
07.08.2016, 16:07
Хадукен, avgoor, да, скорее всего я не прав.

Добавлено через 7 минут
Хадукен, мне кажется, что у вас верный алгоритм.Самому стало интересно узнать, где ошибка.

Кажется понял, в чем проблема. Вот тест: (матрица 2 на 2)

1 2
1 2
1
 Аватар для Хадукен
1 / 1 / 5
Регистрация: 01.08.2016
Сообщений: 71
07.08.2016, 16:17  [ТС]
HenryDukart, программа выдает ответ :
1 2
Мне кажется что это логичный ответ,потому что 1 - это максимальное число, среди минимальных в каждой строке, а 2 - это минимальное число, среди максимальных в каждой строке. Тесты, которые я способен придумать, программа выполняет верно, но меня всё чаще посещает мысль, о том что в этой задаче нужно находить что-то другое.
0
 Аватар для HenryDukart
125 / 125 / 44
Регистрация: 05.10.2013
Сообщений: 462
07.08.2016, 16:27
Лучший ответ Сообщение было отмечено Хадукен как решение

Решение

Хадукен, перечитайте мой пост номер 2. Ответ должен быть 1 1.

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
#include <iostream>
 
using std::cout;
using std::cin;
 
int main()
{
    int n, m, h, max = INT_MIN, min;
    //max - максимальный из минимумов в каждоый строке
    //min - минимум в просаматриваемой строке
    cin >> n >> m;
    
    int *max_in_col = new int[m];
    for (int i = 0; i < m; ++i)
        max_in_col[i] = INT_MIN;
 
    for (int i = 0; i < n; i++)
    {
        min = INT_MAX;
        for (int j = 0; j < m; j++)
        {
            cin >> h;
            if (h < min) min = h;
            if (h > max_in_col[j]) max_in_col[j] = h;
        }
        if (min > max) max = min;
    }
 
    //в min помещаем минимум из максимумов в столбце
    min = max_in_col[0];
    for (int j = 0; j < m; ++j)
        if (max_in_col[j] < min)
            min = max_in_col[j];
 
    cout << max << " " << min;
 
    delete[] max_in_col;
    return 0;
}
1
 Аватар для Хадукен
1 / 1 / 5
Регистрация: 01.08.2016
Сообщений: 71
07.08.2016, 17:41  [ТС]
Аллилуя!!! Перечитал условие 10 раз и заметил, что нижнее значение игры - это maxi_minj, а верхнее значение игры - это minj_maxi! Это означает, что искать верхнее значение игры - это минимум среди максимумов каждого из столбцов!
Теперь моя уверенность, в том что задача решается без массива, разрушена.

Добавлено через 1 час 3 минуты
HenryDukart, спасибо, дружище! Accepted!!!
Не стал воровать твой код, написал по своему:
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
#include <iostream>
 
using std::cin;
using std::cout;
 
int main()
{
    int h,n,m,max,min1,min2;
    cin>>n>>m;
    int *A=new int[m];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>h;
            if (i==0||A[j]<h) A[j]=h;
            if (j==0||min1>h) min1=h;
        }
        if (i==0||min1>min2) min2=min1;
    }
    max=A[0];
    for(int i=1;i<m;i++)
        if (max>A[i]) max=A[i];
    cout<<min2<<" "<<max;
    delete [] A;
    return 0;
}
Добавлено через 3 минуты
Даже в топ 20 попал.(Учитывая питонщиков)
0
 Аватар для HenryDukart
125 / 125 / 44
Регистрация: 05.10.2013
Сообщений: 462
07.08.2016, 17:56
Хадукен, можете еще массив объявить статическим, чтобы не вызывать операцию new и delete.
0
 Аватар для Хадукен
1 / 1 / 5
Регистрация: 01.08.2016
Сообщений: 71
07.08.2016, 18:05  [ТС]
HenryDukart, максимально сократил код, среди С++ первый.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
07.08.2016, 18:05
Помогаю со студенческими работами здесь

Программа не проходит тест
Нужно было сделать программу для определения, является ли десятичная дробь конечной при переводе в двоичную СС. Если да, то перевести и...

Код не проходит тест
https://open.kattis.com/problems/runlengthencodingrun задание. Суть закодировать информация или декодировать. Например, aaassd будет...

Не проходит стресс тест
Ryzen 3600 RX 5700 (реф) БП be quiet! PURE POWER 11 600W Мать AORUS PRO GIGABYTE Кулер AARDWOLF Performa 10X (Да, я уже пожалел,...

Не проходит последний тест
#include&lt;iostream&gt; #include&lt;string&gt; #include&lt;cmath&gt; using namespace std; int main() { int a, b, c; cin &gt;&gt; a &gt;&gt; b &gt;&gt; c; ...

Задача не проходит тест
Добрый день. Есть такая простая задача. /* Нужно добавить в программу новую функциональность Задача: У каждой кошки есть имя и...


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

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Новые блоги и статьи
Идея фильтра интернета (сервер = слой+фильтр).
Hrethgir 31.03.2026
Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .
Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда
anaschu 31.03.2026
В прикрепленном документе раздумья о том, как можно поменять модель в будущем
10 пpимет, которые всегда сбываются
Maks 31.03.2026
1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .
Перемещение выделенных строк ТЧ из одного документа в другой
Maks 31.03.2026
Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .
Functional First Web Framework Suave
DevAlt 30.03.2026
Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .
Автоматическое создание документа при проведении другого документа
Maks 29.03.2026
Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .
Настройка движения справочника по регистру сведений
Maks 29.03.2026
Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .
Автозаполнение реквизита при выборе элемента справочника
Maks 27.03.2026
Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru