--->
8 задач
<---
#1977
Темы:
[Задачи на моделирование]
Источники:
[
Личные олимпиады,
Открытая олимпиада школьников,
2009-2010,
Заключительный этап,
Задача A
]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Из описания некоего растения: «… его время жизни составляет 20 лет. В первый год плод растения попадает в землю. Первые побеги растения появляются лишь на второй год. Плодоносить растение начинает с четвертого года и ежегодно дает по 1 плоду, которые сразу попадают в землю, и из них вырастают такие же растения. На двадцатый год своей жизни растение плодоносит в последний раз, а на двадцать первый год – погибает».
Напишите программу, которая определяет, сколько живых растений будет в N-м году, если в первый год мы посадим один плод этого растения. Только что посаженные плоды за растения не считаются. Также не считаются живыми растения, для которых данный год является 21-м (или больше) годом жизни.
Замечания
Из описания следует, что плод, который появился в 4-м году, сразу попадает в землю, и этот год считается 1-м годом жизни нового растения (при этом при подсчете числа живых растений в этом году данное растение еще не будет учтено). Это растение даст первые побеги в 5-м году, начнет плодоносить — в 7-м, а последний раз будет плодоносить в 23-м году и перестанет быть живым – в 24-м.
При подсчете числа живых растений в 20-м году исходное растение еще считается живым, а в 21-м — уже не считается.
Входные данные
Вводится единственное натуральное число N, не превышающее 100.
Выходные данные
Выведите единственное число – сколько живых растений будет в N‑м году. Только что посаженные плоды за растения не считаются.
Комментарий к примеру тестов
1. Первые три года растение не плодоносит, на четвертый год оно дало 1 плод, но он еще не считается полноценным живым растением.
2. Первые 3 года у нас есть 1 растение, на 4-й год оно дает 1 плод; на 5-й год этот плод прорастает, а исходное растение дает еще 1 плод; на 6-й год второй плод прорастает, исходное растение дает плод, который растением еще не считается.
3. Начиная с 4-го года, исходное растение начинает давать по одному плоду (и дает по плоду на 4-м, 5-м, 6-м, 7-м, 8-м,… годах). Растение, которое получилось из плода, который появился на 4-м году, начинает плодоносить с 7-го года (и дает плоды на 7-м, 8-м, … годах). Растение, которое получилось из плода, который появился на 5-м году, начинает плодоносить с 8-го года. При этом все плоды, появившиеся на 9-м году, растениями еще не считаются. Итого, учитывая исходное растение, у нас будет 9 растений.
Система оценивания
| Подзадача | Баллы | Ограничения | Необходимые подзадачи |
| 1 | 30 | \(n \le 15\) | тесты |
| 2 | 30 | \(n \le 40\) | 1 |
| 3 | 40 | Нет дополнительных ограничений | 2 |
Примеры
Входные данные
4
Выходные данные
1
Входные данные
6
Выходные данные
3
Входные данные
9
Выходные данные
9
#112034
Источники:
[
Личные олимпиады,
Открытая олимпиада школьников,
2012-2013,
Заключительный этап - второй тур,
Задача C
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Как известно, автобус должен ходить по расписанию. И Иннокентий, используя свои многочисленные связи в магазине плитки, совершил невозможное: по маршруту теперь курсируют целых \(M\) автобусов, и на каждой остановке висит свое расписание, которое представляет собой набор из \(M\) времен. Плиточный магнат является крупным авторитетом в городе, поэтому расписание соблюдается: от каждой остановки ровно в каждое из указанных времен отправляется автобус. Казалось, что проблема общественного транспорта навсегда решена...
Однако, дьявол кроется в деталях. Действительно, автобусы отправляются с остановок в нужные времена, но никто не гарантирует, что между остановками не произойдет обгон, и автобус, который отправился от предыдущей остановки раньше, не отправится со следующей гораздо позже, при этом не нарушая условия, что в каждое из указанных в расписании времен какой-то автобус отправляется.
Иннокентий решил оценить масштабы трагедии. Для этого он попросил каждого из Q своих друзей сообщить маршрут, по которому они добираются до места работы. Каждый маршрут описывается тремя числами \(u_i\), \(v_i\), \(w_i\): \(u_i\) — это номер остановки, ближайшей к дому i-го друга, \(v_i\) — номер остановки, ближайшей к его работе, а \(w_i\) — номер автобуса,на котором i-й друг едет из дома на работу. При этом с точки зрения i-го друга автобусы нумеруются от \(1\) до \(M\) в том порядке, в котором они отправляются с остановки \(u_i\).
Иннокентий просит вас независимо для каждого друга определить, насколько поздно тот может доехать до конечной остановки своего маршрута.
Входные данные
В первой строке входных данных содержатся два целых числа \(N\) и \(M\) — количество остановок и количество автобусов соответственно (\(2 \le N * M \le 150 000\)). В следующей строке содержатся \(N-1\) целых чисел \(travel_1\), . . . , \(travel_{N-1}\), где \(travel_i\) — минимальное время, необходимое для перемещения между остановками i и i + 1 (\(1 \le travel_i \le 10^9\)).
В следующих \(N\) строках содержатся описания расписаний, каждое из которых представляет собой отсортированный по возрастанию список из \(M\) различных целых чисел \(t_i\) — времен, в которые автобусы должны отправляться с соответствующей остановки (\(1 \le t_i \le 10^9\)).
В следующей строке содержится число T — тип теста (1 или 2). Если T = 1, то это — обычный тест. Тогда на следующей строке содержится целое число Q — количество опрошенных друзей Иннокентия (\(1 \le Q \le 150 000 \)). Далее в Q строках содержатся описания маршрутов друзей, каждое из которых состоит из трех целых чисел \(u_i\), \(v_i\) и \(w_i\): номеров остановок, где начинается и заканчивается поездка i-го друга, и номер автобуса в расписании остановки ui, на котором эта поездка совершается (\(1 \le u_i < v_i \le N, 1 \le w_i \le M\)).
\textbf{Обратите внимание} : дальнейшее описание относится только к последней группе тестов. Если T = 2, то это — тест-серия. Тогда на следующей строке содержатся три целых числа — A, B и K (\(1 \le A, B \le 10^3 , 1 \le K \le 150\)).
В \t{тесте-серии} у Иннокентия Q = (N -1)·M ·K друзей. На каждой из N - 1 остановок, кроме последней, проживает ровно M * K друзей, причем для каждого \(w\) от 1 до M есть ровно K друзей, которые уезжают с этой остановки w-м автобусом.
Остановки, до которых едут K друзей, уезжающих с u-й остановки w-м автобусом, определяются следующим образом. Задается последовательность чисел \(q_i\): \(q_1\) = A, \(q_2\) = B, для i > 2 \(q_i\) = u * \(q_{i-1}\) + w * \(q_{i-2}\) + 42. Тогда i-й из этих K друзей будет ехать до остановки с номером \(v_i\) = u + 1 + (\(q_i\) mod (N - u)), где mod обозначает операцию взятия остатка от деления.
Выходные данные
Если это обычный тест, то выведите для каждого друга в отдельной строке единственное целое число - искомое максимальное время прибытия на конечную остановку в его маршруте. Если это тест-серия, то выведите единственное целое число — остаток от деления суммы максимальных времен прибытия для всех друзей Иннокентия на \(2^{32}\).
Примечание
Приведем пояснение ко второму тесту из условия.
Это \textbf{тест-серия}. В нем у Иннокентия 5 · 4 · 2 = 40 друзей. Например, с первой остановки вторым автобусом уезжают ровно пять друзей. Поясним, как в этом тесте для них определить конечные остановки. u = 1, w = 2. Строим последовательность \(q_i\): \(q_1\) = 9, \(q_2\) = 10, \(q_3\) = 1 · 10 + 2 · 9 + 42 = 70, \(q_4\) = 1 · 70 + 2 · 10 + 42 = 132, \(q_5\) = 1 · 132 + 2 · 70 + 42 = 314. По ней восстанавливаются конечные остановки для этих пяти друзей Иннокентия: \(v_1\) = 1 + 1 + (9 mod 4) = 3, \(v_2\) = 1 + 1 + (10 mod 4) = 4, \(v_3\) = 1 + 1 + (70 mod 4) = 4, \(v_4\) = 1 + 1 + (132 mod 4) = 2, \(v_5\) = 1 + 1 + (314 mod 4) = 4.
Система оценки
Тесты к этой задаче состоят из шести групп. Каждая группа, кроме нулевой, оценивается в 20 баллов. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов \textbf{предыдущих групп}, исключая тесты из условия. В группах тестов с первой по четвертую включительно вам предлагаются только обычные тесты.
0. Тесты 1—2. Тесты из условия, оцениваются в ноль баллов.
1. Тесты 3—12. В тестах этой группы \(N = 2, M \le 1 000, Q \le 1 000\).
2. Тесты 13—22. В тестах этой группы \(N = 2, M \le 75 000, Q \le 75 000\).
3. Тесты 23—37. В тестах этой группы \(N * M \le 150 000, N * Q \le 150 000\).
4. В тестах этой группы \(N * M \le 150 000, Q \le 150 000\).
5. В этой группе вам предлагаются только тесты-серии. Другие дополнительные ограничения отсутствуют.
Примеры
Входные данные
2 3 1 1 10 21 11 21 31 1 3 1 2 1 1 2 2 1 2 3
Выходные данные
21 21 31
Входные данные
5 2 2 5 3 4 1 3 3 5 10 11 13 14 18 23 2 9 10 5
Выходные данные
667
#112772
Темы:
[Задачи на моделирование]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes
Улица М. города Д. печально известна среди местных жителей качеством дорожного покрытия. В этом тяжело винить ремонтные службы: пожалуй, они следят за этой улицей даже слишком тщательно. Проблема в том, что каждый без исключения ремонт улицы выглядит следующим образом: бригада рабочих выбирает некоторый участок улицы единичной длины и меняет асфальт только на нём, причём тип асфальта на этом участке в результате может отличаться от типов асфальта на других участках, что, разумеется, усложняет проезд по улице.
Вы, как коренной житель города Д. и программист по призванию, решили использовать свои профессиональные навыки на благо общества и облегчить жизнь своим соседям по улице \(М\). А именно, вы решили создать сайт, содержащий актуальную информацию о непроходимости улицы. Прежде всего, вы заметили, что улица разбита на N идущих друг за другом участков единичной длины. По странному совпадению бригада рабочих всегда выбирает для ремонта ровно один из таких участков и целиком меняет тип асфальта на нём. Затем вы пронумеровали эти участки от 1 до \(N\) и собрали информацию о типе асфальта на каждом из участков — числа \(t_1, t_2, ... , t_N\) (\(t_i\) — номер типа асфальта на \(i\)-м участке, согласно Государственному реестру дорожных покрытий). Наконец, вы определили непроходимость улицы как минимальное количество непрерывных непересекающихся отрезков c одинаковым типом асфальта, на которые она разбивается. Например, непроходимость улицы 110111 равна \(3\), потому что она состоит из трёх участков 11, 0 и 111, а идеальная улица 2222 имеет непроходимость, равную \(1\).
Казалось бы, достаточно вычислить и разместить на сайте текущую величину непроходимости улицы, и жители будут довольны? К сожалению, асфальт меняют довольно часто, и вам не хочется каждый раз выходить на улицу и заново собирать данные. Поэтому вы дали возможность жителям сообщать на вашем сайте об обновлении дорожного покрытия. Дело осталось за малым — научиться обновлять после каждого такого сообщения актуальную величину непроходимости улицы.
Входные данные
Первая строка входного файла содержит единственное натуральное число \(N\) — количество участков дороги \((1 \le N \le 100 000)\). Следующая строка содержит \(N\) целых чисел \(t_1, t_2, ... , t_N\) — исходные типы асфальта участков дороги \((|t_i | \le 10^9)\).
Третья строка содержит единственное натуральное число \(Q\) — количество сообщений от жителей об обновлении дорожного покрытия \((1 \le Q \le 100 000)\). Каждая из следующих \(Q\) строк содержит очередное сообщение.
\(i\)-е сообщение представляет собой пару целых чисел \(p_i\) , \(c_i\) — номер ремонтируемого участка дороги и новый номер типа асфальта на этом участке \((1 \le p_i \le N, |c_i | \le 10^9)\). Участки дороги нумеруются от 1 до \(N\) в порядке задания их исходного типа асфальта во второй строке входного файла.
Выходные данные
Выведите \(Q\) строк. \(i\)-я строка (\(1 \le i \le Q\)) должна содержать единственное целое число — величину непроходимости улицы после первых \(i\) обновлений дорожного покрытия.
Замечание
Рассмотрим подробнее второй тестовый пример. Изначально улица 1123221 состоит из 5 отрезков с одинаковым типом асфальта: 11, 2, 3, 22, 1 и, соответственно, имеет непроходимость, равную 5 (её не нужно выводить в выходной файл).
После первого ремонта улица станет выглядеть как 1223221 и всё ещё будет состоять из 5 участков, но других: 1, 22, 3, 22, 1. Поэтому её непроходимость равна 5, и первое число в выходном файле равно 5.
После второго ремонта улица будет состоять из 3 участков: 1, 22222, 1, так что второе число в выходном файле — 3.
После третьего ремонта получим 4 участка: 1, 2222, 9, 1, соответственно, третье и последнее число в выходном файле — 4.
Система оценки
Тесты к этой задаче состоят из трёх групп. Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
Примеры
Входные данные
5 2 2 2 2 2 5 1 2 2 3 4 3 3 1 3 3
Выходные данные
1 3 5 5 3
Входные данные
7 1 1 2 3 2 2 1 3 2 2 4 2 6 9
Выходные данные
5 3 4
Выбрано
:
|