|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
22.11.2009, 13:58 | #1 | |
ACM!
Форумчанин
Регистрация: 19.06.2009
Сообщений: 382
|
Как определить, что игроки играют оптимально?
Вот задачка:
Цитата:
Вопрос - как определить, что игроки играют оптимально? Я могу получить список всех решений, но какое из них оптимальное - для меня загадка... |
|
22.11.2009, 14:15 | #2 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Оптимальное решение - не совсем верное определение для теории игр. Оптимальная стратегия - стратегия, позволяющая достичь оптимального для даного игрока результата. Проще говоря, Ваше задание - определить исход игры, если оба противника будут действовать наилучшим образом.
Я бы не советовал сейчас такое решать. Вы готовитесь к районной олимпиаде, а на районной олимпиаде не бывает настоящих задач. Это - задача. Не особо сложная, но задача. А Вам сейчас для наилучшего результата надо набить руку на кодинговых упражнениях. З.Ы. надо будет в ближайшем будущем ее здать, а то эту задачу я еще не написал |
22.11.2009, 14:20 | #3 |
ACM!
Форумчанин
Регистрация: 19.06.2009
Сообщений: 382
|
Ну если можно, просто объясните решение (охота знать сам принцип)
|
22.11.2009, 14:32 | #4 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Я бы ее писал 2-д динамикой, похожей на Шпрага-Гранди таблицу. Тоесть снизу вверх определеям для каждой позиции значения игровой функции подстроки, а потом уже динамим эту таблицу.
|
23.11.2009, 22:31 | #5 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Все, написал, сдал, прошло. 2-д динамика показала
Pascal Accepted * 0,072 988 Кб Следовательно, я был прав, и такое решение подходит. Этой задачей закрыл первую страницу, из задач с номерами 1-50 она у меня была последней не сданой, как выяснилось (просто обычно сортирую по сложности, а не по номеру). После сдачи сел обсуждение читать - согласен с постами там, задача действительно несколько раз проскакивала на ИОИ. Отгуглил старые ИОИ, если хотите понять само задание более правильно и четко, то взгляните на IOI'96 Day 1 Problem 1: A Game. Там суть более доступно выложена, чем в варианте, который Сергей Николаевич написал для АСМП. По поводу сложности задачи, хочу сказать, что она и сейчас не являеться столь простой для большинства новичков и кодеров "ниже среднего уровня" (как я уже говорил раньше, повторю еще раз "для закрепления"), хотя программирование и пошло далеко вперед, эта задача, которая была симплом (и одновременно сэмплом) межнара школьников по информатике 13 лет назад, и сейчас еще могла бы быть первой задачей ВсеРоса (что бы у всех были хоть какие-то баллы, на уровне ВсеРоса ее полностью или почти полностью сделает наверно бОльшая половина участников) или довольно неплохой (выше средней сложности) задачей на соревнованиях на 1 уровень ниже. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Как определить, что есть объединенные ячейки | Solyarka | Microsoft Office Word | 9 | 26.12.2009 07:42 |
Как определить, что форме перешел фокус? | Johnson | Общие вопросы Delphi | 4 | 20.11.2009 17:35 |
Как определить, что документ не сохранен? | viter.alex | Microsoft Office Word | 4 | 17.01.2009 09:23 |
Игра состоит в том, что игроки по очереди выбирают одну из карточек и передвигают свою фишку по ленте | sverhuVniz | Паскаль, Turbo Pascal, PascalABC.NET | 3 | 16.11.2008 02:46 |
вылетает в release build - как определить что не так? | DbIMKA | Общие вопросы C/C++ | 0 | 31.10.2008 20:18 |