#112821

Фонари

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2015, 2 тур, Задача C ]

Улицу Подводный канал освещают \(n\) фонарей, пронумерованных вдоль улицы от 1 до \(n\). Один или несколько подряд стоящих фонарей назовём сегментом. Таким образом, общее количество сегментов равно \(n(n+1)/2\) . Сегмент считается исправным, если лампочки во всех фонарях этого сегмента исправны.

С фонарями регулярно происходят события одного из двух типов:

• в каком-то сегменте из-за скачков напряжения все лампочки одновременно перегорают;

• Архиэнерго выбирает некоторый сегмент и посылает ремонтников, чтобы заменить на нем все перегоревшие лампочки на исправные.

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

Требуется написать программу, определяющую количество сегментов после каждого события, которые исправны в этот момент или были исправны когда-либо до этого события.

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

В первой строке входных данных содержатся два числа \(n\) и \(q\) — количество фонарей и количество произошедших событий. Следующая строка входных данных состоит из \(n\) символов 0 и 1, описывающих начальное состояние фонарей, где 1 обозначает фонарь с исправной лампочкой, а 0 — с перегоревшей.

В каждой из последующих q строк содержатся описания событий в виде трёх чисел \(l_i\) , \(r_i\) и \(c_i\) , которые означают, что после этого события все лампочки в фонарях с номерами \(l_i\) , \(l_i\) + 1, . . . , \(r_i\) :

• перегорают при \(c_i\) = 0,

• становятся исправными при \(c_i\) = 1.

В описаниях всех событий \(1 \le l_i \le r_i \le n\), а \(c_i\) принимает значение 0 или 1.

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

В первой строке выходных данных выведите единственное число — количество исправных сегментов в начальном состоянии. Затем по одному в строке выведите \(q\) чисел: для каждого из произошедших событий выведите количество сегментов, указываемых в отчёте после этого события.

Таблица системы оценивания

Примеры

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

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

#112822

Сигнализация

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2015, 2 тур, Задача D ]

Подземный бункер состоит из \(n\) комнат, соединённых \(n − 1\) коридорами. Каждый коридор соединяет две различные комнаты и имеет определённую длину. Бункер устроен таким образом, что из любой комнаты \(i\) можно дойти в любую другую комнату \(j\). Заметим, что существует единственный такой путь, не проходящий по одному и тому же коридору дважды. Сумма длин коридоров, составляющих этот путь, называется расстоянием между комнатами \(i\) и \(j\) и обозначается \(ρ(i, j)\).

Каждая комната бункера оборудована звуковой сигнализацией, состоящей из сирены и датчика звука, который её включает. Сирена, включённая в комнате \(i\), активирует датчик звука в каждой комнате, рас- стояние до которой не превосходит расстояние \(d_i\) , определяемое мощностью этой сирены. Другими словами, включение сирены в комнате \(i\) автоматически включает сирену во всех комнатах \(j\), таких что \(ρ(i, j) \le d_i\) . Эта сирена, в свою очередь, может вызвать автоматическое включение других сирен и так далее.

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

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

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

Первая строка входных данных содержит единственное число \(n\) — количество комнат.

Вторая строка содержит последовательность из \(n\) целых чисел \(d_i\) , \(i\)-е из них равно максимальному расстоянию, на котором расположенная в комнате \(i\) сирена активирует датчики (\(0 \le d_i \le 10^9\) ).

Последующие n−1 строк описывают коридоры бункера. В \(i\)-й из них находятся три целых числа: \(u_i\) , \(v_i\) , \(l_i\) , где \(u_i\) , \(v_i\) — номера различных комнат, соединённых коридором \(i\), а \(l_i\) — длина этого коридора (\(1 \le u_i , v_i \le n; 1 \le l_i \le 10^9\) ).

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

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

Таблица системы оценивания

Замечания

В тесте из примера сирена в комнате 4 включает сирену в комнате 5, которая, в свою очередь, включает сирены в комнатах 6 и 7. Сирена в комнате 2 включает сирену в комнате 3. Сирена в комнате 8 включает сирены в комнатах 1, 9 и 10.

Примеры

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

10
1 2 2 2 6 3 4 5 4 3
1 2 5
2 3 1
2 4 5
4 5 2
4 6 4
4 7 3
1 8 1
8 9 5
8 10 4

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

#112827

Тройка

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Москва, 2014, Задача A ]

