
MSWEEPER	Сапер ошибается только один раз MSWEEPER Описание Учебное минное поле имеет вид прямоугольника, который разбит на квадраты прямыми линиями, параллельными сторонам поля. В каждом квадрате спрятано не более одной мины. Каждый незаминированный квадрат имеет характеристику: количество соседей-мин. На рисунке 1 характеристики вписаны в соответствующие квадраты, мины обозначены крестиками Тренировка Сапёра происходит следующим образом: Минёр закладывает мины и сообщает Посреднику исходные характеристики некоторых квадратов. Сапёру расположение мин не известно, его задача заключается в том, чтобы найти все мины, используя характеристики квадратов, которые сообщает ему Посредник, и не подорваться. Если в процессе разминирования Сапёру не хватает информации, он может дополнительно спросить характеристику нужного ему квадрата у Посредника. Если в этом квадрате нет мины, Сапёр получит характеристику, если мина есть – произойдет "взрыв". Задачи Составьте программу MLAYER, которая минирует поле, имитируя действия Минера: Считывает исходные данные из текстового файла MLAYER.IN Минирует поле и определяет набор исходных характеристик для Сапёра Выводит результат в текстовый файл MLAYER.OUT Составьте программу MSWEEPER, которая разминирует поле, имитируя действия Сапёра: Считывает исходные данные из текстового файла MSWEEPER.IN Определяет местонахождение мин и "не мин" Выводит результат в текстовый файл MSWEEPER.OUT Форматы исходных данных и результатов Пусть столбцы поля пронумерованы слева направо, а строки – сверху вниз. Далее будем обозначать row – номер строки, col – номер столбца. Координаты – это пара (row, col) В файле MLAYER.IN расположена пара чисел H и W, разделенных пробелом, где H – количество строк, W – количество столбцов минного поля (1<=H,W<=30) В файле MLAYER.OUT данные расположены следующим образом: в первой строке находится число мин M (M>=0), за которым следует M пар чисел – координат мин; во второй строке – число характеристик K (K>=0), за которым следует K пар чисел – координат соответствующих квадратов; числа в каждой строке разделены пробелами. Размеры поля и характеристики квадратов заданы в файле MSWEEPER.IN следующим образом: в первой строке находятся два числа H и W, во второй – число K, в каждой из оставшихся K строк находятся тройки чисел row, col, c, где H – количество строк, W – количество столбцов (1<=H,W<=30), K – количество характеристик (K<=1), (row, col) – координаты очередного квадрата, c – его характеристика; числа в каждой строке разделены пробелами. В файле MSWEEPER.OUT данные расположены следующим образом: в первой строке – число обнаруженных мин M (M³0), за которым следует M пар чисел – координат мин; во второй строке – число обнаруженных "не мин" N (N³0), за которым следует N пар чисел – координат "не мин"; в каждой строке числа разделены пробелами. Посредник всегда гарантирует корректность исходных данных, а также существование и единственность решения. На рис. 2 показан пример сведений о минном поле, которые Минёр сообщил Посреднику. В таблице 1 содержится соответствующий пример входных и выходных данных Таблица 1 MLAYER.IN 4 3 MLAYER.OUT 3 1 2 2 2 1 3 3 1 1 2 1 2 3 На рис. 3 показан пример начальных сведений о минном поле, которые Посредник сообщил Сапёру. Знаком вопроса обозначен квадрат, о котором Сапёр запросил Посредника. В таблице 2 содержится соответствующий пример входных и выходных данных. Таблица 2 MSWEEPER.IN 4 3 3 1 1 2 2 1 2 2 3 3 MSWEEPER.OUT 2 1 2 2 2 1 3 2 На рис. 4 показан пример ответа Посредника на запрос Сапёра. В таблице 3 содержится пример входных и выходных данных, соответствующий окончанию поединка. Таблица 3 MSWEEPER.IN 4 3 1 3 2 1 MSWEEPER.OUT 1 1 3 Правила проведения соревнований Соревнования проводятся в два тура. К первому туру допускаются участники, предоставившие программу "Сапёр" (MSweeper). В первом туре проводятся поединки эталонного Минёра с каждым из участников-Сапёров. Всем Сапёрам предлагается один и тот же набор минных полей. Участники, набравшие ноль баллов, выбывают из дальнейшей борьбы. Ко второму туру допускаются те участники, которые предоставили программу "Минёр" и набрали больше нуля баллов в первом туре. Во втором туре N участников дважды соревнуются друг с другом: один раз в роли Сапёра и один раз в роли Минёра (всего 2×N×(N-1) поединков). Поединок Сапёра и Минёра происходит так: Посредник вызывает Минёра и получает от него информацию о заминированном поле. Затем Посредник проверяет корректность этой информации по следующим принципам: Минёр должен соблюдать формат своего выходного файла Минёр должен уложиться в отведенное ему время Задача должна иметь решение, причем единственное Участник (MSweeper) должен суметь решить свою собственную (MLayer) задачу Если информация корректна, Посредник вызывает Сапёра и сообщает ему эту информацию (кроме расположения мин). Каждый раз, когда Сапёр хочет получить дополнительную информацию, он заканчивает работу и оставляет в текстовом файле соответствующий запрос. Отвечая на запрос, Посредник формирует текстовый файл с ответом и снова вызывает Сапёра. Поединок заканчивается в следующих случаях: Минёр сообщил некорректную информацию Сапёр правильно указал все мины Сапёр "подорвался" Сапёр не уложился в отведенное ему время Сапёр нарушил формат своего выходного файла Запрос Сапёра не содержит "не мин" (Посреднику нечем ответить) Правила начисления баллов Баллы начисляются Сапёру за каждую правильно указанную мину (естественно, по одному разу). В том случае, если в каком-то поединке Минёр сообщил некорректную информацию, Сапёр получает максимальное количество баллов за этот поединок. Правило определения победителей Победители определяются по сумме балов, набранных ими в первом и втором туре. При равном количестве балов лучшим считается тот, кто потратил меньше времени на разминирование по сумме двух туров. Требования к программам Программа должна быть подготовлена при помощи компилятора Borland Pascal 7.0 или при помощи компилятора Borland C++ 3.1 для работы в среде операционной системы MS DOS Перед началом поединка программа помещается в директорий (каталог), имя которого заранее не известно. Программа запускается на выполнение из текущего директория (иными словами, в момент запуска директорий, в котором находится программа, является текущим директорием ОС на текущем дисковом устройстве) Программа может создавать по мере необходимости в текущем директории свои файлы и поддиректории, суммарный объем которых не должен превосходить 100 килобайт Максимальный объем свободной оперативной памяти, доступный программе, составляет 400 килобайт Передачу управления Посреднику программа осуществляет путем нормального завершения, то есть возврата управления операционной системе Программа не должна создавать, удалять или модифицировать файлы вне текущего директория. Программа не должна запускать резидентных программ или каких-либо иных параллельных процессов Программа не должна изменять параметры ОС, BIOS, аппаратных средств Требования к оформлению результатов Программу-решение следует поместить в текстовый ASCII-файл, который имеет имя, указанное в условии задачи, и расширение .PAS, .CPP . или .C в зависимости от используемого языка программирования. Исходный текст программы-решения должен содержать описание режимов трансляции на тот случай, если жюри будет вынуждено перетранслировать представленный исходный текст. Например, для включения опций компиляции в текст программы в среде Турбо Паскаля достаточно выполнить команду CTRL-O+O. По той же причине для программ на языке Си/Си++ необходимо кроме файлов решения предоставить файл проекта и конфигурации (в версии BorlandC++ 3.1, например, это файлы .PRJ и TCCONFIG.TC) Программа должна правильно ввести исходные данные. Комментировать исходные данные в файле не надо, если это не требуется по условию. В процессе работы программа должна обрабатывать те файлы, которые расположены в текущем директории (т.е. не обязательно на диске А:) Придерживайтесь формы ввода данных и вывода результатов, приведенных в условиях задач и в примерах! Пользуйтесь примерами для отладки программ. Но успешная работа программы на приведенных примерах не гарантирует правильности программы! Для обработки каждого теста существуют ограничения по времени: как правило, 30 секунд, если используется компилятор, и 5 минут, если используется интерпретатор Если могут существовать разные варианты решения задачи, удовлетворяющие условию, достаточно представить одно из них Правильность исходных данных проверять не надо, если это не оговорено особо условием задачи.

