Страница: 1 Отображать по:
#1017
Еловая аллея
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Заданы координаты клеток на прямой, в которые можно посадить ели. Для каждого сорта ели определены тени, отбрасываемые на восток и на запад. Ели не могут расти в тени других елей. Требуется высадить как можно больше елей и для каждой занятой клетки указать, какой сорт ели будет туда посажен.

Мэр города Урюпинска решил посадить на главной аллее города, которая проходит с запада на восток, голубые ели. Причем сажать ели можно не во всех местах, а только на специально оставленных при асфальтировании аллеи клумбах.

Как оказалось, голубые ели бывают M различных сортов. Для ели каждого сорта известна максимальная длина ее тени в течение дня в западном и в восточном направлении (Wi и Ei соответственно). При этом известно, что ели растут гораздо лучше, если в течение дня они не оказываются в тени других елей.

Координатная ось направлена вдоль аллеи с запада на восток.

По заданным координатам клумб вычислите максимальное число елей, которое можно посадить, соблюдая условие о том, что никакая ель не должна попадать в тень от другой ели.

Входные данные

Во входном файле записано сначала натуральное число M — количество сортов елей (1M100). Затем идет M пар чисел Wi, Ei, описывающих максимальную длину тени в западном и восточном направлении в течение дня для каждого сорта ели (числа Wi, Ei — целые, из диапазона от 0 до 30000). Далее идет натуральное число N — количество клумб, в которых можно сажать ели (1N100). Далее идет N чисел, задающих координаты клумб (координаты — целые числа, по модулю не превышающие 30000). Клумбы перечислены с запада на восток (в порядке возрастания их координат).

Примечание

Если на клумбе с координатой X мы посадили ель, максимальная тень которой в восточном направлении равна E, то все клумбы с координатами от X+1 до X+E–1 попадают в тень от этой ели, а клумба с координатами X+E — уже нет. Аналогично для тени в западном направлении.

Выходные данные

В выходной файл выведите сначала число A — максимальное количество елей, которые удастся посадить, а затем A пар чисел, описывающих ели. Первое число каждой пары задает номер клумбы, в которую садится ель. Второе число определяет номер сорта этой ели.

Примеры
Входные данные
3
10 1
2 2
1 10
10
0
1
3
5
7
9
11
13
15
16
Выходные данные
8
9 2
8 2
7 2
6 2
5 2
4 2
3 2
1 2
#1020
Левый лабиринт
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

В спортзале размером NxM метров построили современный аттракцион под названием "Левый лабиринт". Для этого на полу спортзала с интервалом в 1 метр начертили линии, параллельные стенам спортзала. Таким образом, спортзал разбили на NxM клеток. Дальше некоторые из этих клеток покрасили в черный цвет.

Аттракцион заключается в том, что участника ставят в некоторой клетке спортзала и просят как можно быстрее добежать до некоторой другой клетки. При этом накладываются следующие условия:

  • Участнику запрещено ходить по черным клеткам.
  • Придя в какую-то клетку, участник может пойти либо прямо, либо налево, либо направо (если в соответствующем направлении клетка не покрашена в черный цвет): ходить назад, а также ходить по диагонали запрещается.
  • За все время пути участнику разрешается повернуть направо (то есть пойти из текущей клетки направо относительно того, откуда он пришел в данную клетку) не более K раз.
  • В начальной клетке участник может встать лицом в ту сторону, в какую ему захочется. С какой стороны участник прибежит в конечную клетку также не важно.

Известно, что на то, чтобы перебежать из клетки в соседнюю, участник тратит ровно 1 секунду. Требуется вычислить минимальное время, за которое участник сможет достичь конечной клетки.

Входные данные

Во входном файле сначала записано число K — количество разрешенных поворотов направо (целое число из диапазона от 0 до 5), затем записаны числа N и M, задающие размеры спортзала — натуральные числа, не превышающие 20. Далее записано N строк по M чисел в каждой. Число 0 обозначает непокрашенную клетку, число 1 — покрашенную, число 2 — клетку, откуда стартует участник и число 3 — клетку, куда нужно добежать (клетки, помеченные 2 и 3 являются непокрашенными). В лабиринте всегда есть ровно одна начальная клетка и ровно одна клетка, в которую нужно попасть.

Выходные данные

В выходной файл выведите минимальное время, за которое можно добраться в конечную клетку. Если попасть в конечную клетку с соблюдением всех условий нельзя, выведите –1.

Примеры
Входные данные
1 3 4
0 0 2 0
0 1 1 0
0 0 3 0
Выходные данные
6
Входные данные
0 5 5
0 1 0 0 0
0 1 0 1 0
0 0 3 1 0
1 0 1 1 0
2 0 0 0 0
Выходные данные
12
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест