|
1 / 1 / 5
Регистрация: 01.08.2016
Сообщений: 71
|
||||||
Антагонистические игры двух лиц, програмама не проходит 3 тест07.08.2016, 14:22. Показов 3731. Ответов 11
Задача:
Кликните здесь для просмотра всего текста
Теория игр Одним из интересных объектов, изучаемых в теории игр, являются так называемые антагонистические игры двух лиц. Такие игры характеризуются множеством X стратегий первого игрока, множеством Y стратегий второго игрока и функцией выигрыша K(x, y) (x из X, y из Y). Если множества стратегий X и Y конечны, то такую игру принято называть матричной, так как функцию выигрыша K в этом случае удобно задавать матрицей.(Время: 1 сек. Память: 16 Мб Сложность: 28%) Рассмотрим матричную игру, в которой 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 Мой код решения:
Добавлено через 6 минут В решении я не использую массив, потому что без него программа работает эффективнее(правда ведь?).
0
|
||||||
| 07.08.2016, 14:22 | |
|
Ответы с готовыми решениями:
11
Тест на интеллект. Спорим, вы не угадаете больше 25 известнейших лиц?!
Не проходит тест |
|
125 / 125 / 44
Регистрация: 05.10.2013
Сообщений: 462
|
|
| 07.08.2016, 15:09 | |
|
Хадукен, очень трудно понять ваш код с такими именами переменных.
Нижнее значение — это в каждой строке выбираете минимальный элемент и из них берете максимальный. Верхнее — в каждом столбце находите максимальный и из них берете минимальный. Если нижнее значение можно найти без дополнительного массива, то для верхнего уж придется завести.
1
|
|
|
1550 / 877 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
|
|
| 07.08.2016, 15:33 | |
|
0
|
|
|
1 / 1 / 5
Регистрация: 01.08.2016
Сообщений: 71
|
||||||
| 07.08.2016, 15:35 [ТС] | ||||||
|
Сделал более понятные переменные:
0
|
||||||
|
125 / 125 / 44
Регистрация: 05.10.2013
Сообщений: 462
|
|
| 07.08.2016, 15:45 | |
|
0
|
|
|
1 / 1 / 5
Регистрация: 01.08.2016
Сообщений: 71
|
|
| 07.08.2016, 15:49 [ТС] | |
|
Мне точно известно, что задача может быть решена за один просмотр.
0
|
|
|
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
|
|
|
125 / 125 / 44
Регистрация: 05.10.2013
Сообщений: 462
|
||||||
| 07.08.2016, 16:27 | ||||||
Сообщение было отмечено Хадукен как решение
Решение
Хадукен, перечитайте мой пост номер 2. Ответ должен быть 1 1.
1
|
||||||
|
1 / 1 / 5
Регистрация: 01.08.2016
Сообщений: 71
|
||||||
| 07.08.2016, 17:41 [ТС] | ||||||
|
Аллилуя!!! Перечитал условие 10 раз и заметил, что нижнее значение игры - это maxi_minj, а верхнее значение игры - это minj_maxi! Это означает, что искать верхнее значение игры - это минимум среди максимумов каждого из столбцов!
Теперь моя уверенность, в том что задача решается без массива, разрушена. Добавлено через 1 час 3 минуты HenryDukart, спасибо, дружище! Accepted!!! Не стал воровать твой код, написал по своему:
Даже в топ 20 попал.(Учитывая питонщиков)
0
|
||||||
|
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
|
|
| 07.08.2016, 18:05 | |
|
Помогаю со студенческими работами здесь
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.
При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .
|