Автор: | Центральная предметно-методическая комиссия по информатике | Ограничение времени: | 2 сек | |
Входной файл: | birch.in | Ограничение памяти: | 512 Мб | |
Выходной файл: | birch.out | |||
Максимальный балл: | 100 |
На краю деревни растет старая березовая аллея. Аллея имеет форму прямой полосы шириной W метров. Вдоль левой стороны аллеи растет N берез, а вдоль правой — M берез, при этом i-я береза с левой стороны аллеи находится на расстоянии ai метров от начала аллеи, а j-я береза с правой стороны — на расстоянии bj метров от начала аллеи.
В первом примере можно, например, оградить березы способом, указанным на рисунке.
Во втором примере длины ленты недостаточно, чтобы оградить хотя бы по одной березе с каждой стороны.
Правильные решения для тестов, в которых 1 ≤ (N + M) ≤ 50, будут оцениваться из 30 баллов.
Правильные решения для тестов, в которых 1 ≤ (N + M) ≤ 500, будут оцениваться из 60 баллов.
Первая строка входного файла содержит два разделенных пробелом целых числа: длину ленты L и ширину аллеи W.
Вторая и третья строки описывают березы вдоль левой стороны аллеи. Вторая строка содержит число N — количество берез, а третья строка содержит N различных целых чисел a1, a2, …, aN, заданных по возрастанию. Четвертая и пятая строки описывают березы вдоль правой стороны аллеи. Четвертая строка содержит число M — количество берез, а пятая строка содержит M различных целых чисел b1, b2, …, bM, заданных по возрастанию.Выходной файл должен содержать одно целое число: максимальное количество берез, которое можно оградить заданной лентой. Гарантируется, что если максимальное число берез, которое можно оградить лентой длины L, равно X, то нет способа оградить (X + 1) березу лентой длины (L + 10−5).
1 ≤ L ≤ 2×105; 1 ≤ W ≤ 104; 1 ≤ N, M ≤ 2000; 0 ≤ ai, bi ≤ 105;
№ | Входной файл (birch.in ) |
Выходной файл (birch.out ) |
---|---|---|
1 |
|
|
2 |
|
|
Автор: | Центральная предметно-методическая комиссия по информатике | Ограничение времени: | 3 сек | |
Входной файл: | divisors.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | divisors.out | |||
Максимальный балл: | 100 |
Натуральное число a называется делителем натурального числа b, если b = ac для некоторого натурального числа c. Например, делителями числа 6 являются числа 1, 2, 3 и 6. Два числа называются взаимно простыми, если у них нет общих делителей кроме 1. Например, 16 и 27 взаимно просты, а 18 и 24 — нет.
Будем называть нормальным набор из k чисел (a1, a2, …, ak), если выполнены следующие условия:
Например, набор (2, 9, 10) является нормальным набором из 3 делителей числа 360.
Требуется написать программу, которая по заданным значениям n и k определяет количество нормальных наборов из k делителей числа n.
Правильные решения для тестов, в которых n ≤ 1000 и k = 2, оцениваются из 30 баллов.
Правильные решения для тестов, в которых k = 2, оцениваются из 60 баллов (в эти баллы включаются также 30 баллов для случая n ≤ 1000 и k = 2).
Первая строка входного файла содержит два целых числа: n и k.
В выходном файле должно содержаться одно число — количество нормальных наборов из k делителей числа n.
2 ≤ n ≤ 108
2 ≤ k ≤ 10
№ | Входной файл (divisors.in ) |
Выходной файл (divisors.out ) |
---|---|---|
1 |
|
|
2 |
|
|
Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 1 сек | |
Входной файл: | power.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | power.out | |||
Максимальный балл: | 100 |
В физико-биологической лаборатории исследуют воздействие излучения на растения при облучении через силовые поля.
Экспериментальная установка содержит квадратную платформу размером 109 × 109, заполненную плодородной почвой. Над платформой установлен источник излучения. Между источником излучения и платформой можно включать n силовых полей.
Генератор силовых полей установлен над точкой (0, 0). При этом i-е силовое поле представляет собой прямоугольник со сторонами, параллельными границам платформы и координатами двух противоположных углов (0, 0) и (xi, yi).
В эксперименте планируется изучать воздействие излучения на растения при облучении через k силовых полей. Из заданных n полей необходимо выбрать k полей для эксперимента. Ученые хотят выбрать силовые поля таким образом, чтобы площадь участка платформы, над которой находятся все k выбранных силовых полей, была максимальна.
Требуется написать программу, которая по заданным целым числам n, k и описанию n силовых полей определяет, какие k силовых полей необходимо выбрать для эксперимента, чтобы площадь участка, покрытого всеми k силовыми полями, была максимальна, и выводит площадь этого участка.
Первая строка входного файла содержит целые числа n и k — общее количество силовых полей и количество силовых полей, которые необходимо выбрать для эксперимента.
Последующие n строк содержат по два целых числа xi, yi — координаты дальнего от начала координат угла прямоугольного участка i-го силового поля.
Требуется вывести одно целое число: максимальную площадь искомого участка.
1 ≤ k ≤ n ≤ 200 000, 1 ≤ xi, yi ≤ 109
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Ограничения | Необходимые подзадачи | |
---|---|---|---|---|
n | k | |||
1 | 18 | 1 ≤ n ≤ 20 | 1 ≤ k ≤ n | |
2 | 25 | 1 ≤ n ≤ 300 | 1 ≤ k ≤ n | 1 |
3 | 20 | 1 ≤ n ≤ 3000 | 1 ≤ k ≤ n | 1, 2 |
4 | 17 | 2 ≤ n ≤ 200 000 | k = 2 | |
5 | 20 | 1 ≤ n ≤ 200 000 | 1 ≤ k ≤ n | 1, 2, 3, 4 |
По запросу сообщается результат окончательной проверки на каждом тесте.
На рис. 1 показаны пять силовых полей, заданных во входном файле. Оптимальный способ выбрать из них три поля для эксперимента показан на рис. 2.
Рис 1. Силовые поля в примере описания входных данных.
Рис 2. Оптимальный выбор трех из пяти силовых полей в данном примере.
№ | Входной файл (power.in ) |
Выходной файл (power.out ) |
---|---|---|
1 |
|
|
Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 1 сек | |
Входной файл: | qual.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | qual.out | |||
Максимальный балл: | 100 |
Взаимодействие сотрудников в некоторой компании организовано в виде иерархической структуры. Всего в компании работают n сотрудников. Каждому сотруднику присвоен уникальный номер от 1 до n, директору присвоен номер 1. У каждого сотрудника, кроме директора, есть ровно один непосредственный начальник. Непосредственный начальник сотрудника i имеет номер pi , причем pi < i.
Сотрудник x является подчиненным уровня 1 сотрудника y, если px = y. Для k > 1 сотрудник x является подчиненным уровня k сотрудника y, если сотрудник px является подчиненным уровня k − 1 сотрудника y.
У директора компании появилась возможность направить некоторых сотрудников на курсы повышения квалификации. Для этого он решил выбрать два числа L и R и направить на курсы всех сотрудников с номерами i, такими что L ≤ i ≤ R.
Перед тем, как выбрать числа L и R, директор получил m пожеланий от сотрудников компании, j-е пожелание задается двумя числами uj и kj и означает, что сотрудник uj просит отправить на курсы одного из своих подчиненных уровня kj. Для экономии средств директор хочет выбрать такие L и R, чтобы количество сотрудников, направленных на повышение квалификации, было минимальным возможным, но при этом все пожелания были выполнены.
Требуется написать программу, которая по заданным в компании отношениям начальник-подчиненный и пожеланиям сотрудников определяет такие числа L и R, что если отправить на курсы повышения квалификации всех сотрудников с номерами от L до R включительно, то все пожелания будут выполнены, а количество сотрудников, направленных на повышение квалификации, будет минимальным возможным. Если оптимальных пар чисел L, R будет несколько, требуется найти ту из них, в которой значение L минимально.
Первая строка входного файла содержит число n — количество сотрудников компании. Вторая строка содержит (n − 1) чисел: p2, p3, …, pn (1 ≤ pi ≤ i) — номера непосредственных начальников сотрудников.
Третья строка содержит число m — количество пожеланий от сотрудников.
Последующие m строк задают пожелания сотрудников и содержат по два целых числа uj, kj (1 ≤ uj < n, 1 ≤ kj < n, гарантируется, что у сотрудника uj есть хотя бы один подчиненный уровня kj).
Необходимо вывести два искомых числа: L и R. Если оптимальных пар (L, R) несколько, требуется вывести ту, в которой значение L минимально.
2 ≤ n, m ≤ 200 000
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Ограничения | Необходимые подзадачи | |
---|---|---|---|---|
n | Дополнительные условия | |||
1 | 19 | 2 ≤ n, m ≤ 50 | ||
2 | 25 | 2 ≤ n, m ≤ 3000 | 1 | |
3 | 21 | 2 ≤ n, m ≤ 200 000 | для всех i выполнено pi = i − 1 | |
4 | 35 | 2 ≤ n, m ≤ 200 000 | 1, 2, 3 |
По запросу сообщаются баллы за каждую подзадачу.
На повышение квалификации будут направлены сотрудники с номерами 3, 4, 5 и 6. Сотрудник с номером 3 является подчиненным уровня 1 сотрудника с номером 1, сотрудник с номером 4 — подчиненным уровня 2 сотрудника с номером 1, а сотрудник с номером 6 — подчиненным уровня 1 сотрудника с номером 3.
№ | Входной файл (qual.in ) |
Выходной файл (qual.out ) |
---|---|---|
1 |
|
|