ОТКРЫТАЯ ВСЕСИБИРСКАЯ ОЛИМПИАДА ПО ИНФОРМАТИКЕ И ПРОГРАММИРОВАНИЮ ----------------------------------------------------------------- ЗАОЧНЫЙ ТУР ----------- Общие замечания --------------- В данном файле описаны средства, предоставляемые жюри Олимпиады участникам для отладки решений задачи заочного тура. Решением задачи заочного тура является код на одном из трех разрешенных языков программирования, оформленный так, как описано в данном файле. Разрешенными языками программирования являются: * C++ (используется компилятор gcc Version 3.3.5) * Pascal (используется компилятор Free Pascal Compiler 2.0) * Modula-2 (используется компилятор XDS Modula-2/Oberon-2 2.51) * Java ( используется компилятор Java 1.5.0 ) Эти компиляторы доступны в сети Интернет, например, по следующим адресам: DJGPP, GCC для Windows: http://www.midpec.com/djgpp/zip-picker.html Free Pascal Compiler: для Windows: http://sourceforge.net/project/showfiles.php?group_id=2174 Пакеты gcc и Free Pascal Compiler входят в стандартную поставку основных дистрибутивов Linux. Modula-2: для Windows: http://www.excelsior-usa.com/download/xds25x/xds-x86-251-enduser-win32.exe для Linux: http://www.excelsior-usa.com/download/xds25x/xds-x86-251-enduser-linux.tgz документация: http://www.excelsior-usa.com/xdsdoc.html Java: JDK (Java Development Kit) для всех платформ: http://java.sun.com/j2se/1.5.0/download.jsp по этой же ссылке для скачивания доступна докунтация кроме того, доступна on-line документация: http://java.sun.com/j2se/1.5.0/docs/index.html Компиляция и проверка присланных решений будет производиться в операционной системе Linux. Предоставленные примеры игровых стратегий компилируются в исполняемые файлы, принимающие следующие параметры: (запуск в ОС Linux) $ ./plates [inputfile [logfile]] (запуск в OС Windows) > plates.exe [inputfile [logfile]] (для Java) > java Game [inputfile [logfile]] inputfile -- имя файла с описанием начальной ситуации. Если параметр не задан, начальная ситуация читается из файла input.txt в текущем каталоге. Если файл не может быть открыт на чтение, программа выходит с кодом возврата 0. logfile -- имя файла, в который будут выводиться логи поединка. Если параметр не задан, логи будут записаны в файл log.txt. Файл перезаписывается без предупреждения. Если файл не может быть открыт на запись, программа выходит с кодом возврата 0. В процессе работы программа выводит в поток стандартного вывода информацию о количестве ходов. В архиве приведен пример файла со входной ситуацией. Формат файла описан ниже. Комментарии (отделены точкой с запятой) приведены для удобства, в реальном входном файле комментарии недопустимы. Разбивка по строкам фиксирована. Количество пробельных символов между ключевыми словами, цифрами и скобками может изменяться, но должно быть больше либо равно единице (т.е. любые две лексемы должны быть разделены пробельным символом). В случае победы первого игрока программа выводит соответствующее сообщение в поток стандартного вывода и выходит с кодом возврата 1. В случае победы второго игрока код возврата равен 2, в случае ничьи код возврата равен 3. В случае остановки игры по Ctrl+C или Esc код возврата равен 4. Гарантируется, что в случае корректной остановки игры файл лога будет дописан до окончания текущего блока move { }. Пример файла с начальной ситуацией: move 0 { ; номер хода, всегда 0 ship 0 { ; номер БПЛА owner { 1 } ; принадлежность: 1, 2 или 3 position { -28.500 0.000 } ; координаты БПЛА velocity { 0.000 5.000 } ; скорость БПЛА fuel { 400.000 } ; объем горючего в баке БПЛА } ship 1 { owner { 2 } position { -25.500 0.000 } velocity { 0.000 5.000 } fuel { 400.000 } } ; и т.д. } Таким образом описаны от 1 до 20 БПЛА. Параметр owner может принимать следующие значения: * 1 (БПЛА принадлежит первому игроку); * 2 (БПЛА принадлежит второму игроку); * 3 (БПЛА разрушен и движется неуправляемо). Остальные параметры должны принимать значения из диапазонов, приведенных в условии. Жюри обращает внимание участников на то, что хотя проверяющая программа принимает произвольные ситуации, реальное тестирование будет проводиться с начальными ситуациями, описанными в правилах. Файл лога начинается с описания начальной ситуации, затем следует описания игровых ситуаций после первого хода и т.д. в следующем виде: move 0 { ; описание начальной ситуации } move 1 { ; описание ситуации после первого хода } ; и т.д. Предоставленный визуализатор работают с файлом лога в том формате, в котором он создается программой проверки стратегий. Для того, чтобы запустить программу, Вам потребуется установить интерпретатор языка Java версии не меньше 1.3.1 (JRE 1.3.1). Мы рекомендуем версию 1.5.0 (JRE 1.5.0). Вы можете скачать его по адресу http://java.sun.com/j2se/1.3.1/download.jsp . На этой странице нужно выбрать ссылку "Download JRE 5.0 update 4" (номер update может быть другим). После перехода по ссылке Вам нужно будет подтвердить лицензионное соглашение, и Вам будет предложен выбор из нескольких разных дистрибутивов Java. Если вы планируете вносить изменения в визуализатор, Вам понадобится полноценный пакет разработчика (JDK 1.5.0). Его можно скачать с той же страницы. После установки Java вы сможете запускать визуализатор на своём компьютере с помощью файла run.bat (Windows) или run.sh (Linux), указывая в качестве параметра имя игрового log-файла. Визуализатор предоставляется в виде jar-файла LogPlayer.jar. Исходные коды визуализатора доступны в том же jar-файле и могут быть распакованы при помощи любого zip-архиватора. При тестировании стратегия каждого участника будет откомпилирована в отдельный исполняемый файл, тем самым будет достигнута максимальная изоляция стратегий друг от друга. Программа, осуществляющая поединок, будет написана на языке C++ и будет использовать алгоритм, аналогичный приведенному в примере проверяющей программы на языке C++. ВАЖНО: Жюри обращает внимание участников на то, что при проверке олимпиады реальная тестирующая система будет отличаться от предоставленной в качестве примера. В частности, будут контролироваться количество использованной памяти, будет запрещена запись файлов на диск, будет предотвращена возможность подмены игровой ситуации средствами, не оговоренными в условии, и т.п. Подробно ограничения описаны в условии задачи. Далее приведены описания файлов пакета для каждого из используемых языков программирования. 1. C++ ------- Участникам предоставляются следующие файлы: * player1.cpp -- пример игровой стратегии * player2.cpp -- пример игровой стратегии * input.txt -- пример файла с описанием начальной ситуации * plates.cpp -- проверяющая программа Решением задачи на языке C++ является файл, содержащий определение класса PLAYER на языке C++. Класс PLAYER обязан содержать следующие методы, определенные в области public (параметр MAX_SHIPS обозначает общее количество БПЛА): * конструктор: PLAYER::PLAYER( /* in */ int owner[MAX_SHIPS], /* in */ double x[MAX_SHIPS], /* in */ double y[MAX_SHIPS], /* in */ double u[MAX_SHIPS], /* in */ double v[MAX_SHIPS], /* in */ double fuel[MAX_SHIPS] ); * процедура принятия решения: void PLAYER::move( /* in */ int owner[MAX_SHIPS], /* in */ double x[MAX_SHIPS], /* in */ double y[MAX_SHIPS], /* in */ double u[MAX_SHIPS], /* in */ double v[MAX_SHIPS], /* in */ double fuel[MAX_SHIPS], /* out */ double fuel_consumption[MAX_SHIPS], /* out */ double norm_accel[MAX_SHIPS] ); Помимо этих двух методов, класс может содержать другие методы и поля, на усмотрение автора стратегии. 2. Pascal ---------- Участникам предоставляются следующие файлы: * player1.pas -- пример игровой стратегии; * player2.pas -- пример игровой стратегии; * input.txt -- пример файла с описанием начальной ситуации * plates.pas -- проверяющая программа Решением задачи на языке Pascal является файл, содержащий определение объекта (класса) на языке Pascal. Имя класса зависит от определенных при компиляции символов и записывается следующим образом: {$IFDEF PLAYER1} Cplayer1 {$ELSE} Cplayer2 {$ENDIF} Таким образом, в случае, если при компиляции был определен символ PLAYER1 с помощью директивы компилятора {$DEFINE PLAYER1}, класс автоматически получит имя Cplayer1, в противном случае класс будет автоматически назван Cplayer2. Класс обязан содержать следующие методы, определенные в области public (описание типов TIntArr и TDoubleArr находится в файле plates.pas): * конструктор: constructor Create( { in } var owner: TIntArr; { in } var x: TDoubleArr; { in } var y: TDoubleArr; { in } var u: TDoubleArr; { in } var v: TDoubeArr; { in } var fuel: TDoubleArr; ); Принимает на вход описание начальной ситуации: принадлежность каждого БПЛА (1, если БПЛА принадлежит игроку, 2, если БПЛА принадлежит противнику, 3, если БПЛА разрушен, но еще не вышел из игрового пространства, 0, если БПЛА уничтожен и не может взаимодействовать с остальными БПЛА), координаты, скорость количество горючего в баке каждого БПЛА. * процедура принятия решения: procedure move( { in } var owner: TIntArr; { in } var x: TDoubleArr; { in } var y: TDoubleArr; { in } var u: TDoubleArr; { in } var v: TDoubeArr; { in } var fuel: TDoubleArr; { out } var fuel_consumption: TDoubleArr; { out } var norm_accel: TDoubleArr; ); Помимо этих двух методов, класс может содержать другие методы и поля, на усмотрение автора стратегии. 3. Modula-2 ------------ Участникам предоставляются следующие файлы: * Player1.def -- интерфейс модуля игровой стратегии; * Player1.mod -- реализация модуля игровой стратегии (пример); * Player2.def -- интерфейс модуля игровой стратегии; * Player2.mod -- реализация модуля игровой стратегии (пример); * input.txt -- пример файла с описанием начальной ситуации * Plates.mod -- проверяющая программа; * Plates.prj -- проект для сборки исполняемого файла; * Defs.def -- интерфейс вспомогательного модуля общих описаний; * Defs.mod -- реализация вспомогательного модуля общих описаний. Решением задачи на языке Modula-2 является модуль Player1.mod, содержащий реализацию на языке Modula-2 функций игровой стратегии, заданных в интерфейcном модуле Player1.def. Процедура инициализации: PROCEDURE Create (VAR owner: TIntArr; VAR x, y, u, v, fuel: TDoubleArr); Процедура принятия решения: PROCEDURE Move (VAR owner: TIntArr; VAR x, y, u, v, fuel, fuel_consumption, norm_accel: TDoubleArr); Типы TIntArr, TDoubleArr и константа MAX_SHIPS (число БПЛА) описаны в модуле Defs.def. Запуск компилятора для сборки проекта выполняется следующей командной строкой: xm =p Plates.prj Перед запуском ознакомьтесь с файлами readme компилятора и установите переменные окружения XDSDIR и PATH необходимым образом. 4. Java -------- Участникам предоставляются следующие файлы: * Player.java -- интерфейс игровой стратегии * Player1.java -- пример игровой стратегии * Player2.java -- пример игровой стратегии * input.txt -- пример файла с описанием начальной ситуации * Game.java -- проверяющая программа * LogReader.java -- вспомогательный модуль проверяющей программы Решением задачи на языке Java является файл, содержащий имплементацию интерфейса Player. Файл должен называться Player1.java Класс Player1 будет содержать следующие методы, унаследованные от интерфейса Player (параметр MAX_SHIPS обозначает общее количество БПЛА): * инициализация: void init( /* in */ int owner[], /* in */ double x[], /* in */ double y[], /* in */ double u[], /* in */ double v[], /* in */ double fuel[] ); * процедура принятия решения: void move( /* in */ int owner[], /* in */ double x[], /* in */ double y[], /* in */ double u[], /* in */ double v[], /* in */ double fuel[], /* out */ double fuel_consumption[], /* out */ double norm_accel[] ); Помимо этих двух методов, класс может содержать другие методы и поля, на усмотрение автора стратегии. Решение участника не должно имплементировать какие-либо другие интерфейсы. Описание визуализатора ---------------------- Предоставленный визуализатор работают с файлом лога в том формате, в котором он создается программой проверки стратегий. Для того, чтобы запустить программу, Вам потребуется установить интерпретатор языка Java версии не меньше 1.3.1 (JRE 1.3.1). Мы рекомендуем версию 1.5.0 (JRE 1.5.0). Вы можете скачать его по адресу http://java.sun.com/j2se/1.3.1/download.jsp . На этой странице нужно выбрать ссылку "Download JRE 5.0 update 4" (номер update может быть другим). После перехода по ссылке Вам нужно будет подтвердить лицензионное соглашение, и Вам будет предложен выбор из нескольких разных дистрибутивов Java. Если вы планируете вносить изменения в визуализатор, Вам понадобится полноценный пакет разработчика (JDK 1.5). Его можно скачать с той же страницы. После установки Java вы сможете запускать визуализатор на своём компьютере с помощью файла run.bat (Windows) или run.sh (Linux), указывая в качестве параметра имя игрового log-файла. Визуализатор предоставляется в виде jar-файла LogPlayer.jar. Исходные коды визуализатора доступны в том же jar-файле и могут быть распакованы при помощи любого zip-архиватора. Дополнительные сведения ----------------------- При оформлении примеров жюри преследовало две цели: а) совместимость с как можно большим количеством компиляторов; б) отсутствие необходимости каким-либо образом изменять исходные коды стратегий в зависимости от того, является ли данный игрок первым либо вторым (для языков C++ и Pascal). В частности, именно этим обусловлено нестандартное оформление стратегий на языке Pascal. Тем не менее, жюри доводит до сведения участников, что все решения будут компилироваться ТОЛЬКО при помощи перечисленных выше компиляторов. Пожалуйста, перед отправкой решения проверьте его, скомпилировав его при помощи одного из разрешенных компиляторов.