У Олега есть карта «Тройка», на которой осталась одна поездка на наземном транспорте. От дома Олега до школы можно доехать на трамвае, троллейбусе или автобусе. Трамвай ходит через каждые 15 минут, троллейбус — через каждые 10 минут, автобус — через каждые 5 минут, при этом в 8:00 одновременно от остановки отправляются и трамвай, и троллейбус, и автобус (то есть трамвай отправляется в 8:00, 8:15, 8:30, 8:45, 9:00; троллейбус — в 8:00, 8:10, 8:20, 8:30, 8:40, 8:50, 9:00; автобус — в 8:00, 8:05, 8:10, 8:15 и т. д.). Трамвай едет до нужной остановки X минут, троллейбус — Y минут, автобус — Z минут. Когда Олег пришёл на остановку, на часах было 8 часов M минут. Определите минимальное время, через которое Олег окажется на нужной ему остановке (считая время ожидания транспорта и время поездки на транспорте). Если какой-то транспорт отправляется в тот же момент, когда Олег пришёл на остановку, то Олег успевает на нём уехать.

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

Программа получает на вход сначала три целых положительных числа X , Y , Z , не превосходящие 100, записанные в отдельных строчках, — время поездки на трамвае, троллейбусе, автобусе соответственно. В четвёртой строке входных данных записано целое число M ( 0 ≤ M ≤ 59 ) — момент времени (в минутах), когда Олег пришёл на остановку.

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

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

Примечание

Олег пришёл на остановку в 8:12. Ему нужно подождать 8 минут и сесть на троллейбус, который довезёт его за 10 минут.

Примеры

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

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

#112828

Заработная плата

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Москва, 2014, Задача B ]

В некоторой компании работают три сотрудника — Алексей, Виктор и Сергей. Их месячный оклад составляет A , B и C рублей соответственно. При этом Алексей работает на полную ставку, а Виктор и Сергей — на половину ставки, то есть работают вдвое меньше, чем Алексей.

По итогам месяца директор компании хочет распределить между этими сотрудниками премиальный фонд, который составляет N рублей. При этом директор хочет распределить премиальный фонд таким образом, чтобы итоговая зарплата (сумма оклада и премии) у этих сотрудников оказалась пропорциональна проведённому на работе времени, то есть зарплата Алексея должна оказаться ровно в два раза больше, чем зарплата Виктора и Сергея. Более формально, если премия Алексея составит x рублей, премия Виктора — y рублей, премия Сергея — z рублей, то A + x = 2 × ( B + y ) = 2 × ( C + z ) , x + y + z ≤ N . При этом бухгалтерия требует, чтобы размер премии (как и размер оклада) выражался целым числом рублей, а директор хочет распределить максимально большую часть премиального фонда, то есть сумма x + y + z должна быть максимально возможной, не превышая при этом N .

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

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

Программа получает на вход сначала три целых числа A , B , С , записанные в отдельных строках, — размеры окладов Алексея, Виктора и Сергея ( A > 0 , B > 0 , С > 0 ). В четвёртой строке входных данных записано одно целое число N — размер премиального фонда ( N \(\ge\) 0 ).

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

Программа должна вывести три числа — размер премии Алексея, Виктора и Сергея. Если премиальный фонд нельзя распределить так, чтобы выполнялись требуемые условия, программа должна вывести одно число 0.

Примечание

В первом тесте: с учетом премии зарплата Алексея составит 12 рублей, Виктора и Сергея — 6 рублей.

Во втором тесте: Добиться нужного соотношения премиальных выплат невозможно.

Ограничения и система оценивания

Решение, которое выводит правильный ответ только на тестах из условия и тех тестах, на которых ответом является «0», будет оцениваться в 0 баллов.

Решение, правильно работающее в случае, когда все входные числа не превосходят 100, будет оцениваться в 30 баллов.

Решение, правильно работающее в случае, когда все входные числа не превосходят 10 ⁵ , будет оцениваться в 60 баллов.

Решение, правильно работающее в случае, когда все входные числа не превосходят 10 ⁹ , будет оцениваться в 100 баллов.

Примеры

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

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

5
3
2

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

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

#112829

Ремонт дороги

Темы: [Жадный алгоритм]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Москва, 2014, Задача C ]

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

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

Определите, какое наименьшее количество компаний-подрядчиков необходимо привлечь для ремонта дороги.

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

Первая строка входных данных содержит целое число L ( L > 0 ) — максимальную длину фрагмента дороги, который может отремонтировать одна компания. Во второй строке входных данных записано целое число N ( N > 0 ) — длина всей дороги. Следующие N строк содержат по одному числу, равному 0 или 1. Число 1 обозначает, что соответствующий участок дороги нуждается в ремонте, число 0 — что участок не требует ремонта.

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

Программа должна вывести одно целое число — минимальное количество компаний-подрядчиков, которое необходимо привлечь для ремонта дороги.

Примечание

В тесте из примера первая компания может отремонтировать участок номер 3, вторая компания — участки с 5 по 7.

Ограничения и система оценивания

Решение, правильно работающее в случае, когда числа L и N не превосходят 10, будет оцениваться в 30 баллов.

Решение, правильно работающее в случае, когда числа L и N не превосходят 1000, будет оцениваться в 60 баллов.

Решение, правильно работающее в случае, когда числа L и N не превосходят 10 ⁵ , будет оцениваться в 100 баллов.

Примеры

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

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