Задача 1. «Парадокс заключенного»
Условие
Легенда, на которой основана эта задача, гласит о двух задержанных преступниках, против которых нет серьезных улик. Их рассаживают по разным камерам и пытаются добиться от них подробностей про соучастника. Всего возможно четыре варианта развития событий. Если оба рассказывают друг про друга, то их ждет серьезное наказание, которое немного смягчится за счет чистосердечного признания (в нашем случае это начисление 1 балла каждому). Если один дает показания, а другой молчит, то разговорчивый идет на свободу, а молчаливый садится всерьез и надолго (5 и 0 баллов соответственно). Если оба молчат, то их наказывают не так серьезно, опираясь всего лишь на имеющиеся доказательства (по 3 балла каждому).
Подсказка
Естественно, если игра идет один период, то выгоднее давать показания. Несложно доказывается, что и для любого известного количества периодов тоже надо давать показания каждый раз. Гораздо интереснее, когда количество периодов заранее неизвестно. В таком случае можно добиться большего количества очков, если иногда отказываться давать показания (это и есть парадокс). Т.е. анализировать действия и реакцию противника. В общем виде стратегия понятна: обманывать «доверчивых» (тех, кто часто молчит), договариваться с «вменяемыми» (с теми, кто также стремится к взаимовыгодному сотрудничеству) и не поддаваться на удочку «обманщиков» (тех, кто постоянно дает против нас показания).
Задание
Задача – разработать программу, которая будет играть в «парадокс заключенного» с программой-противником.
Входные данные
Ваша программа будет получать на вход файл paradox.in. В первой строке содержится целое число N (N <= 1000) – количество сыгранных периодов. В следующих N строках содержатся предыдущие ходы программы, по одному слову в строке. Каждый ход представляет собой слово “YES” (дать показания) или “NO” (молчать). Затем следуют N строк в том же формате, содержащие ходы противника.
Выходные данные
Выходной файл paradox.out должен содержать одно слово “YES” или “NO” – очередной ход вашей программы.
Пример входных данных:2
YES
YES
NO
NO
Пример выходных данных:NOОценка
Решения будут оцениваться аналогично футбольным чемпионатам: случайным образом все решения делятся на группы по 4, затем в группе сравниваются каждое с каждым и 2 решения, набравшие большие суммы баллов, выходят в следующий тур. Перед следующим туром все вышедшие в него решения снова случайным образом делятся на четверки и так далее. Баллы, набранные решениями, суммируются с самого первого тура. Максимальная сумма баллов, набранная каким-либо решением, принимается за абсолютную величину, остальным участникам начисляются коэффициенты относительно этой величины. В каждой игре количество периодов одинаково, но заранее неизвестно участникам.
Задача 2. Игра “Просто Филя”
Условие
Дано прямоугольное клеточное поле 41´45 клеток. Каждая клетка покрашена в один из шести цветов. Цвета пронумерованы от 1 до 6. Левая верхняя и правая нижняя клетки поля имеют различный цвет. В результате поле разбивается на некоторое количество одноцветных областей. Две клетки одного и того же цвета, имеющие общую сторону, принадлежат одной и той же области. Играют два игрока. За первым игроком закреплена область, включающая левую верхнюю клетку, за вторым – правую нижнюю. Игроки ходят по очереди. Делая ход, игрок перекрашивает свою область в любой из шести цветов по своему выбору, за исключением цвета своей области и цвета области противника. В результате хода к области игрока присоединяются все прилегающие к ней области выбранного цвета, если такие имеются (на рисунке изображена раскраска левого верхнего угла поля до хода первого игрока и после него).| 3 | 4 | 4 | 5 | 6 | 6 | 6 | |
| 3 | 3 | 5 | 5 | 6 | 6 | 1 | |
| 4 | 3 | 5 | 6 | 2 | 4 | 6 | |
| 2 | 6 | 5 | 6 | 5 | 4 | 6 | |
| 2 | 4 | 3 | 2 | 6 | 5 | 6 | |
| 3 | 6 | 6 | 1 | 1 | 1 | 1 | |
| 5 | 4 | 4 | 5 | 6 | 6 | 6 | |
| 5 | 5 | 5 | 5 | 6 | 6 | 1 | |
| 4 | 5 | 5 | 6 | 2 | 4 | 6 | |
| 2 | 6 | 5 | 6 | 5 | 4 | 6 | |
| 2 | 4 | 3 | 2 | 6 | 5 | 6 | |
| 3 | 6 | 6 | 1 | 1 | 1 | 1 | |
Цель игры – включить в свою область как можно больше клеток. Игра заканчивается, когда все поле разобьется на две области или в течение четырех ходов ни одна область не увеличилась.
Задание
Написать программу, которая по текущему состоянию поля делает один ход за первого игрока. Программа будет участвовать в тестовой игре следующим образом:· по данным входного файла программа выбирает номер цвета, записывает его в выходной файл и заканчивает свою работу;· тестирующая система по выбранному цвету перекрашивает область первого игрока, делает ответный ход и вновь запускает вашу программу, предоставляя ей в качестве начальных данных измененное поле;· программа будет запускаться до тех пор, пока тестовая игра не завершится;· в случае некорректного хода программы тестовая игра завершается досрочно.
Входные данные
Входной файл filya.in содержит 41 строку по 45 цифр в каждой без пробелов. Первая цифра файла соответствует цвету левой верхней клетки игрового поля. Вам предоставляется пример входного файла.
Выходные данные
Выходной файл filya.out содержит номер цвета хода.
Пример выходного файла
5
Примечание
Для отладки своей программы вы можете воспользоваться программой filya.exe, правила работы с которой описаны в файле read.me.
Подсказка
Эта задача из разряда классических игр типа крестики-нолики, шашки, шахматы, и при ее решении следует использовать похожие методы. Точного решения для нее не существует, можно подойти к решению эвристически, тут все ограничивается только фантазией автора.Обычно такие задачи решаются с помощью так называемых минимаксных деревьев с оценочной эвристической функцией. Те, кто это знает, могут биться над функцией, а для остальных эта задачка будет еще интереснее, так как здесь можно много чего придумать.Оценка
Качество вашей программы будет оцениваться в зависимости от количества клеток в вашей области после завершения тестовой игры.Для проверки будут использоваться несколько игровых полей (10).Программы последовательно играют друг с другом на каждом из полей. Для каждого поля выбирается лучшая программа – та, которая показала на этом поле лучший результат. Затем каждая программа играет на каждом поле с лучшей. Коэффициент начисляется относительно балла, набранного на этом поле лучшей программой.Задача 3. «Выборы»
Условие
Затерянное на просторах Океании племя Тумба-Юмба решило выбрать себе вождя. Незнакомое с демократическими достижениями цивилизации, племя использовало немного нестандартный механизм выборов, связанный с особыми традициями и образом жизни.Каждый человек здесь четко знает свой авторитет (целое число от 1 до 10 000, все авторитеты в племени различны). По традиции вождь должен быть выбран единогласно и обладать самым высоким авторитетом в племени. Еще одна особенность состоит в том, что каждый Тумба-Юмбинец живет на своем острове и не все они могут общаться между собой (т.е. для каждого жителя племени известно, с кем он может общаться). Процесс передачи информации – очень трудоемкий, поэтому наша задача будет состоять в том, чтобы каждый житель узнал, кто же вождь (и это был человек с наибольшим авторитетом), и при этом количество сообщений было как можно меньшим.Задание
Ваша программа должна описывать поведение одного жителя племени, чтобы во взаимодействии с другими жителями (экземплярами той же программы с другими входными данными) определить, кто же является вождем, и использовать при этом наименьшее суммарное количество обменов сообщениями.Входные данные
Вашей программе на вход будут подаваться три файла:· info.in – файл с информацией о данном жителе племени. В первой строке он содержит два числа – номер жителя (целое число от 1 до 100) и его авторитет (число от 1 до 10 000 каждое). Во второй строке содержится целое число от 1 до 100 – количество «соседей». В третьей строке перечислены номера соседей через пробел – целые числа от 1 до 100.· memory.in – файл, хранящий «память» данного жителя. При первом запуске файл будет пуст, при любом другом запуске он будет содержать то, что ваша программа записала себе в память в прошлом периоде. Формат файла произвольный, но его размер не превышает 10 Кбайт.· messages.in – файл с сообщениями, переданными в прошлом периоде от соседей. От каждого соседа за один период может поступить не более одного сообщения. В первой строке содержится количество сообщений. Каждое из них содержит две строки. В первой находится целое число, обозначающее номер человека, от которого получено сообщение, вторая – собственно сообщение в произвольном формате (без символов перевода строки) длиной до 1 Кбайт. При первом запуске файл содержит число 0.Выходные данные
Программа должна создать два файла:· memory.out – это «память» данного человека, которая будет доступна вашей программе на следующем периоде. Формат файла произвольный, но его длина не должна превышать 10 Кбайт.· messages.out – файл, содержащий сообщения, которые будут посланы вашей программой соседям. В первой строке должно содержаться целое число – количество сообщений. Каждое сообщение описывается двумя строками аналогично сообщению в файле messages.in.Если программа считает, что выбрала вождя, формат файла messages.out должен быть следующим: в первой строке содержится число -1, а во второй – номер вождя.Пример входных файлов
Файл info.in не изменяется на протяжении работы программы.Пусть он будет таким:1 100121 этап:Файл memory.in пуст, messages.in содержит число 0.Программа создает пустой файл memory.out и создает файл messages.out следующего вида:121 authority is 1002 этап:Файл memory.in по-прежнему пуст, а файл messages.out пусть имеет такой вид:122 authority is 200Пример выходного файла
Пусть наша программа решила, что нашла вождя, и создает файл messages.out в следующем виде-12Оценка
Для оценки каждая программа должна выполнить десять тестовых заданий. Для каждой программы будет считаться количество выполненных действий. Чем их меньше, тем больше коэффициент.Коэффициенты вычисляются для каждого теста относительно лучшей в нем программы, а затем суммируются по всем тестам. При этом, если хотя бы один экземпляр неправильно выбрал вождя, программа автоматически получает за тест 0 баллов.