MSWEEPER

Сапер ошибается только один раз
MSWEEPER

Описание
Учебное минное поле имеет вид прямоугольника, который разбит на квадраты прямыми линиями, параллельными сторонам поля. В каждом квадрате спрятано не более одной мины. Каждый незаминированный квадрат имеет характеристику: количество соседей-мин. На рисунке 1 характеристики вписаны в соответствующие квадраты, мины обозначены крестиками

Тренировка Сапёра происходит следующим образом: Минёр закладывает мины и сообщает Посреднику исходные характеристики некоторых квадратов. Сапёру расположение мин не известно, его задача заключается в том, чтобы найти все мины, используя характеристики квадратов, которые сообщает ему Посредник, и не подорваться. Если в процессе разминирования Сапёру не хватает информации, он может дополнительно спросить характеристику нужного ему квадрата у Посредника. Если в этом квадрате нет мины, Сапёр получит характеристику, если мина есть – произойдет "взрыв".

Задачи
Составьте программу MLAYER, которая минирует поле, имитируя действия Минера:

Считывает исходные данные из текстового файла MLAYER.IN
Минирует поле и определяет набор исходных характеристик для Сапёра
Выводит результат в текстовый файл MLAYER.OUT

Составьте программу MSWEEPER, которая разминирует поле, имитируя действия Сапёра:

