Страница: << 94 95 96 97 98 99 100 >> Отображать по:

#112589

Министерство

Темы: [Алгоритмы на графах] [Хеш]

Источники: [ Личные олимпиады, Central European Olympiad in Informatics , Central European Olympiad in Informatics 2007, Министерство ]

Однажды в далекой-далекой стране правительство создало Министерство по сокращению бумажной волокиты. Как вы наверное догадались, это было крупнейшее министерство за всю историю страны. Количество сотрудников было поистине огромным. Несмотря на это, структура министерства была очень простой: каждый сотрудник имел не более трёх подчинённых, каждый из которых снова имел не более трех подчиненных и так далее...

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

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

Есть два особых случая:

Департамент, в котором должностное лицо — сам министр, тогда этот департамент есть всё министерство.
Департамент, в котором у должностного лица нет ни одного подчинённого.

Высотой департамента назовем длину максимальной последовательность сотрудников x ₁ , ..., x _d такую, что сотрудник x _i является начальником сотрудника x _{i

+ 1} для всех 1 ≤ i < d . Заметим что высота департамента, состоящего из одного сотрудника равна 1 .

Два департамента A и B совпадают, если существует взаимно-однозначное отображение, сопоставляющее каждому сотруднику x _A из департамента A сотрудника x _B из департамента B , таким образом, что сотрудник x _A является начальником сотрудником y _A , тогда и только тогда, когда x _B является начальником y _B . Заметим, что если два департамента совпадают, то они имеют одинаковую высоту, одинаковое количество сотрудников и начальнику первого департамента соответствует начальник второго.

На приведенных картинках департаменты A и B совпадают, а C не совпадает ни с A , ни c B .

$\text{[math]}$

Вам необходимо для каждой высоты вычислить количество различных департаментов имеющих такую глубину. Формально требуется построить последовательность n ₁ , ..., n _d , где d это высота всего министерства, а n _i — количество различных департаментов высоты i .

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

Входной файл содержит единственную строку, которая описывает иерархическую структуру министерства, используя следующую нотацию. Каждый департамент кодируются строкой "( x ₁ ... x _k )", где k — количество подчинённых у начальника департамента, а строки x _i — коды им подчиняющихся департаментов. Департамент, состоящий из одного человека, кодируется строкой "()". Структура министерства задается кодом всего министерства. Количество сотрудников министерства не превосходит 1 000 000 (включая министра).

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

Выходной файл должен содержать d строк, где d это высота министерства. i -ая строка должна содержать количество различных департаментов высоты i .

Примечание

Приведенная картинка иллюстрирует пример из условия. $\text{[math]}$

Примеры

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

(((())())((()())(()()()))(()(())))

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

#112744

Выбор зала

Темы: [Формула]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2015, 1 день, Выбор зала ] [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2015, 1 день, Задача A ]

Для проведения церемонии открытия олимпиады по информатике организаторы осуществляют поиск подходящего зала. Зал должен иметь форму прямоугольника, длина каждой из сторон которого является целым положительным числом. Чтобы все участники церемонии поместились в зале, и при этом он не выглядел слишком пустым, площадь зала должна находиться в пределах от $A$ до $B$ квадратных метров, включительно.

Чтобы разместить на стенах зала плакаты, рассказывающие об успехах школьников на олимпиадах, но при этом не создать ощущения, что успехов слишком мало, периметр зала должен находиться в пределах от $C$ до $D$ метров, включительно. Прежде чем сделать окончательный выбор, организаторы олимпиады решили просмотреть по одному залу каждого подходящего размера. Залы с размерами $Y$ × $Z$ и $Z$ × $Y$ считаются одинаковыми. Чтобы понять необходимый объем работ по просмотру залов организаторы задались вопросом, сколько различных залов удовлетворяют приведенным выше ограничениям. Требуется написать программу, которая по заданным $A$, $B$, $C$ и $D$ определяет количество различных залов, площадь которых находится в пределах от $A$ до $B$, а периметр — от $C$ до $D$, включительно.

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

Входной файл содержит четыре разделенных пробелами целых числа: $A$, $B$, $C$ и $D$ (1 ≤ $A$ ≤ $B$ ≤ $10^9$ , 4 ≤ $C$ ≤ $D$ ≤ $10^9$ )

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

Выходной файл должен содержать одно число — искомое количество залов.

Пояснения к примеру

В примере ограничениям удовлетворяют залы следующих размеров: 1 × 2, 1 × 3, 2 × 2

Система оценки и описание подзадач

