Вы можете предполагать, что суммарное время работы библиотеки в процессе тестирования не будет превышать 4 сек.
Загрузить библиотеку для тестирования
Рассмотрим игру для двух игроков. Игрокам дан прямоугольник размером x × y (где x и y — положительные целые числа). Игроки ходят по очереди. Ход состоит в разделении прямоугольника на два прямоугольника одним горизонтальным или вертикальным разрезом. Полученные прямоугольники должны иметь положительные целочисленные размеры.
.jpg)
Возможные разрезы прямоугольника размером 4 × 3.
После каждого разреза прямоугольник с меньшей площадью убирается, а оставшийся передается другому игроку. Если прямоугольник разделен на две равные части, то убирается одна из них. Игрок, который получает прямоугольник размером 1 × 1, проигрывает, так как не может сделать следующий ход.
Ваша задача — написать программу, которая бы играла в игру с прямоугольниками и выигрывала. Для того чтобы играть, программа должна использовать специальную библиотеку. В библиотеке есть функции dimension_x() и dimension_y(), возвращающие размеры прямоугольника. Начальные размеры прямоугольника — целые числа от 1 до 100 000 000. Как минимум один из размеров больше 1. К тому же, в 50% тестов размеры прямоугольника не будут превышать 25.
В библиотеке есть также процедура cut(dir, position), которая должна вызываться вашей программой, чтобы сделать ход. Параметры dir и position описывают направление и позицию разреза соответственно. Параметр dir может принимать одно из двух значений: vertical и horizontal. Если dir = vertical, то проводится вертикальный разрез, а параметр position указывает x - координату разреза, как показано на рисунке выше. При этом вы должны гарантировать выполнение неравенства 1 ≤ position ≤ dimension_x()− 1. Если dir = horizontal, то проводится горизонтальный разрез, а параметр position указывает y ? координату разреза. При этом, вы должны гарантировать выполнение неравенства 1 ≤ position ≤ dimension_y()− 1.
После запуска вашей программы она будет играть за одного из игроков. Ваша программа ходит первой, она должна разрезать исходный прямоугольник. Когда ваша программа вызывает процедуру cut, ваш ход записывается и управление передается программе соперника. После хода соперника управление возвращается вашей программе. Значения, которые возвращаются функциями dimension_x() и dimension_y(), будут отражать результат вашего хода и хода соперника. Как только ваша программа выигрывает, проигрывает или делает неправильный ход, ее исполнение будет прервано. Прерывание вашей программы — это автоматический процесс, так что ваша программа должна продолжать делать столько ходов, сколько возможно до автоматического прерывания ее исполнения. Вы можете предполагать, что для предложенных входных данных всегда существует выигрышная стратегия для вашей программы.
Ваша программа не должна читать какие-либо файлы или писать в них, не должна использовать стандартный ввод и вывод и не должна пытаться изменять содержимое какой-либо памяти вне вашей программы. Нарушение любого из этих правил может привести к дисквалификации.
Экспериментирование
Для того, чтобы дать вам возможность поэкспериментировать с библиотекой, в ваше распоряжение предоставлены примеры библиотек: их исходные тексты находятся в файлах preclib.pas, creclib.c и creclib.h . Эти библиотеки вы можете взять по адресу: http :// contest / . Они реализуют очень простую стратегию. Когда вы запустите вашу программу, она будет играть против этих простых соперников. Вы можете изменять их, чтобы протестировать вашу программу с лучшими соперниками. Следует учесть, что во время тестирования после окончания тура, ваша программа будет играть против другого соперника.
При посылке вашей программы на проверку с использованием интерфейса TEST , она будет откомпилирована с немодифицированной библиотекой соперника. При этом посылаемый вами входной файл будет передан как стандартный ввод вашей программе. Входной файл должен состоять из двух строк, каждая из которых должна содержать по одному целому числу. Первая строка должна содержать исходную ширину, вторая — исходную высоту прямоугольника. Эти размеры будут прочитаны библиотекой, предложенной в качестве примера.
Если вы модифицируете часть implementation библиотеки preclib.pas, пожалуйста, перекомпилируйте её, используя команду ppc386 -O2 preclib.pas. Эта команда создаст файлы preclib.o и preclib.ppu. Эти файлы необходимы для компиляции вашей программы и должны быть в помещены в каталог, где находится ваша программа. Пожалуйста, не модифицируйте часть interface библиотеки preclib.pas.
Если вы модифицируете библиотеку creclib.c, пожалуйста, не забудьте поместить ее вместе с creclib.h в каталог, где находится ваша программа, — они необходимы для компиляции. Пожалуйста, не модифицируйте файл creclib.h.
В ваше распоряжение также предоставляются две простые программы, которые иллюстрируют использование библиотек crec.c и prec.pas. Пожалуйста, помните, что эти программы не являются правильными решениями. Вы можете откомпилировать их, используя такие команды:
gcc -O2 -static crec.c creclib.c -lm
g++ -O2 -static crec.c creclib.c -lm
ppc386 -O2 -XS prec.pas
Библиотеки
В ваше распоряжение предоставлены библиотеки, которые обеспечивают следующую функциональность:
Библиотека для FreePascal (preclib.ppu, preclib.o)
type direction = (vertical, horizontal);
function dimension_x(): longint;
function dimension_y(): longint;
procedure cut(dir: direction; position: longint);
Включите следующий оператор в ваш исходный файл rec.pas:
uses preclib;
Чтобы откомпилировать вашу программу, скопируйте файлы preclib.o и reclib.ppu в каталог, где находится ваш исходный файл, и выполните следующую команду:
ppc386 -O2 -XS rec.pas
Файл prec.pas является примером использования библиотеки preclib.
Библиотека для GNU C/C++ (creclib.h, creclib.c)
typedef enum __direction {vertical, horizontal} direction;
int dimension_x();
int dimension_y();
void cut(direction dir, int position);
Включите следующий оператор в ваш исходный файл (rec.c или rec.cpp):
#include ”creclib.h”
Чтобы откомпилировать вашу программу, скопируйте файлы creclib.c и creclib.h в каталог, где находится ваш исходный файл, и выполните следующую команду:
gcc -O2 -static rec.c creclib.c –lm
или:
g++ -O2 -static rec.cpp creclib.c –lm
Файл crec.c является примером использования библиотеки в C.
Пример взаимодействия
Ниже приведен пример взаимодействия вашей программы с библиотекой. Он показывает, как может проходить игра. Игра начинается с прямоугольника размером 4 × 3. Существует выигрышная стратегия для этого случая.
|
Ваша программа вызывает
|
Что происходит
|
|
dimension_x()
|
возвращает 4
|
|
dimension_y()
|
возвращает 3
|
|
cut(vertical, 1)
|
ваш разрез записывается, и прямоугольник размером 3 × 3 передается вашему сопернику, который разрезает его и получается прямоугольник размером 3 × 2; после этого управление передается вашей программе
|
|
dimension_x()
|
возвращает 3
|
|
dimension_y()
|
возвращает 2
|
|
cut(horizontal, 1)
|
ваш разрез записывается, и прямоугольник размером 3 × 1 передается вашему сопернику, который разрезает его и получается прямоугольник размером 2 × 1; после этого управление передается вашей программе
|
|
dimension_x()
|
возвращает 2
|
|
dimension_y()
|
возвращает 1
|
|
cut(vertical, 1)
|
в результате вашего разреза получается прямоугольник размером 1 × 1, так что вы выиграли; после этого работа вашей программы автоматически прекращается.
|