Страница: << 5 6 7 8 9 10 11 >> Отображать по:

#3400

Распил бревен

Темы: [Многоугольники. Выпуклые оболочки]

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

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

Для каждой заготовки измеряется несколько сечений. Каждое из них задано в виде ломаной, представленной координатами ее вершин (\(x_0, y_0\)), (\(x_1, y_1\)), ..., (\(x_N, y_N\)) в порядке их следования. Координаты вершин ломанной удовлетворяют следующим условиям:

\(x_0 < x_1 < x_2 < \dots < x_N\);

\(x_i = 0\) для некоторого \(0 < i < N\);

\(y_0 = y_N = 0\);

для всех \(i\) от 1 до (\(N – 1\)) выполнено условие \(y_i > 0\).

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

основание треугольника лежит на оси абсцисс;

основание симметрично относительно начала координат;

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

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

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

Первая строка входного файла содержит целое число \(K\) – количество измеренных сечений.

Далее следуют описания каждого из \(K\) сечений. В первой строке описания сечения содержится число \(N_K\) – количество звеньев ломаной. За ней следуют (\(N_K + 1\)) строк, каждая из которых содержит пару целых чисел \(x_i\) и \(y_i\) – координаты вершин ломаной сечения в порядке их следования.

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

Выходной файл должен содержать одно вещественное число – наибольшую возможную площадь треугольника. Эта площадь должна иметь абсолютную или относительную погрешность не более \(10^{–6}\), что означает следующее. Пусть выведенное число равно \(x\), а в правильном ответе оно равно \(y\). Ответ будет считаться правильным, если значение выражения \(|x – y| / max(1, |y|)\) не превышает \(10^{–6}\).

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

Данная задача содержит пять подзадач.

Подзадача 1 (20 баллов)

\(K = 1\), \(N_1 \leq 15\), координаты вершин по модулю не превышают 20.

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

Подзадача 2 (10 баллов)

\(1 \leq K \leq 20\), сумма \(N_i \leq 2000\), координаты вершин по модулю не превышают \(10^4\). Гарантируется, что полученный в качестве ответа треугольник является прямоугольным.

Подзадача 3 (20 баллов)

\(1 \leq K \leq 20\), сумма \(N_i \leq 2000\), координаты вершин по модулю не превышают \(10^4\).

Подзадача 4 (10 баллов)

\(1 \leq K \leq 1000\), сумма \(N_i \leq 10^5\), координаты вершин по модулю не превышают \(10^9\). Гарантируется, что полученный в качестве ответа треугольник является прямоугольным.

Подзадача 5 (40 баллов)

\(1 \leq K \leq 1000\), сумма \(N_i \leq 10^5\), координаты вершин по модулю не превышают \(10^9\).

Каждый тест для данной подзадачи оценивается отдельно.

Примеры

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

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

25.0

#111222

Вирусы и антивирусы

Темы: [Обход в глубину]

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

Антивирусная IT-компания имеет официальную иерархическую структуру управления. В ней есть босс – единственный сотрудник, над которым нет начальника. Каждый из остальных сотрудников подчинён ровно одному сотруднику – своему начальнику. Начальник может иметь нескольких подчинённых и отдавать или передавать приказы любому из них. Приказы могут передаваться от одного сотрудника другому только по цепочке, каждый раз от начальника к его подчинённому. Сотрудник А главнее сотрудника Б в этой иерархии, если А может отдать или передать приказ сотруднику Б непосредственно, или через цепочку подчинённых. Босс главнее любого сотрудника. Оказалось, что все сотрудники объединены ещё в одну организованную подобным образом тайную иерархическую структуру, производящую компьютерные вирусы. В тайной структуре может быть другой босс, а у сотрудников – другие начальники. Будем называть пару сотрудников А и Б устойчивой, если А главнее Б и в основной, и в тайной иерархических структурах. Требуется написать программу, определяющую количество устойчивых пар в компании.

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

В первой строке задано число N – количество сотрудников компании (1 ≤ N ≤ 100 000). Во второй строке – N целых чисел a_i, где a_i = 0, если в официальной иерархии сотрудник с номером i является боссом, в противном случае a_i равно номеру непосредственного начальника сотрудника номер i. В третьей строке – N целых чисел b_i, где b_i = 0, если в тайной иерархии сотрудник с номером i является боссом, в противном случае b_i равно номеру непосредственного начальника сотрудника номер i. Нумерация сотрудников ведется с единицы в том порядке, в каком они упомянуты во входном файле.

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

Выходной файл должен содержать единственное число – количество устойчивых пар.

Примечание

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

(оценивается в 25 баллов) Количество сотрудников N не превосходит 100.
(оценивается в 25 баллов) Количество сотрудников N не превосходит 2000.
(оценивается в 50 баллов) Количество сотрудников N не превосходит 10⁵.

Примеры

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

3
0 3 1
0 1 1

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

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

5
2 0 1 3 4
3 1 0 2 4

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

#111227

Ордынское войско

Темы: [Перебор] [Динамическое программирование: последовательности]

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

Готовясь к бою, хан Гирей пронумеровал всех воинов своего войска натуральными числами от 1 до N. Поскольку воины умеют сражаться, но не умеют считать, при любом построении в шеренгу они выстраиваются в произвольном порядке. Одного или несколько воинов, стоящих в шеренге, будем называть отрядом. Отряд назовем правильным, если номера этих воинов в том порядке, в котором они стоят в шеренге, образуют упорядоченную по возрастанию последовательность чисел. Среди всех правильных отрядов хан Гирей выбирает ударный отряд – самый большой по количеству воинов. Так, в шеренге 1 3 2 4 из четырех воинов ударными являются отряды 1 3 4 и 1 2 4, а отряд 1 4 – один из правильных, но не ударный. Некоторые воины являются личными телохранителями хана Гирея. Требуется составить программу, определяющую количество таких шеренг, в которых телохранители хана образуют ударный отряд.

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