Подзадача 1 (50 баллов)
1 ≤ $A$ ≤ $B$ ≤ 1000, 4 ≤ $C$ ≤ $D$ ≤ 1000.
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 2 (50 баллов)
1 ≤ $A$ ≤ $B$ ≤ $10^9$,
4 ≤ $C$ ≤ $D$ ≤ $10^9$.
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Примеры

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

2 10 4 8

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

#112749

Вырубка леса

Темы: [Бинарный поиск по ответу]

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

Фермер Николай нанял двух лесорубов: Дмитрия и Федора, чтобы вырубить лес, на месте которого должно быть кукурузное поле. В лесу растут $X$ деревьев.

Дмитрий срубает по A деревьев в день, но каждый $K$-й день он отдыхает и не срубает ни одного дерева. Таким образом, Дмитрий отдыхает в $K$-й, 2$K$-й, 3$K$-й день, и т.д.

Федор срубает по B деревьев в день, но каждый $M$-й день он отдыхает и не срубает ни одного дерева. Таким образом, Федор отдыхает в $M$-й, 2$M$-й, 3$M$-й день, и т.д.

Лесорубы работают параллельно и, таким образом, в дни, когда никто из них не отдыхает, они срубают $A$ + $B$ деревьев, в дни, когда отдыхает только Федор — $A$ деревьев, а в дни, когда отдыхает только Дмитрий — $B$ деревьев. В дни, когда оба лесоруба отдыхают, ни одно дерево не срубается.

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

Требуется написать программу, которая по заданным целым числам $A$, $K$, $B$, $M$ и $X$ определяет, за сколько дней все деревья в лесу будут вырублены.

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

Входной файл содержит пять целых чисел, разделенных пробелами: $A$, $K$, $B$, $M$ и $X$ (1 ≤ $A$, $B$ ≤ $10^9$ , 2 ≤ $K$, $M$ ≤ 10¹⁸, 1 ≤ $X$ ≤ 10¹⁸).

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

Выходной файл должен содержать одно целое число — искомое количество дней.

Пояснения к примеру

В приведенном примере лесорубы вырубают 25 деревьев за 7 дней следующим образом:
* 1-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 5 деревьев;
* 2-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 10 деревьев;
* 3-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 12 деревьев;
* 4-й день: Дмитрий отдыхает, Федор срубает 3 дерева, итого 15 деревьев;
* 5-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 20 деревьев;
* 6-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 22 дерева;
* 7-й день: Дмитрий срубает 2 дерева, Федор срубает оставшееся 1 дерево, итого все 25 деревьев срублены.
Внимание! Тест из примера не подходит под ограничения для подзадач 2 и 3, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера. Решение должно выводить правильный ответ на тест даже, если оно рассчитано на решение только каких-либо из подзадач 2 и 3

Система оценки и описание подзадач

Подзадача 1 (32 балла)
1 ≤ $X$ ≤ 1000, 1 ≤ $A$, $B$ ≤ 1000, 2 ≤ $K$, $M$ ≤ 1000
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 2 (10 баллов)
1 ≤ $X$ ≤ 10¹⁸
$X$ < $K$
$X$ < $M$
При решении этой подзадачи можно считать, что лесорубы не отдыхают.
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 3 (10 баллов)
1 ≤ $X$ ≤ 10¹⁸
Дополнительно к приведенным ограничениям выполняется условие $K$ = $M$.
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 4 (48 баллов)
1 ≤ $X$ ≤ 10¹⁸, 1 ≤ $A$, $B$ ≤ $10^9$, 2 ≤ $K$, $M$ ≤ 10¹⁸
В этой подзадаче 16 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Примеры

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

2 4 3 3 25

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

#112772

Ремонт асфальта

Темы: [Задачи на моделирование]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2014-2015, 1 тур, Задача D ]

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

Вы, как коренной житель города Д. и программист по призванию, решили использовать свои профессиональные навыки на благо общества и облегчить жизнь своим соседям по улице $М$. А именно, вы решили создать сайт, содержащий актуальную информацию о непроходимости улицы. Прежде всего, вы заметили, что улица разбита на 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.

Система оценки

Тесты к этой задаче состоят из трёх групп. Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.

Примеры

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

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

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

7
1 1 2 3 2 2 1
3
2 2
4 2
6 9

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

5
3
4

#112773

Вид из окна

Темы: [Сортировка записей] [Элементарная геометрия]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2014-2015, 2 тур, Вид из окна ] [ Личные олимпиады, Открытая олимпиада школьников, 2014-2015, 2 тур, Задача A ]

