SnarkNews winter series-2009, раунд 2

 

A – Fence

Input file: fence.in, output file:  fence.out.

Time Limit: 2 seconds, Memory Limit: 64 Mebibytes

 

           Для парка культуры и отдыха было решено изготовить забор. Чтобы забор не портил своим невзрачным видом облик города, архитекторы решили сделать забор фигурным, и разработали несколько различных шаблонов для изготовления секций забора. Шаблон представляет собой многоугольник, где три стороны всегда одинаковы, а четвертая сторона (верхняя часть забора) представляет ломаную линию. Проекции вершин этой ломаной линии на основание забора следуют равномерно, и таким образом шаблон описывается как последовательность высот точек. Высота точек указывается в целых миллиметрах и варьируется от 0 до 2047.

           Количество точек в шаблоне равняется L (1 <= L <= 150). Архитекторы разработали M шаблонов (1 <= M <=600), и завод изготовил по шаблонам N секций ( N <= 6000). Пример секции с L = 7 изображен на рисунке.

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

Впрочем, дело несколько упрощается – внутренняя (обращённая в парк) сторона секции отличается по цвету от внешней стороны, поэтому можно сказать с уверенностью, что измерения высот секции проделаны в том же порядке, что и в шаблоне.

 

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

Все данные разделяются одним пробелом. Последние данные в строке завершаются символом перевода строки.

Первая строка содержит количество тестов. Далее идут данные тестов.

Первая строка данных теста содержит значения L (число точек в шаблоне и секции), M (число различных шаблонов), N (число найденных секций).

Далее M строчек содержат информацию о шаблоне: номер шаблона (натуральное число) и L точек шаблона.

Далее N строчек содержат информацию о секциях забора, в каждой строке содержится L точек одной  секции забора.

 

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

В первой строке выводится слово TEST и через пробел номер теста.

Затем следует N строк, каждая строка содержит номер шаблона, с которым совпала секция, либо, если подходящего шаблона не найдено, то выводится символ дефиса '-'.

В последней строке теста выводится слово ”OK=” (без кавычек) и число секций, сопоставленных с шаблонами, через пробел символы ”BAD=” и число испорченных секций.


Пример входных данных

2

4 2 4

1 250 123 0 66

2 22 31 120 100

250 123 0 66

22 31 120 100

25 31 120 100

250 123 0 66

3 3 4

1 55 11 12

3 33 1 2

2 14 15 2

55 11 12

14 15 2

33 1 2

14 15 2

          

Пример выходных данных

TEST 1

1

2

-

1

OK=3 BAD=1

TEST 2

1

2

3

2

OK=4 BAD=0

SnarkNews Winter Series – 2009, раунд 2.

B Building

Input file: building.in, output file:  building.out.

Time Limit: 2 seconds, Memory Limit: 64 Mebibytes

Администрация города подбирает площадку для строительства новых спортивных сооружений. На рассмотрении несколько проектов, каждый проект требует выделения  некоторого прямоугольного участка земли. Некоторые участки оказались частично или полностью в пользовании частными лицами, а в случае утверждения проекта администрация будет вынуждена выкупить этот участок, поэтому для определения стоимости очень важно знать площадь пересечения участков. Участки частников также прямоугольной формы (рис. 1) и стороны всех участков параллельны координатным осям. Для каждого проекта был построен план, включающий подобранный участок и его окружение. В приведенном примере показано пересечение участков частников (тонкая линия) с участком, подобранным для строительства (толстая линия). Помогите определить площадь пересечения для каждого подобранного участка для строительства с участками частников.

X2

 

X1

 

Y2

 

Y1

 

Рис. 1.

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

В первой строке входного файла содержится число К – количество, подобранных для строительства участков. Далее описывается план каждого участка: в первой строке описания содержится число N - количество участков частников, отображенных на плане. Затем следуют N строк с координатами двух вершин этих прямоугольных участков. В последней строке плана координаты участка, подобранного для строительства. Координаты одного прямоугольника описываются в формате X1 Y1 X2 Y2. Координатами вершин являются целые, неотрицательные числа, не больше 100. Количество исходных прямоугольников не больше 20.

Пример входных данных

2

1

15 15 25 25

10 10 20 20

2

15 15 25 25

5  5  12 12

10 10 20 20

 

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

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

Пример выходных данных

25

29

SnarkNews Winter Series – 2009, раунд 2.

C – Jammed

Input file: jammed.in, output file:  jammed.out.

