Входные данные: - Выходные данные: - Ограничение на память: 32 MB Время на тест: 1 секунда Тесты к задаче:Скачать Библиотека:Скачать
ЗАДАЧА
Дорожка представляет собой горизонтальную или вертикальную последовательность клеток сетки, состоящую не менее чем из двух последовательных клеток. Две дорожки расположены на сетке размером N на N. Одна дорожка горизонтальная, а другая - вертикальная. На Рис. 1 эти две дорожки помечены символом X. Дорожки могут быть одинаковой или разной длины. Дорожки могут иметь общую клетку, а могут не иметь таковой. Если на диаграмме, такой как Рис. 1, можно интерпретировать клетку, например (4,4), как принадлежащую только одной дорожке или обеим дорожкам, то следует считать, что данная клетка принадлежит и той, и другой дорожке. Следовательно, на Рис. 1 верхняя клетка вертикальной дорожки будет (4,4), но не (5,4).
В начале не известно, где расположены дорожки. Ваша задача - написать программу, определяющую их положение. Назовем горизонтальную дорожку ДОРОЖКА1, а вертикальную - ДОРОЖКА2. Каждая клетка сетки представлена парой чисел (r,c), задающих номер строки и столбца соответственно. Левая верхняя клетка сетки имеет координаты (1,1). Каждая дорожка задается парой клеток: <(r1, c1), (r2, c2)>. На Рис. 1 ДОРОЖКА1 задается как <(4,3), (4,8)>, а ДОРОЖКА2 - как <(4,4), (9,4)>.
При решении данной задачи вы должны использовать библиотеку для получения входных данных, для поиска решения и для выдачи ответа. Размер N квадратной сетки возвращается библиотечной функцией gridsize, которую вы должны вызвать в начале работы. Для определения положений дорожек вы можете использовать только библиотечную функцию rect(a,b,c,d), которая получает на входе координаты прямоугольной области и возвращает число 1, если в указанной области встречается хотя бы одна клетка, принадлежащая хотя бы одной дорожке, и число 0 - в противном случае. Область задается в виде [a,b]*[c,d], где a≤b и c≤d, при этом необходимо обратить внимание на порядок аргументов. Например, на Рис. 1 проверяемая область закрашена серым цветом. От вас требуется написать программу, определяющую точное положение дорожек, используя ограниченное число вызовов функции rect.
Ваша программа должна выдавать ответ с помощью вызова библиотечной функции report(r1, c1, r2, c2, p1, q1, p2, q2), где пара <(r1, c1),(r2, c2)> задает ДОРОЖКУ1, а пара <(p1, q1),(p2, q2)> - ДОРОЖКУ2. Вызов функции report приведет к завершению работы вашей программы. Обратите внимание, что ДОРОЖКА1 горизонтальная, а ДОРОЖКА2 - вертикальная, и (r1, c1) - координаты левого конца горизонтальной ДОРОЖКИ1, а (p1, q1) - координаты верхнего конца вертикальной ДОРОЖКИ2. Таким образом, r1=r2, c1 < c2, p1 < p2 и q1=q2. Если параметры функции report не удовлетворяют этим ограничениям, то стандартный вывод будет содержать сообщение об ошибке.
ОГРАНИЧЕНИЯ
Входные данные доступны только через вызовы библиотечных функций gridsize и rect.
Размер сетки N удовлетворяет ограничению 5≤N≤10000.
Число вызовов функции rect не должно превышать 400 для любого теста. Если ваша программа совершит более 400 вызовов функции rect, то это приведет к ее досрочному завершению.
Ваша программа должна выполнить более одного вызова функции rect, и ровно один раз - вызов функции report.
Если вызов функции rect будет произведен с некорректными параметрами, то это приведет к досрочному завершению вашей программы.
Ваша программа не должна считывать или записывать какие-либо файлы, а также использовать стандартный ввод/вывод.
БИБЛИОТЕКА
В вашем распоряжении находится библиотека, включающая:
FreePascal библиотеку (prectlib.ppu, prectlib.o)
function gridsize: LongInt;
function rect(a,b,c,d : LongInt) : LongInt;
procedure report(r1, c1, r2, c2, p1, q1, p2, q2 : LongInt);
Инструкции:
при компиляции вашего файла rods.pas используйте оператор
uses prectlib;
и командную строку
fpc -So -O2 -XS rods.pas
Программа prodstool.pas представляет собой пример использования данной FreePascal библиотеки.
GNU C/C++ библиотеку (crectlib.h, crectlib.o)
int gridsize();
int rect(int a, int b, int c, int d);
void report(int r1, int c1, int r2, int c2, int p1, int q1, int p2, int q2);
Программа prodstool.с представляет собой пример использования данной GNU C/C++ библиотеки.
Для C/C++ в среде RHIDE
Убедитесь, что в опциях Option->Linker указано crectlib.o.
ЭКСПЕРИМЕНТИРОВАНИЕ
Для проведения экспериментов с библиотекой вы должны создать текстовый файл rods.in. Файл должен состоять из трех строк. В первой строке файла должно быть записано число N, размер сетки. Вторая строка должна содержать координаты ДОРОЖКИ1, r1 c1 r2 c2, где (r1, c1) - координаты левого конца дорожки. Третья строка должна содержать координаты ДОРОЖКИ2 p1 q1 p2 q2, где (p1, q1) - координаты верхнего конца дорожки.
После запуска вашей программы с вызовов функции report, будет создан выходной файл rods.out. Этот файл будет содержать число вызовов функции rect и координаты концов дорожек, которые вы передадите при вызове функции report. Если в процессе работы программы произошли какие-либо ошибки или нарушения требований условия при обращении к библиотеке, то файл rods.out будет содержать соответствущее сообщение об ошибке.
Диалог между вашей программой и библиотекой записывается в файл rods.log. Этот файл rods.log будет содержать последовательность вызовов функции rect в форме "k : rect(a,b,c,d) = ans". Это означает, что k-ый вызов функции rect(a,b,c,d) вернул число ans.
ПРИМЕРЫ ВВОДА И ВЫВОДА
Пример:
rods.in
9
4 3 4 8
4 4 9 4
rods.out
20
4 3 4 8
4 4 9 4
СИСТЕМА ОЦЕНКИ
Если ваша программа нарушает какое-либо вышеназванное ограничение (например, число вызовов функции rect более 400), или если ответ вашей программы (положение дорожек) некорректный, то вы получаете 0 баллов.
Если ответ вашей программы правильный, то ваши баллы будут зависеть от количества вызовов функции rect на каждом тесте. Если это число не превышает 100, то вы получаете 5 баллов, если оно от 101 до 200, то вы получаете 3 балла, а если от 201 до 400, то вы получаете 1 балл.
аудиторские услуги восстановление и ведение бухгалтерского учета . Предлагаем ремонт плазменных телевизоров в москве.