В первой строке входного файла задано натуральное число N – общее количество воинов (1 ≤ N ≤ 15). Во второй строке задано натуральное число K – количество телохранителей хана (1 ≤ K ≤ N). В третьей строке через пробел указаны K различных натуральных чисел, не превосходящих N, – номера телохранителей хана в порядке возрастания.

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

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

Примечание

В первом примере войско состоит из пяти воинов. Ударный отряд должен состоять из трех воинов с номерами 1, 3 и 4. Этому условию удовлетворяют следующие 11 шеренг: (1, 3, 2, 5, 4), (1, 3, 5, 2, 4), (1, 3, 5, 4, 2), (1, 5, 3, 2, 4), (1, 5, 3, 4, 2), (2, 1, 3, 5, 4), (2, 1, 5, 3, 4), (2, 5, 1, 3, 4), (5, 1, 3, 2, 4), (5, 1, 3, 4, 2), (5, 2, 1, 3, 4).

Данная задача содержит семь подзадач. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы успешно пройдены.

(оценивается в 40 баллов) 1 ≤ N ≤ 8.
(оценивается в 10 баллов) 9 ≤ N ≤ 10.
(оценивается в 10 баллов) N = 11.
(оценивается в 10 баллов) N = 12.
(оценивается в 10 баллов) N = 13.
(оценивается в 10 баллов) N = 14.
(оценивается в 10 баллов) N = 15.

Примеры

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

5
3
1 3 4

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

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

3
3
1 2 3

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

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

1
1
1

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

#111634

Робот

Темы: [Строки] ["Два указателя"]

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

Студенты одного из вузов спроектировали робота для частичной автоматизации процесса сборки авиационного двигателя.

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

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

Память робота состоит из K ячеек, каждая из которых содержит одну операцию. Операции выполняются последовательно, начиная с первой, в том порядке, в котором они расположены в памяти. Выполнив последнюю из них, робот продолжает работу с первой. Робота можно остановить после любой операции. Использование робота экономически целесообразно, если он выполнит хотя бы K + 1 операцию.

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

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

В первой строке входного файла записано число K > 0 "— количество операций, которые можно записать в память робота.

Вторая строка состоит из N > K строчных латинских букв, обозначающих операции "— процесс сборки двигателя. Операции одного и того же типа обозначаются одной и той же буквой.

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

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

Примечание

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

Тесты из условия. Подзадача оценивается в 0 баллов.

N ≤ 100. Подзадача оценивается в 30 баллов.

N ≤ 2000. Подзадача оценивается в 30 баллов.

N ≤ 200 000. Подзадача оценивается в 40 баллов.

Примеры

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

2
zabacabab

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

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

2
abc

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

#111636

Древние династии

Темы: [Динамическое программирование] [Дерево отрезков, RSQ, RMQ] [Очередь]

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

История Татаро-монгольского ханства богата на правителей. Каждый из N правителей принадлежал к одной из двух династий, причём власть часто переходила от одной династии к другой. Каждое восхождение правителя на престол отмечалось праздником, проводимым 26 марта. В летописях зафиксированы годы проведения этих праздников, причем известно, что правители первой династии устраивали для народа праздник кумыса, а второй — праздник мёда.

На конференции по истории Татаро-монгольского ханства каждый из S учёных предложил свою версию толкования летописи. А именно, i-й историк утверждал, что от каждого праздника кумыса до следующего праздника кумыса проходило не менее KL_i лет, но не более KR_i лет, в то время как от каждого праздника мёда до следующего праздника мёда проходило не менее ML_i лет, но не более MR_i лет.

Каждой предложенной версии может соответствовать несколько распределений правителей по династиям. Ученые договорились считать показателем сомнительности распределения число переходов власти к представителю той же самой династии.

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

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

В первой строке входного файла записано число N (2 ≤ N ≤ 200 000) — количество праздников в летописи. Следующая строка содержит целые числа X₁, X₂, ..., X_N (1 ≤ X₁ ≤ X₂ ≤ ... ≤ X_N ≤ 10⁹) — годы проведения праздников.

В третьей строке записано число учёных S (1 ≤ S ≤ 50). В каждой из последующих S строк записаны четыре натуральных числа KL_i, KR_i, ML_i, MR_i (1 ≤ KL_i ≤ KR_i ≤ 10⁹), (1 ≤ ML_i ≤ MR_i ≤ 10⁹).

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

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

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

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

Примечание

Данная задача содержит шесть подзадач. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.

Тесты из условия. Подзадача оценивается в 0 баллов.
2 ≤ N ≤ 15, 1 ≤ S ≤ 10. Подзадача оценивается в 20 баллов.
2 ≤ N ≤ 2000, 1 ≤ S ≤ 50, N × S ≤ 2000. Подзадача оценивается в 20 баллов.
2 ≤ N ≤ 10 000, 1 ≤ S ≤ 50, N × S ≤ 10 000. Подзадача оценивается в 20 баллов.
2 ≤ N ≤ 200 000, 1 ≤ S ≤ 50, N × S ≤ 200 000. Подзадача оценивается в 20 баллов.
2 ≤ N ≤ 200 000, 1 ≤ S ≤ 50. Подзадача оценивается в 20 баллов.

Примеры

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

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

1 1
211

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

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

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

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

2 0
21212

Страница: << 5 6 7 8 9 10 11 >> Отображать по:

Выбрано

Отменить

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