|
Название задачи: Сетевая игра. |
 |
Условие
|
Имя входного файла: |
net.in |
|
Имя выходного файла: |
net.out |
|
Максимальное время работы на одном тесте: |
1 секунда |
|
Максимальный объем используемой памяти: |
64 мегабайта |
|
Максимальная оценка за задачу: |
100 баллов |
Петя и Вася нашли на чердаке остатки рыболовной сети своего деда. Часть веревок давно сгнила, и сеть распалась на большое число кусков, каждый из которых состоит не более чем из 50 веревочек единичной длины.
Так как использовать по назначению остатки данной сети было уже нельзя, братья разложили один из найденных кусков на прямоугольном столе так, что веревочки оказались параллельны сторонам стола, и стали играть в следующую игру.
Братья делают ходы по очереди, Петя ходит первым. Своим ходом игрок находит веревочку, являющуюся стороной некоторой целой единичной квадратной ячейки сети (все четыре образующие ее веревочки целы), и перерезает выбранную веревочку. Проигрывает тот из братьев, который не может сделать очередной ход.
Требуется написать программу, которая по описанию куска сети на столе определяет, может ли Петя выиграть при любой игре Васи, и если да, то какой первый ход он должен для этого сделать.
Формат входных данных
В первой строке входного файла задано число N (1 ≤ N ≤ 50) - количество веревочек единичной длины, из которых состоит кусок сети. Следующие N строк входного файла содержат по две пары целых чисел - координаты концов веревочек. Каждая четверка чисел описывает отрезок единичной длины, параллельный одной из осей координат.
Координаты всех точек неотрицательны и не превосходят 50.
Формат выходных данных
Первая строка выходного файла должна содержать число 1, если Петя может выиграть при любой игре Васи, и число 2, если нет. В случае выигрыша Пети вторая строка должна содержать номер веревочки, которую он должен перерезать первым ходом. Если возможных выигрышных ходов несколько, выведите любой. Веревочки пронумерованы, начиная с 1, в том порядке, в котором они заданы во входном файле.
Примечание
Максимальная оценка за решение задачи при N ≤ 13 равна 40 баллам.
Пример
|
net.in |
net.out |
|
11 1 1 1 2 2 3 2 4 3 1 3 2 1 2 1 3 1 1 2 1 2 1 2 2 2 1 3 1 1 2 2 2 2 2 3 2 1 3 2 3 2 3 3 3 |
1 6 |
Решение
Тесты и проверяющая программа
Решения, написанные членами научного комитета и жюри Всероссийской олимпиады
Разбор задачи "Сетевая игра".
В качестве вводного замечания скажем, что игра всегда завершается победой либо первого, либо второго игрока. По правилам игры ничья никогда получиться не может.
Уровень сложности 1 (40 баллов)
В данной задаче было выделено несколько уровней сложности. Сначала рассмотрим задачу в самой простой формулировке, в которой количество веревочек ограничено 13.
Из-за такого ограничения на количество верёвочек оказывается, что возможно небольшое число конфигураций. Самое большое число ячеек сети, которые могут быть образованы 13 верёвочками, равно 4. Эти ячейки могут образовывать фигуры, хорошо известные по игре "Тетрис", и их подфигуры. Все они приведены ниже.
Эти фигуры являются одной компонентной связности каждая. Но поскольку, например, одиночный квадратик использует всего 4 верёвочки, мы можем комбинировать несколько одиночных квадратиков и фигур из двух клеток, связывая их верёвочками, которые не образуют новых ячеек сети. Таким образом, мы получим ещё несколько конфигураций игры, каждая из которых приведена ниже.
Все конфигурации приведены здесь без учёта возможных поворотов и отражений. Естественно, если в какой-либо конфигурации у нас остались верёвочки, мы можем их потратить, "подвешивая" их к верёвочкам, образующим ячейки сети. В частности, мы можем получить следующие конфигурации.
Третья конфигурация на рис. выше использует все 13 верёвочек, которые не образуют ни одной ячейки сети.
Построив все возможные конфигурации верёвочек можно вручную посчитать исход игры для каждой из возможных конфигураций. Получается, что если рассматривать фигурки тетриса, то единственной проигрышной конфигурацией является квадрат 2x2. Из "составных" конфигураций проигрышной является конфигурация из 2 одиночных клеток и без клеток вообще.
Теперь, вручную просчитав исход игры для всех возможных конфигураций, мы можем написать программу, которая будет отождествлять конфигурацию верёвочек во входном файле с одной из конфигураций, описанных выше. Жюри предполагало, что правильно написанное подобное решение должно набирать 40 баллов.
Уровень сложности 2 (70 баллов)
Очевидно, что с ростом количества ниточек, ручной разбор возможных конфигураций становиться практически невозможным, и нам требуются способы алгоритмического вычисления исходов игры.
Попробуем находить решение перебором по верёвочкам. Любая конфигурация, появляющаяся в процессе игры, отличается от начальной конфигурации только отсутствием некоторых верёвочек, разрезанных в процессе игры. Мы можем занумеровать все верёвочки числами от 0 до N-1. Тогда, поскольку нам известно начальное расположение верёвочек, любое состояние верёвочек, возникающее в процессе игры, описывается набором из N нулей и единиц, то есть N-битным числом. Начальное состояние описывается числом из всех 1.
Мы можем организовать перебор с возвратом от начальной конфигурации. На каждом уровне перебора мы пробуем отрезать каждую из оставшихся верёвочек, и если для некоторой верёвочки такой ход является допустимым, запускается рекурсивный поиск решений для новой конфигурации.
На каждом шаге перебора нам необходимо знать, какой из игроков ходит. На ходе первого игрока он выигрывает, если существует хотя бы один ход, который переводит игру в конфигурацию, проигрышную для второго игрока, первый игрок проигрывает, если при любом его ходе получается конфигурация, выигрышная для второго игрока. Аналогичные правила действуют и для хода второго игрока. Сформулированные правила выигрыша первого игрока позволяют нам сформулировать эвристику сокращения перебора, известную как αβ-отсечение, а именно, как только на ходе первого игрока мы находим ход, на котором он выигрывает, нам совсем не требуется перебирать оставшиеся ходы, вместо этого мы можем завершить работу функции немедленно, сформировав возвращаемое значение, соответствующее выигрышу первого игрока. Точно также мы сокращаем перебор и для второго игрока.
Такая эвристика очень просто программируется (буквально добавлением одного оператора if и break в тело цикла), но для данной игры даёт очень хороший результат, позволяя сократить количество просматриваемых конфигураций примерно в 2 раза.
Мы можем немного ускорить работу программы, если перед началом перебора удалим все верёвочки, которые не являются границей никакой ячейки сети. Для этого проще всего построить ячейки сети на координатной плоскости (благо, что ограничения на координаты это позволяют), а затем посмотреть, является ли каждая верёвочка границей какой либо ячейки. В цикле по всем верёвочкам для каждой вертикальной верёвочки мы прибавляем 1 к клеткам, расположенной слева и справа от неё, а для каждой горизонтальной верёвочки мы прибавляем 1 клеткам, расположенным сверху и снизу от верёвочки. Те клетки, в которых после цикла записано число 4, являются целыми ячейками сети.
Особой аккуратности требует работа с верёвочками, координаты которых находятся на границе диапазона допустимых координат. Например, если мы рассмотрим вертикальную верёвочку с координатой x, равной 0, то для неё не существует клетки слева. Чтобы избежать излишних проверок координат, можно создать массив размера 52x52 вместо 50x50. Для программ на Паскале этого можно добиться, объявив массив как array [-1..51] of integer. Такой приём недоступен для программирующих на Си, однако в можно добиться того же эффекта, объявив массив как int m[52][52], но прибавляя 1 к каждой координате при чтении конфигурации верёвочек из входного файла. Кстати, это даже будет более эффективно и для программ на Паскале, чем первый подход.
Тем не менее, вернёмся к организации перебора. Если на каждом шаге рекурсии после разрезания верёвочки сразу же удалять верёвочки, которые мы больше не можем использовать, так как они больше не являются границей целой ячейки сети, мы также получим некоторое ускорение.
Но самое главное улучшение следующее. Если мы рассмотрим ход работы алгоритма перебора, мы заметим, что перебор много раз попадает в одну и ту же конфигурацию. Возникает идея сохранить результат вычисления результата игры в данном состоянии для того чтобы, когда мы снова вернёмся в это же состояние, мы сможем взять уже вычисленное значение, а не выполнять весь рекурсивный обход по новой. Для каждого состояния верёвочек достаточно сохранять исход игры для первого игрока: 1 - если первый игрок выигрывает, 2 - если он проигрывает. Добавляя сюда 0 для ситуации, когда исход игры в данной конфигурации ещё неизвестен, мы получаем, что для каждого состояния игры достаточно хранить 1 байт информации (реально в нём будут использоваться только 2 бита). Если в некоторую конфигурацию мы попадаем на ходе второго игрока, исход игры для него будет противоположным чем тот, который сохранён в таблице, то есть 0 для 0 в таблице, 1 для 2 в таблице, 2 для 1 в таблице. Как уже было замечено выше, общее количество возможных состояний, которые могут возникать в процессе игры, равно 2^N, и, следовательно, для хранения всех состояний нам потребуется массив этого размера. Поскольку ограничение памяти для данной задачи установлено в 64 мб, под массив мы можем занять не более чем 32 мб памяти, что соответствует значению N равному 25.
Итак, если нам дано количество верёвочек, не превышающее 25, то мы можем реализовать рекурсивный поиск решения с отсечениями и запоминанием промежуточных результатов в таблице. Мы можем пытаться поднять это ограничение на N за счёт хранения информации от нескольких состояниях в одном байте, так мы получим максимальное N равное 27. С другой стороны, массив информации о состояниях игры достаточно разрежен, то есть большое количество конфигураций игры никогда не посещаются. Это позволяет нам использовать различные техники для хранения разреженных массивов, например, хэш-таблицы. В результате мы можем значительно поднять ограничение на максимальное количество верёвочек, но тогда мы столкнёмся с проблемой нехватки времени из-за того, что работа с разреженными массивами требует значительно больше времени, чем работа с обычными массивами.
Уровень сложности 3 (100 баллов)
Все соображения, изложенные выше, подталкивают нас к одному простому наблюдению. Игру можно рассматривать не только в терминах верёвочек, но в терминах целых ячеек сети. Мы можем за шаг игры удалить либо две смежных ячейки сети, либо одну ячейку при условии, что у неё меньше 4 соседей. Максимальное число ячеек в фигуре, которая состоит не более из 50 верёвочек равно всего 20. Это будет фигура прямоугольника 5x4, которая использует 49 верёвочек. Состоянием такой игры будет множество ещё целых ячеек сети. Если в начале игры было K ячеек, то всего состояний у такой игры не более чем 2^K. При максимальном значении K равном 20 мы легко можем создать массив требуемого размера.
Перебор по ячейкам сети организуется следующим образом: для каждой ячейки сети мы сначала пытаемся удалить сразу две ячейки: её и соседнюю с каждой из четырёх сторон ячейку. Если у ячейки меньше четырёх соседних ячеек, мы пытаемся удалить и саму ячейку. После каждого из возможных удалений мы запускаем рекурсию для новой конфигурации ячеек.
Некоторую сложность представляет восстановление номера верёвочки, которая является выигрышной для первого игрока, поскольку в переборе по ячейкам верёвочки никогда не возникают. Один из способов решить данную проблему √ запускать перебор не по ячейкам, а по верёвочкам, а на втором и последующих шагах работать только с ячейками.
Как и в случае перебора по верёвочкам, αβ-отсечение позволяет существенно ускорить перебор. Именно такое решение считалось полным и проходило все тесты.
Резюме полного решения
Итак, полное решение данной задачи должно состоять из следующих этапов:
- Построение ячеек по входному множеству верёвочек.
- Перебор по ячейкам с запоминанием результатов вычисления и αβ-отсечением.
- Восстановление номера верёвочки выигрышного хода.
Динамическое программирование
В данной задаче мы можем попробовать реализовать вычисление результата игры с помощью метода динамического программирования. В этом случае мы начинаем расчёт с всех конфигураций, состоящих из 1 клетки, затем переходим к конфигурации из двух клеток и так далее, пока не дойдем до конфигурации с K клетками. Проблема динамического программирования в том, что при таком расчёте исходов игры мы попадаем в большое число состояний, которые никогда бы не были достигнуты при оптимальной игре обоих игроков. Кроме того, переход от шага i к шагу i + 1 при динамическом программировании в данном случае достаточно сложен. Поэтому решение, использующее принцип динамического программирования, не должно проходить несколько самых сложных тестов.