Time Limit: 4 seconds, Memory Limit: 64 Mebibytes

 

Всем известна игра 15, где надо выстроить изначально неупорядоченную последовательность чисел, перемещая фишки с нанесёнными числами от 1 до 15 в квадрате 4×4. На основе данной игры была разработана другая – поле в ней лишь 4×2 клетки, на поле 7 фишек, но на фишках изображены буквы латинского алфавита и арабские цифры (на каждой фишке – один символ, но на разных фишках могут быть одинаковые символы). Цель игры прежняя – упорядочить в соответствии с образцом стартовую расстановку фишек за минимальное количество ходов.

Свободная клетка обозначается специальным символом # и используется для перемещения фишек по полю. Перемещать фишки на свободную клетку разрешается из соседних клеток, имеющих общую грань со свободной. Например, на рисунке более правый символ 0 можно переместить вниз на свободную клетку, тогда 0 будет в нижней клетке, а пустой станет верхняя клетка, либо в свободную клетку переместить букву C или цифру 2.

 

M

0

0

A

8

C

#

2

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

Первая строка содержит количество тестов (не больше 100). Далее в каждом тесте содержится четыре строки: две первые строки содержат стартовую комбинацию символов, следующие две - образец. Каждая строка содержит 4 символа (латинский алфавит и арабские цифры), пустая клетка обозначается символом #. Тесты разделены между собой пустой строкой.


Пример входных данных

2

ACM8

002#

ACM#

2008

 

rogp

mar#

prog

ram#

 

 

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

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

Пример выходных данных

 

           17

26

 

SnarkNews Winter Series – 2009, раунд 2

D – Hadron Collider

 

Input file: hadron.in, output file:  hadron.out.

Time Limit: 2 seconds, Memory Limit: 64 Mebibytes

 

 

Внутри адронного коллайдера образовалось N разновидностей новых частиц в количестве A1, … ,AN единиц каждая. Большая часть новых частиц, однако, успевает прореагировать между собой раньше, чем эти частицы сможет уловить детектор, поэтому физикам очень важно предсказать конечный итог реакции между частицами.

Для простоты будем считать, что в реакции участвуют 2 частицы, с одним из следующих результатов, в зависимости от типа:

·     Первая частица уничтожает вторую

·     С одинаковыми шансами или первая частица уничтожает вторую, или вторая уничтожает первую

·     Частицы отскакивают друг от друга без какого-либо вреда

Необходимо определить все возможные исходы эксперимента.

 

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

Каждый тест описывается набором чисел: первое число задает количество видов частиц N (1 ≤ N ≤ 4). В следующей строке N чисел определяют начальное количество частиц каждого типа Ai (1 ≤ Ai ≤ 2). Следующие N строк  формируют матрицу A[N][N]. Ненулевое значение ячейки Аij указывает, что частица типа i при столкновении уничтожает частицу типа j. При этом столкновение двух частиц может привести к уничтожению ровно одной из них. Далее начинается описание следующего теста. Тест с N = 0 означает окончание входных данных.

 

Пример входных данных:

3

1 1 2

0 0 1

1 0 0

1 1 1

1

2

0

0

 

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

Первая строка теста является заголовком следующего вида TEST n: (Где n номер теста, нумерация начинается с 1). Следующие строки содержат лексикографически упорядоченные всевозможные исходы эксперимента, один вариант эксперимента в каждой строке по N чисел.

 

Пример выходных данных:

TEST 1:

0 0 1

0 1 0

1 0 0

TEST 2:

2

SnarkNews Winter Series – 2009, раунд 2

 

E – Agent

 

Input file: agent.in, output file:  agent.out.

Time Limit: 2 seconds, Memory Limit: 64 Mebibytes

 

 

Агент Джеймс Бонд пошел на пенсию, но неугомонный характер требовал новых впечатлений. Поэтому Джеймс Бонд с удовольствием согласился провести мастер-класс в некоторых группах школы «Молодого агента». Тема одного из занятий – работа агента с напарником. В таком опасном деле, как разведка, важно иметь очень надёжного напарника, поэтому напарниками могут стать только агенты, которые максимально близки по возрасту (т.е. два агента не могут стать напарниками, если в группе существует третий агент, который старше одного и младше другого).

Задание Бонда состоит в том, чтобы агенты нашли друг другу напарников таким образом, чтобы у каждого агента был хотя бы один напарник (всего у агента может быть 2 напарника – один младше, и один старше него, но эти двое не считаются напарниками между собой). Очевидно, что группа из 4 и более агентов может поделиться несколькими способами.

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

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