Даны несколько ломанных (кусочно-линейных функций, определённых на отрезке $[a, b]$). Требуется определить, верно ли, что для каждой пары таких функций одна из функций больше либо равна, чем другая во всех точках отрезка $[a, b]$

На протяжении многих лет Вася работает программистом в одной очень большой и очень известной компании. Эта компания обеспечивает своих сотрудников всем необходимым для приятной и плодотворной работы: бесплатными обедами, транспортом от дома до места работы и многим, многим другим. И вот в один прекрасный солнечный день Вася понял, что ему очень наскучил вид из окна его офиса, и ему нужно, чтобы за окном было что-то новое и прекрасное. А что может быть лучше чудесного горного пейзажа? Придя к этой мысли, Вася попросил своего менеджера подобрать себе новый офис с красивым видом на горы.

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

Более формально, вид из окна офиса представляет собой набор горных цепей, пронумерованных от $1$ до $N$, где горная цепь с номером i представляет собой ломаную на плоскости из $l_i$ звеньев с вершинами в точках ($x_i$,$j$ , $y_i$,$j$ ), причем для любых $i$, $j$ выполнено $x_{i,j} < x_{i,j+1}$.

Кроме этого, окно в офисе имеет фиксированную ширину, поэтому все горные цепи начинаются и заканчиваются на одной вертикали, то есть существуют такие числа $A$ и $B$, что для любого номера $i$ горной цепи выполнено $x_{i,0} = A, x_{i,l_i} = B$.

Отметим, что из определения горной цепи следует, что для любого значения абсциссы $A \le x \le B$ на ломаной с номером $i$ существует единственная точка ($x$, $y_i$($x$)) с этим значением абсциссы, принадлежащая этой ломаной. Будем говорить, что горная цепь $i$ находится строго выше горной цепи $j$ в точке $x$, если выполнено строгое неравенство $y_i(x) > y_j (x)$.

Естественно считать, что цепь под номером $i$ пересекается с цепью под номером $j$, если существуют такие два значения абсциссы $x_1$, $x_2$, что цепь $i$ находится строго выше цепи $j$ в точке $x_1$, но при этом цепь $j$ находится строго выше цепи $i$ в точке $x_2$, то есть выполнены неравенства $y_i$($x_1$) > $y_j$ ($x_1$) и $y_j$ ($x_2$) > $y_i$($x_2$). Обратите внимание на поясняющие рисунки, расположенные в примечании к задаче.

Вам необходимо определить, подойдет ли подобранный офис Васе, и, если нет, то найти любую пару пересекающихся горных цепей.

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

В первой строке входных данных через пробел идут два целых числа: $A$ и $B$ ($−10^9 \le A < B \le 10^9$ ).

Во второй строке входных данных находится единственное число $N$ — количество горных цепей, видимых из окна подобранного менеджером Васи офиса ($1 \le N \le 100 000$).

Далее следуют описания N горных цепей. В первой строке i-го описания содержится число $l_i \ge 1$ — количество звеньев ломаной, из которых состоит соответствующая горная цепь. В следующих $l_i$ + 1 строках описания содержатся два целых числа — координаты ($x_{i, j} , y_{i,j}$ ) вершин ломаной ($0 \le j \le l_i$). Суммарное число звеньев всех ломаных не превосходит 200 000.

Гарантируется, что для каждой горной цепи вершины соответствующей ей ломаной идут во входных данных в порядке возрастания абсциссы, причем для любого $i$ выполнено $x_{i,0} = A, x_{i,l_i} = B$.

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

Если же офис подходит Васе, то есть никакие две горные цепи из входных данных не пересекаются, в единственной строке выходных данных выведите слово «Yes» (без кавычек).

Иначе выведите в первой строке слово «No» (без кавычек), а на следующей строке выведите два числа — номера двух пересекающихся горных цепей. Горные цепи нумеруются согласно их появлению во входных данных, начиная с 1.

Замечание

Напоминаем, что абсциссой точки называется её $x$-координата, а ординатой — её $y$-координата.

В первом примере хотя ломаные и касаются друг друга в точке (−3, 2), но, согласно данному выше определению, они не пересекаются.

Во втором примере в точке $x_1$ = 1 одна ломаная выше другой, а в точке $x_2$ = 3 — наоборот, то есть горные цепи пересекаются.

Система оценки

Тесты к этой задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.

Примеры

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

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

Yes

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

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

No
1 2

Страница: << 94 95 96 97 98 99 100 >> Отображать по:

Выбрано

Отменить

Добавить в контест