Входные данные: xor1.in, ..., xor10.in Выходные данные: xor1.out, ..., xor10.out Ограничения на память: - Время на тест: - Тесты к задаче:Скачать
ЗАДАЧА
Вы разрабатываете программу для мобильного телефона, оснащенного черно-белым экраном, на котором x-координаты отсчитываются слева направо, а y-координаты - сверху вниз, как показано на рисунках. Ваша программа использует разнообразные картинки, которые могут быть различного размера. Вместо того, чтобы хранить эти картинки, вы хотите создавать их, используя графическую библиотеку телефона. В начале рисования картинки все пикселы экрана окрашены в белый цвет. Единственная графическая операция, поддерживаемая библиотекой, - это XOR(L,R,T,B), которая перекрашивает в противоположный цвет пикселы, попадающие в прямоугольник с левым верхним углом в точке (L,T), а правым нижним - в точке (R,B), где L обозначает левую, T - верхнюю, R - правую, B - нижнюю координаты. Заметим, что в некоторых других графических библиотеках порядок аргументов может отличаться.
Например, рассмотрим получение картинки с рис. 3. Применяя XOR(2,4,2,6) к полностью белой картинке, получаем картинку, показанную на рис. 1. Применяя XOR(3,6,4,7) к картинке с рис. 1, получаем картинку, показанную на рис. 2, наконец, применяя XOR(1,3,3,5) к картинке с рис. 2, получаем картинку, показанную на рис. 3.
Ваша задача: для заданной черно-белой картинки построить по возможности кратчайшую последовательность вызовов XOR, приводящую к генерации, начиная с белого экрана, этой картинки. Вам даны входные файлы, описывающие картинки. Вы должны сдать файлы, описывающие параметры требуемых вызовов XOR, а не исходный текст программы для создания этих файлов.
ВВОД
Вам даны 10 текстовых файлов с именами с xor1.in по xor10.in. Каждый входной файл устроен следующим образом. Первая его строка содержит одно целое число N, 5≤N≤2000, обозначающее, что картинка имеет N строк и N столбцов. Оставшиеся строки входного файла описывают строки картинки сверху вниз. Каждая строка содержит N целых чисел: цвета пикселов слева направо. Значение 0 обозначает белый пиксел, а значение 1 - черный.
ВЫВОД
Вы должны сдать 10 выходных файлов, соответствующих входным.
Первая строка файла должна содержать текст
#FILE xor I
где целое число I - номер соответствующего входного файла. Вторая строка должна содержать целое число K - количество вызовов XOR. В последующих K строках должны располагаться описания этих вызовов в порядке от первого к последнему. Каждая из этих K строк должна содержать четыре целых числа: параметры вызова XOR в порядке L, R, T, B.
Если
- последовательность вызовов XOR, указанная в вашем файле, не приводит к генерации требуемой картинки, или
- число вызовов XOR, указанных в вашем файле, не равно K, или
- в вашем выходном файле K > 40000, или
- ваш выходной файл содержит вызов XOR с параметрами L>R или T>B, или
- ваш выходной файл содержит вызов XOR с неположительными координатами, или
- ваш выходной файл содержит вызов XOR со значением координаты, превышающим N,
то вы получите за данный тест 0 баллов. В противном случае ваш балл вычисляется по формуле:
1+9*ЧислоВызововВЛучшемРешенииУчастников/ЧислоВызововВВашемРешении.
Баллы округляются до первого знака после десятичной запятой по каждому тесту. Общий балл округляется до ближайшего целого.
Предположим, что вы сдали решение с 121 вызовом XOR. Если это решение - лучшее среди всех участников, то вы получите 10 баллов. Если лучшее среди сданных участниками решений использует 98 вызовов XOR, то ваш балл составит 1+9*98/121(=8.289:) и будет округлен до 8.3. Межкомнатные двери где. Межкомнатные двери деревянные массив. . Мощные дизельные обогреватели B 360 от ведущего производителя. . типография офсетная печать листовок