Задача A. Круглый Граф
 Скачать 236.78 Kb.
|
|
Высшая проба 2021 Очный тур, Задача A. Круглый Граф Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт У графа Михаила есть n усадеб расположенных по кругу. Он хочет построить несколько подзем- ных переходов между усадьбами, чтобы перемещаться между ними быстрее. Вы можете выбрать какое-то число k, такое, что для каждой усадьбы она будет соединена с соседними k усадьбами слева и k усадьбами справа. Какое же минимальное k вы должны выбрать, чтобы кратчайшее расстояние между любыми двумя усадьбами было не больше d? Расстояние между двумя усадьбами измерятеся в количестве переходов, которые нужно сделать, чтобы добраться из одной усадьбы в другую. Формат входных данных Первая строка содержит одно целое число t (1 6 t 6 10) — число наборов входных данных. Для каждого набора входных данных на новой строке вводится два целых числа n и d (3 6 n 6 10 12 , 1 6 d 6 10 12 ). Формат выходных данных Для каждого набора входных данных выведите одно число - минимальное k удовлетворяющее условию. Числа разделяйте переводами строк или пробелами. Пример стандартный ввод стандартный вывод 2 6 2 3 1 2 1 Замечание В первом наборе входных данных если мы соединим каждую усадьбу с каждым из соседей (т.е. если k = 1), то для попадания в противоположную усадьбу нужно будет совершить 3 перехода (см. рисунок) Если соединить каждую усадьбу с двумя соседями (k = 2) будет ситуация как на ри- сунке и потребуется не больше двух переходов для попадания из любой усадьбы в любую. Страница 1 из 9 Высшая проба 2021 Очный тур, Во втором наборе данных мы просто соединяем все усадьбы (k = 1). Система оценки: Решения, корректно работающие при n, d 6 10 4 получат не менее 25% баллов. Решения, корректно работающие при n, d 6 10 9 получат не менее 70% баллов. Страница 2 из 9 Высшая проба 2021 Очный тур, Задача B. Игра в спички Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Даша и Света играют со спичками, составляя из них разные фигурки. Всего у девочек есть ровно k спичек, и сегодня их задача - собирать прямоугольные сетки. Фигура называется прямоугольной сеткой размера n × m, если спички представляют собой прямоугольник размера n × m расчерченный на единичные квадраты, где каждый отрезок разъединяющий квадратики изображается спичкой (для лучшего понимания рассмотрите примеры). А вот формы у прямоугольников бывают разные. Соответственно задача Даши — собрать прямоугольник минимальной площади из ровно k спичек, а Светы - собрать прямоугольник максимальной площади из ровно k спичек. Помогите девочкам найти размеры искомых прямоугольников. Формат входных данных В первой строке вводится целое число t (1 6 t 6 10) — число наборов входных данных. Далее каждый набор описывается одним числом k (1 6 k 6 10 9 ) — числом спичек, которые есть у девочек. Формат выходных данных Для каждого набора входных данных выведите минимальную и максимальную возможную пло- щадь занимаемую прямоугольной сеткой из ровно k спичек. Если же прямоугольник собрать невоз- можно, вместо обоих чисел необходимо вывести одно число «-1». Пример стандартный ввод стандартный вывод 4 4 7 22 3 1 1 2 2 7 8 -1 Замечание В первом наборе данных единственный возможный вариант, это квадрат (прямоугольник 1 × 1) составленный из спичек. Во втором наборе данных возможны варианты прямоугольника 1 × 2 и 2 × 1, оба имеют площадь 2. Страница 3 из 9 Высшая проба 2021 Очный тур, В третьем наборе данных возможны варианты 1 × 7, 7 × 1, 2 × 4 и 4 × 2, первые два имеют площадь 7, следующие два имеют площадь 8. В четвертом наборе данных из 3 спичек невозможно собрать никакой прямоугольник. Система оценки: Решения работающие корректно при k 6 1000 получат не менее 30% баллов. Решения работающие корректно при k 6 10 6 получат не менее 60% баллов. Страница 4 из 9 Высшая проба 2021 Очный тур, Задача C. Битовая сортировка Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Девочке Софии очень нравится бинарная запись числа. Однажды вечером она выписывала слу- чайные числа. По счастливой случайности все эти числа были k-битными, то есть для любого числа a i , которое София написала, выполняется 0 6 a i < 2 k . После этого ее заинтересовал вопрос: если она может поменять значение одного бита в одном из чисел на противоположное, то за какое мини- мальное количество подобных действий она сможет отсортировать свой список по неубыванию? Формат входных данных В первой строке вводится число t (1 6 t 6 100) — количество наборов входных данных. Для каждого набора входных данных вводятся числа n и k (1 6 n 6 100, 1 6 k 6 30). В следующих n строках вводятся k-битные целые числа a i , которые написала София (0 6 a i < 2 k ). Числа записаны в двоичной системе счисления (от старших разрядов к младшим) с ровно k битами. Гарантируется, что сумма n по всем наборам входных данных не превосходит 100. Формат выходных данных Для каждого набора входных данных выведите одно число - минимальное количество действий, необходимых для сортировки массива. Пример стандартный ввод стандартный вывод 4 3 3 000 101 010 3 3 000 111 010 3 3 100 111 010 1 1 0 1 2 2 0 Замечание В первом наборе данных достаточно изменить первый бит во втором числе. Тогда получится последовательность 000,001,010, что в десятичной системе будет 0,1,2. Во втором наборе данных можно изменить первые два бита второго числа. Тогда получится последовательность 000,001,010, что в десятичной системе будет 0,1,2. Во третьем наборе данных можно изменить первый и последний бит последнего числа. Тогда получится последовательность 100,111,111, что в десятичной системе будет 4,7,7. В четвертом примере ничего менять не надо, так как последовательность уже неубывающая. Система оценки: Решения, работающие корректно при n 6 2 получат не менее 10% баллов. Решения, работающие корректно при n 6 10 получат не менее 40% баллов. Решения, работающие корректно при k 6 10 получат не менее 40% баллов. Страница 5 из 9 Высшая проба 2021 Очный тур, Задача D. Run, Pancake, Run Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт Тимур решил заняться пробежками по общежитию. Он мотивирует себя блинами. Общежитие состоит из n комнат, некоторые пары из которых соединены переходами длиной 10 метров. Общежитие является деревом, то есть для каждой пары комнат существует ровно один путь их соединяющий. Каждая комната содержит тарелку, в которой находится ровно k блинов. Каждый переход со- держит тарелку, в которой находится ровно 2 блина. Пробежка Тимура выглядит следующим образом: 1. Тимур стартует в любой из комнат и ест в ней 1 блин. Переходит к шагу 2. 2. Тимур, находясь в комнате v, выбирает некоторую комнату u, такую, что: · Переход между v и u существует и содержит хотя бы 1 блин. · Комната u содержит хотя бы 1 блин. Если такой комнаты не существует, Тимур расстраивается и немедленно прекращает пробежку. Иначе он переходит к шагу 3. 3. Тимур перебегает из v в u, съедая по одному блину в переходе между ними и в комнате u, после чего возвращается к шагу 2. Тимуру стало интересно, какое максимальное количество метров он сможет пробежать, если выберет стратегию оптимально. Помогите ему определить это. Формат входных данных Первая строка теста содержит одно целое число t (t 6 100) — количество наборов тестовых данных. Затем следуют t наборов тестовых данных, разделенные пустой строкой. Первая строка набора тестовых данных содержит два целых числа n, k (1 6 n 6 10 5 , 1 6 k 6 10 9 ). Следующая n − 1 строка набора тестовых данных содержит два целых числа v, u (1 6 v, u 6 n, u 6= v) — описание переходов. Гарантируется, что переходы задают дерево. Гарантируется, что сумма n в тестовых наборах не превосходит 10 5 Формат выходных данных Для каждого набора тестовых данных выведите в отдельной строке одно целое число — ответ на него. Система оценки Группа Баллы Доп. ограничения Комментарий sum n k 0 0 – – Тесты из условия 1 2 n 6 1 000 k = 1 2 2 – k = 1 3 3 n 6 300 k = 2 4 4 n 6 20 – 5 4 n 6 1 000 – 6 5 – – Тесты к этой задаче состоят из 6 групп. Каждый тест в группе оценивается в 1 балл. Страница 6 из 9 Высшая проба 2021 Очный тур, Примеры стандартный ввод стандартный вывод 3 7 1 1 2 1 3 2 4 2 5 3 6 3 7 4 2 1 2 1 3 1 4 2 10 1 2 40 40 20 1 12 2 7 8 4 5 7 11 8 10 6 7 4 3 9 7 3 2 4 6 1 2 12 11 160 Страница 7 из 9 Высшая проба 2021 Очный тур, Задача E. Метро Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 6 секунд Ограничение по памяти: 768 мегабайт В столице Берляндии построили первую линию метро. Линия содержит n + 1 станцию и n пере- гонов между ними, i-й перегон соединяет станции с номерами i и i + 1 и стоимость проезда по нему равна c i Перед полным открытием метро правительство Берляднии планирует сделать m тестовых за- пусков метро. В i-м запуске будут открыты станции, номера которых не меньше l i и не больше r i , а также все перегоны между этими станциями. В каждом тестовом запуске метро для каждой пары станций с номерами a и b, таких что a < b, будет пущен поезд из станции a в станцию b, с остановка- ми на всех промежуточных станциях. Например если всего в метро 5 станций и во время тестового запуска будет открыты станции между 2 и 4, то будет пущен поезд со станции 2 на станцию 3, со станции 3 на станцию 4 и со станции 2 на станцию 4 с промежуточной остановкой на станции 3. Чтобы показать доступность метро, правительство Берляндии для каждого тестового запуска выбирает число k i и считает k i -й минимальный по стоимости проезда перегон среди открытых пе- регонов в i-й день, при этом каждый перегон учитывается столько раз, сколько поездов по нему проезжает. Другими словами правительство Берляднии хочет выписать стоимость проезда по каж- дому перегону столько раз, сколько поездов по нему проехало, после чего отсортировать полученный массив по возрастанию и найти в нём k i -е число. Помогите правительству Берляндии найти такой перегон для каждого из тестовых запусков. Формат входных данных В первой строке вводятся два целых числа n и m (1 6 n, m 6 300 000) — число перегонов и число тестовых запусков метро. В следующей строке вводятся n чисел c 1 , c 2 , c 3 , . . . , c n (1 6 c i 6 500 000) — стоимости проезда по перегонам метро. Следующие m строк описывают тестовые запуски. В i-й строке вводятся три целых числа l i , r i и k i (1 6 l i < r i 6 n + 1, 1 6 k i 6 1 6 (r i − l i )(r i − l i + 1)(r i − l i + 2)) — первая открытая станция, последняя открытая станция и какой по стоимости перегон надо найти. Формат выходных данных Для каждого тестового запуска в отдельной строке выведите стоимость k i -го минимального по стоимости перегона среди всех открытых перегонов в i-й день, при этом учитывая каждый перегон столько раз, сколько поездов по нему проезжают в i-й тестовый запуск. Пример стандартный ввод стандартный вывод 5 6 1 2 3 2 3 1 3 2 1 4 7 3 6 4 1 6 35 2 5 7 2 6 10 1 2 2 3 3 2 Замечание В задаче 21 тестов, каждый тест кроме первого независимо оценивается в 1 балл. Тесты можно разделить на 10 групп: Страница 8 из 9 Высшая проба 2021 Очный тур, Дополнительные ограничения Группа Макс. балл n m c i k i Комментарий 0 0 – – – – Тесты из условия. 1 1 n 6 10 m 6 100 c i 6 10 – 2 2 n 6 100 m 6 100 c i 6 100 – 3 2 n 6 100 – c i 6 100 – 4 2 n 6 500 m 6 500 c i 6 500 – 5 2 n 6 10 000 m 6 10 000 c i 6 10 000 – 6 2 n 6 100 000 m 6 100 000 c i 6 30 – 7 3 n 6 100 000 m 6 100 000 – – 8 2 – – c i 6 2 – 9 2 – – c i 6 500 k i 6 500 10 2 – – – – Страница 9 из 9 |