В первой строке входного файла находится одно целое число M (1M12) – количество групп, в которых проводит мастер-класс Джеймс Бонд. Далее последовательно идёт M описаний группы. Описание каждой группы состоит из двух строк. В первой строке находится одно целое число N – количество агентов в группе (2N10000). Во второй строке находятся N пар целых положительных чисел, разделённых пробелом. Первое число в паре – это возраст агента (в днях) из диапазона [5000, 16000], второе – риск раскрытия агента, число в диапазоне [1, 1000]. Известно, что в любой группе все агенты разного возраста.

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

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

Пример входных данных

2

3

6000 2 5500 3 5000 4

5

5005 1 5004 2 5003 3 5002 4 5001 5

Пример выходных данных

5

7

Комментарии к примеру: в первой группе выбирать себе напарников не приходится – вариант разделения всего один: пара 6000-5500 (риск 2) и пара 5500-5000 (риск 3).

Во второй группе агенты 5005 и 5001, как крайние по возрасту, без вариантов получают в качестве напарников 5004 и 5002 соответственно. А вот оставшийся без напарника агент 5003 может выбрать себе 5004 либо 5002. В паре с 5004 риск меньше (2 против 3), поэтому оптимальное разделение имеет суммарный риск 1 + 2 + 4 = 7.

SnarkNews Winter Series-2009, раунд 2

F - Intersections

Input file: intersections.in, output file:  intersections.out.

Time Limit: 2 seconds, Memory Limit: 64 Mebibytes

Известно, что в Старгороде строится объездная автодорога. Она не является кольцевой, то есть имеет западное и восточное окончание (кто знает - может только пока?). Наиболее интересными инженерными объектами на дороге, являются конечно же мосты. Очевидно, что железобетонный мост слишком дорогой для участка с одним автомобилем в день, а деревянный мост не способен обслуживать шоссе с десятком машин в минуту. Поэтому для оправданного проектирования мостов необходимо знать, сколько автомобилей проезжает через мост.

На дороге будут использоваться преимущественно развязки "клеверный лист", схема такой развязки изображена на рисунке. Согласно этой схеме, автомобиль, поворачивающий направо - не едет через мост, автомобиль поворачивающий налево (по этой развязке он поворачивает на 270 градусов направо и пересекает свой путь на другом уровне) - всегда едет через мост, и автомобиль, проезжающий прямо - может ехать, а может не ехать через мост, тут всё зависит от направления движения.

Исследован поток автомобилей, которые едут по дорогам, пересекающим объездную дорогу. Необходимо посчитать поток автомобилей, которые поедут через мосты объездной дороги. Следует помнить, что для некоторых перекрёстков объездная дорога проходит по земле, а мост содержит поперечная дорога - считать такие мосты не требуется. Хоть дорога двусторонняя, один тест исследует только одно направление объездной дороги (например, с запада на восток).

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

Первая строка входа содержит количество тестов. Первая строка каждого теста содержит число N≤100 – количество перекрёстков, перекрёстки перечислены с запада на восток. Следующие N строк содержат информацию о типе пересечения, затем о потоке поперечной дороги. Тип пересечения - латинская буква L, означает что объездная дорога проходит по земле, а поперечная проходит через мост, буква B означает что поперечная дорога проходит по земле, а объездная через мост. Далее указаны 2 числа, показывающее количество автомобилей, покинувших объездную дорогу, первое число - с поворотом налево, второе - с поворотом направо. Далее указаны 2 числа, показывающее количество автомобилей, выехавших на объездную дорогу, первое число - с поворотом налево, второе - с поворотом направо. Количество машин по любой из поперечных дорог не превышает 109.

Гарантируется корректность входных данных (изначально на трассе машин нет, покинуло трассу столько же машин, сколько и заехало на трассу, точка перекрёсток схода находится позднее перекрёстка захода).

 

Пример входных данных

2

2

B 0 0 2 3

B 4 1 0 0

5

B 0 0 9 9

B 0 0 0 0

L 3 3 0 0

B 0 0 0 0

B 8 4 0 0

 

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

Для каждого теста в выходной файл выводится одна строка, содержащая N чисел - потоки машин на мост объездной дороги. Если объездная дорога проходит по земле, а мост - над ней, то выводится -1.

Пример выходных данных

2 4

9 18 -1 12 8