Подзадачи

Программа, проходящая все тесты с N, M ≤ 50, набирает 10 баллов.

Всероссийская олимпиада школьников. Муниципальный этап

Классы

Задача B. «Разноцветный забор»

Имя файла с исходным текстом программы: fence

Входной файл: input.txt

Выходной файл: output.txt

Ограничение по времени: 5 секунд

Ограничение по памяти: 64M байт

Максимальная оценка: 20 баллов

Митя красит забор на дачном участке. У него есть несколько различных красок, и Митя пока подбирает наилучшую цветовую гамму. Он берёт какую-нибудь краску и красит ею прямоугольный кусок забора. Затем берёт другую краску (иногда ту же самую) и красит другой прямоугольный кусок. Иногда этот кусок пересекается с ранее покрашенным куском. У Мити происходит творческий процесс, поэтому он не очень внимательно следит за расположением закрашенных участков. В результате забор оказывается покрытым разноцветными пересекающимися прямоугольниками.

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

Вход

В первой строке входного файла записаны два натуральных числа N и K - количество прямоугольников, закрашенных Митей и количество различных красок (1 ≤ N, K ≤ 1000). В остальных строках записано N пятёрок целых чисел X1, Y1, X2, Y2, C – координаты левого нижнего и правого верхнего углов закрашенного прямоугольника и номер краски, которой он был закрашен (-10⁶ ≤ X1, Y1, X2, Y2 ≤ 10⁶, 1 ≤ C ≤ K).

Выход

Для каждой краски от 1 до K запишите в выходной файл площадь забора, которая в итоге оказалась покрашенной в данный цвет.

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

input.txt	output.txt
3 4 -10 -10 10 10 1 -11 -11 9 9 2 9 9 11 11 3	38 400 4 0

Подзадачи

Программа, проходящая все тесты с -100 ≤ X1, Y1, X2, Y2 ≤ 100, набирает 10 баллов.

Всероссийская олимпиада школьников. Муниципальный этап

Классы

Задача C. «Из пустого в порожнее»

Имя файла с исходным текстом программы: flood

Входной файл: input.txt

Выходной файл: output.txt

Ограничение по времени: 1 секунда

Ограничение по памяти: 64M байт

Максимальная оценка: 20 баллов

Имеется N сосудов ёмкостью V₁, V₂, …, V_N, в которых первоначально налито W₁, W₂, …, W_N воды. Затем начинается переливание. Берут какой-нибудь сосуд и переливают из него Q воды в другой сосуд. Если в первом сосуде оказывается меньше, чем Q воды, то вся она выливается. Если во второй сосуд не умещается вся переливаемая вода, то излишки выливаются на пол и пропадают. Ваша задача – по известной последовательности переливаний определить, сколько воды останется в каждом из сосудов.

Вход

В первой строке входного файла записаны целые числа N и K (2 ≤ N ≤ 1000, 1 ≤ K ≤ 10⁶). Во второй строке записано N целых чисел V₁, V₂, …, V_N (0 ≤ V_i ≤ 10⁶). В третьей строке записано N целых чисел W₁, W₂, …, W_N (0 ≤ W_i ≤ V_i). В остальных строках файла записано K троек целых чисел a, b, Q – номер сосуда, из которого переливают, номер сосуда, в который переливают, и количество переливаемой воды (1 ≤ a, b ≤ N, a ≠ b, 0 ≤ Q ≤ 10⁶).

Выход

Для каждого сосуда запишите в выходной файл количество воды, оставшееся в нём после всех переливаний.

Дата добавления: 2015-07-08