Парковка
Имя входного файла: | parking. in |
Имя выходного файла: | parking. out |
Ограничение по времени: | 3 секунды |
Ограничение по памяти: | 32 мегабайта |
Максимальный балл: | 100 баллов |
Администрация города Немногоярославца в связи с резким увеличением потока туристов решила организовать в центре города автомобильную стоянку. Стоянка имеет вид кольца с N парковочными местами. Парковочные места занумерованы от 1 до N по часовой стрелке. Автомобилист, подъезжая к стоянке, двигается вдоль нее по часовой стрелке, пока не найдет свободное парковочное место. После этого он паркует свой автомобиль на этом месте.
Вчера, после открытия, стоянку посетило M автомобилистов. Про каждого автомобилиста известно время его подъезда к стоянке, время, когда он покинул свою стоянку, а также парковочное место, около которого он подъехал к стоянке. Требуется определить для каждого автомобилиста номер парковочного места, которое он занял. Известно, что никакие два события не произошли одновременно, в частности никакие два автомобилиста не подъезжают к парковке одновременно, и пока некоторый автомобилист ищет место для парковки, ни один другой автомобилист не подъезжает к парковке и не покидает ее.
Формат входных данных
Первая строка входного файла содержит числа N — количество парковочных мест и M — количество автомобилистов (1 ≤ N ≤ 105, 1 ≤ M ≤ N). Следующие M строк содержат описания автомобилистов в следующем формате: t1 — время подъезда к стоянке, t2 — время, когда он покинул стоянку, и c — номер парковочного места, около которого он подъехал к стоянке (t1, t2 целые, 1 ≤ t1 < t2 ≤ 109; 1 ≤ c ≤ N).
Формат выходных данных
Выведите в выходной файл M чисел — для всех автомобилистов в порядке их перечисления во входном файле выведите номер занятого парковочного места.
Примеры
parking. in | parking. out |
6 6 1 9 6 2 5 6 3 7 6 4 11 4 6 10 5 8 12 4 | 6 1 2 4 5 1 |
Имя входного файла: | mayors. in |
Имя выходного файла: | mayors. out |
Ограничение по времени: | 3 секунды |
Ограничение по памяти: | 32 мегабайта |
Максимальный балл: | 100 баллов |
Во Флатландии имеется N городов, расположенных на плоскости в точках с координатами (xi, yi). Недавно президент Флатландии решил назначить в каждом городе мэра. При этом, чтобы его нельзя было уличить в дискриминации, он решил назначить на эти посты как мужчин, так и женщин. Для каждой горизонтальной и вертикальной прямой назовем несправедливостью модуль разности между количеством городов на этой прямой, в которых на пост мэра назначены мужчины и количеством городов на этой прямой, в которых на этот пост назначены женщины.
Чтобы показать свою беспристрастность, президент хочет минимизировать суммарную несправедливость по всем вертикальным и горизонтальным прямым.
Напишите программу, которая определит для каждого города, следует ли в нем назначить на пост мэра женщину или мужчину, так, чтобы суммарная несправедливость была минимальна.
Формат входных данных
Первая строка входного файла содержит число N — количество городов (1 ≤ N ≤ 20000). Следующие N строк содержат по два целых числа — координаты городов. Все координаты не превышают 109 по абсолютной величине.
Формат выходных данных
Выведите в выходной файл M чисел — для каждого города выведите 0, если в нем следует назначить на пост мэра мужчину, и 1, если женщину.
Примеры
mayors. in | mayors. out |
5 0 0 0 1 1 0 1 1 1 2 | 0 1 1 0 0 |
Ломаная
Имя входного файла: | poly. in |
Имя выходного файла: | poly. out |
Ограничение по времени: | 3 секунды |
Ограничение по памяти: | 32 мегабайта |
Максимальный балл: | 100 баллов |
На плоскости дана ломаная, каждое из звеньев которой перпендикулярно биссектрисе одного из углов, образованных координатными осями. Никакая вершина ломаной не лежит на звене1 ломаной. В частности, никакие две вершины ломаной не совпадают. Ваша задача — подсчитать число точек самопересечения ломаной.
Формат входных данных
В первой строке входного файла записано N — количество вершин ломаной (2≤N≤100000). В последующих N строках записаны координаты вершин — целые числа, по модулю не превосходящие 106. Вершины перечислены в порядке прохода по ломаной.
Формат выходных данных
В первой строке выходного файла выведите число точек самопересечения ломаной.
Примеры
poly. in | poly. out |
8 1 0 3 2 5 0 4 -1 1 2 3 4 5 2 2 –1 | 3 |
1 Кроме, возможно, того звена, концом которого она является ☺