Считывает исходные данные из текстового файла MSWEEPER.IN
Определяет местонахождение мин и "не мин"
Выводит результат в текстовый файл MSWEEPER.OUT

Форматы исходных данных и результатов

Пусть столбцы поля пронумерованы слева направо, а строки – сверху вниз. Далее будем обозначать row – номер строки, col – номер столбца. Координаты – это пара (row, col)

В файле MLAYER.IN расположена пара чисел H и W, разделенных пробелом, где H – количество строк, W – количество столбцов минного поля (1<=H,W<=30)

В файле MLAYER.OUT данные расположены следующим образом: в первой строке находится число мин M (M>=0), за которым следует M пар чисел – координат мин; во второй строке – число характеристик K (K>=0), за которым следует K пар чисел – координат соответствующих квадратов; числа в каждой строке разделены пробелами.

Размеры поля и характеристики квадратов заданы в файле MSWEEPER.IN следующим образом: в первой строке находятся два числа H и W, во второй – число K, в каждой из оставшихся K строк находятся тройки чисел row, col, c, где H – количество строк, W – количество столбцов (1<=H,W<=30), K – количество характеристик (K<=1), (row, col) – координаты очередного квадрата, c – его характеристика; числа в каждой строке разделены пробелами.

В файле MSWEEPER.OUT данные расположены следующим образом: в первой строке – число обнаруженных мин M (M³0), за которым следует M пар чисел – координат мин; во второй строке – число обнаруженных "не мин" N (N³0), за которым следует N пар чисел – координат "не мин"; в каждой строке числа разделены пробелами.

Посредник всегда гарантирует корректность исходных данных, а также существование и единственность решения.

Подпись: 2 + +
2 + 3
Рис.2
На рис. 2 показан пример сведений о минном поле, которые Минёр сообщил Посреднику. В таблице 1 содержится соответствующий пример входных и выходных данных

Таблица 1

MLAYER.IN
4 3

MLAYER.OUT
3 1 2 2 2 1 3
3 1 1 2 1 2 3

На рис. 3 показан пример начальных сведений о минном поле, которые Посредник сообщил Сапёру. Знаком вопроса обозначен квадрат, о котором Сапёр запросил Посредника. В таблице 2 содержится соответствующий пример входных и выходных данных.

Таблица 2

MSWEEPER.IN
4 3
3 1 1 2 2 1 2 2 3 3

MSWEEPER.OUT
2 1 2 2 2
1 3 2

На рис. 4 показан пример ответа Посредника на запрос Сапёра. В таблице 3 содержится пример входных и выходных данных, соответствующий окончанию поединка.

Таблица 3

MSWEEPER.IN
4 3
1 3 2 1

MSWEEPER.OUT
1 1 3

Правила проведения соревнований
Соревнования проводятся в два тура. К первому туру допускаются участники, предоставившие программу "Сапёр" (MSweeper). В первом туре проводятся поединки эталонного Минёра с каждым из участников-Сапёров. Всем Сапёрам предлагается один и тот же набор минных полей. Участники, набравшие ноль баллов, выбывают из дальнейшей борьбы.

