Задача A. Круглый Граф
 Скачать 227.38 Kb.
|
|
Высшая проба 2021 Очный тур, 9-10 класс Задача 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 из 7 Высшая проба 2021 Очный тур, 9-10 класс Во втором наборе данных мы просто соединяем все усадьбы (k = 1). Система оценки: Решения, корректно работающие при n, d 6 10 4 получат не менее 25% баллов. Решения, корректно работающие при n, d 6 10 9 получат не менее 70% баллов. Страница 2 из 7 Высшая проба 2021 Очный тур, 9-10 класс Задача 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 из 7 Высшая проба 2021 Очный тур, 9-10 класс В третьем наборе данных возможны варианты 1 × 7, 7 × 1, 2 × 4 и 4 × 2, первые два имеют площадь 7, следующие два имеют площадь 8. В четвертом наборе данных из 3 спичек невозможно собрать никакой прямоугольник. Система оценки: Решения работающие корректно при k 6 1000 получат не менее 30% баллов. Решения работающие корректно при k 6 10 6 получат не менее 60% баллов. Страница 4 из 7 Высшая проба 2021 Очный тур, 9-10 класс Задача 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 из 7 Высшая проба 2021 Очный тур, 9-10 класс Задача 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 из 7 Высшая проба 2021 Очный тур, 9-10 класс Примеры стандартный ввод стандартный вывод 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 из 7 |