Ко второму туру допускаются те участники, которые предоставили программу "Минёр" и набрали больше нуля баллов в первом туре. Во втором туре N участников дважды соревнуются друг с другом: один раз в роли Сапёра и один раз в роли Минёра (всего
2×N×(N-1) поединков).

Поединок Сапёра и Минёра происходит так: Посредник вызывает Минёра и получает от него информацию о заминированном поле. Затем Посредник проверяет корректность этой информации по следующим принципам:

Минёр должен соблюдать формат своего выходного файла
Минёр должен уложиться в отведенное ему время
Задача должна иметь решение, причем единственное
Участник (MSweeper) должен суметь решить свою собственную (MLayer) задачу

Если информация корректна, Посредник вызывает Сапёра и сообщает ему эту информацию (кроме расположения мин). Каждый раз, когда Сапёр хочет получить дополнительную информацию, он заканчивает работу и оставляет в текстовом файле соответствующий запрос. Отвечая на запрос, Посредник формирует текстовый файл с ответом и снова вызывает Сапёра.

Поединок заканчивается в следующих случаях:

Минёр сообщил некорректную информацию
Сапёр правильно указал все мины
Сапёр "подорвался"
Сапёр не уложился в отведенное ему время
Сапёр нарушил формат своего выходного файла
Запрос Сапёра не содержит "не мин" (Посреднику нечем ответить)

Правила начисления баллов
Баллы начисляются Сапёру за каждую правильно указанную мину (естественно, по одному разу). В том случае, если в каком-то поединке Минёр сообщил некорректную информацию, Сапёр получает максимальное количество баллов за этот поединок.

Правило определения победителей
Победители определяются по сумме балов, набранных ими в первом и втором туре. При равном количестве балов лучшим считается тот, кто потратил меньше времени на разминирование по сумме двух туров.

Требования к программам

Программа должна быть подготовлена при помощи компилятора Borland Pascal 7.0 или при помощи компилятора Borland C++ 3.1 для
работы в среде операционной системы MS DOS
Перед началом поединка программа помещается в директорий (каталог), имя которого заранее не известно.
Программа запускается на выполнение из текущего директория (иными словами, в момент запуска директорий, в котором находится
программа, является текущим директорием ОС на текущем дисковом устройстве)
Программа может создавать по мере необходимости в текущем директории свои файлы и поддиректории, суммарный объем которых
не должен превосходить 100 килобайт
Максимальный объем свободной оперативной памяти, доступный программе, составляет 400 килобайт
Передачу управления Посреднику программа осуществляет путем нормального завершения, то есть возврата управления
операционной системе
Программа не должна создавать, удалять или модифицировать файлы вне текущего директория.
Программа не должна запускать резидентных программ или каких-либо иных параллельных процессов
Программа не должна изменять параметры ОС, BIOS, аппаратных средств

Требования к оформлению результатов

Программу-решение следует поместить в текстовый ASCII-файл, который имеет имя, указанное в условии задачи, и расширение *.PAS, *.CPP . или *.C в зависимости от используемого языка программирования. Исходный текст программы-решения должен содержать описание режимов трансляции на тот случай, если жюри будет вынуждено перетранслировать представленный исходный текст. Например, для включения опций компиляции в текст программы в среде Турбо Паскаля достаточно выполнить команду CTRL-O+O. По той же причине для программ на языке Си/Си++ необходимо кроме файлов решения предоставить файл проекта и конфигурации (в версии BorlandC++ 3.1, например, это файлы *.PRJ и TCCONFIG.TC)
Программа должна правильно ввести исходные данные. Комментировать исходные данные в файле не надо, если это не требуется по условию. В процессе работы программа должна обрабатывать те файлы, которые расположены в текущем директории (т.е. не обязательно на диске А:)

Придерживайтесь формы ввода данных и вывода результатов, приведенных в условиях задач и в примерах! Пользуйтесь примерами для отладки программ. Но успешная работа программы на приведенных примерах не гарантирует правильности программы!
Для обработки каждого теста существуют ограничения по времени: как правило, 30 секунд, если используется компилятор, и 5 минут, если используется интерпретатор
Если могут существовать разные варианты решения задачи, удовлетворяющие условию, достаточно представить одно из них
Правильность исходных данных проверять не надо, если это не оговорено особо условием задачи.