Областная олимпиада по информатике, 2018 год, 9 класс
(k-я пара) Вам задан массив a, состоящий из n целых чисел a1, a2, ..., an.
Два элемента массива ai, aj с индексами (i,j) 1≤i<j≤n, могут образовать пару и силой этой пары назовем ai+aj. Найдите силу пары, являющейся k-й по счету, если отсортировать все пары по неубыванию силы.
Во второй строке через пробел заданы целые числа a1, a2, ..., an (0≤ai≤106).
Во втором примере можно сделать десять пар с силами {a1 + a2, a1 + a3, a1 + a4, a1 + a5, a2 + a3, a2 + a4, a2 + a5, a3 + a4, a3 + a5, a4 + a5} = {1 + 5, 1 + 3, 1 + 5, 1 + 3, 5 + 3, 5 + 5, 5 + 3, 3 + 5, 3 + 3, 5 + 3} = {6, 4, 6, 4, 8, 10, 8, 8, 6, 8}. Если их отсортировать по неубыванию силы, то получится {4, 4, 6, 6, 6, 8, 8, 8, 8, 10} и седьмой элемент это 8.
Ограничения которые присутствуют в тестах:
Два элемента массива ai, aj с индексами (i,j) 1≤i<j≤n, могут образовать пару и силой этой пары назовем ai+aj. Найдите силу пары, являющейся k-й по счету, если отсортировать все пары по неубыванию силы.
Формат входных данных:
В первой строке заданы два целых числа n и k (1≤k≤n∗(n−1)2).Во второй строке через пробел заданы целые числа a1, a2, ..., an (0≤ai≤106).
Формат выходных данных:
Выведите ответ на задачу.Примеры:
1.Вход:3 3 7 1 4Ответ:
112.Вход:
5 7 1 5 3 5 3Ответ:
83.Вход:
10 32 0 0 0 0 0 0 0 0 0 0Ответ:
04.Вход:
9 15 5 6 3 0 0 4 1 4 1Ответ:
5
Замечание:
В первом примере можно сделать три пары с силами {a1 + a2, a1 + a3, a2 + a3} = {7 + 1, 7 + 4, 1 + 4} = {8, 11, 5}. Если их отсортировать по неубыванию силы, то получится {5, 8, 11} и третий элемент это 11.Во втором примере можно сделать десять пар с силами {a1 + a2, a1 + a3, a1 + a4, a1 + a5, a2 + a3, a2 + a4, a2 + a5, a3 + a4, a3 + a5, a4 + a5} = {1 + 5, 1 + 3, 1 + 5, 1 + 3, 5 + 3, 5 + 5, 5 + 3, 3 + 5, 3 + 3, 5 + 3} = {6, 4, 6, 4, 8, 10, 8, 8, 6, 8}. Если их отсортировать по неубыванию силы, то получится {4, 4, 6, 6, 6, 8, 8, 8, 8, 10} и седьмой элемент это 8.
Система оценки:
Задача содержит 50 тестов, каждая из которых весят 2 балла.Ограничения которые присутствуют в тестах:
- 24 теста: 2≤n≤103
- 26 тестов: 2≤n≤104
комментарий/решение(14)
(Такси) В городе Алматы проживает преуспевающий бизнесмен по имени Елибай. С недавних пор он занимается строительством N объектов . Он каждый день ездит на своем автомобиле с головного офиса в объекты, осматривает объекты и возвращается обратно в офис. Он обязательно должен возвращаться в офис между походами в объекты, так как он должен заполнить некоторые документы. Сегодня у него случилась беда, у машины разрядился аккумулятор. Чтобы не опоздать он обратился к двум сервиса для заказа такси ZhureBER и Zhett. Тарифы у них оказались недешевыми. За d километров придется платить d2 тенге. Однако его друг Айсултан - который владеет сервисом такси предложил ему купить N промо-кодов для поездки на такси со стоимостью X, тогда ему придется платить за каждую поездку X тенге если X≥d, иначе X+(d−X)2 тенге.
Елибай для осмотра объекта под номером i заказывает такси из офиса в объект и обратно (суммарная дистанция из офиса в объект и обратно di). Он не может за одну поездку два раза пользоваться промо-кодом и для осмотра нового объекта каждый раз заказывает новый такси.
Так как Айсултан давний друг Елибая, он предложил ему самому выбрать число X, конечно же X должно быть неотрицательным целым числом.
Во второй строке записаны N целых чисел d1,d2,…dn расстояние от офиса до i-го объекта и обратно.
Если X = 6, мы можем получить минимальную стоимость 70.
Суммарно 6×10+(9−6)2+(7−6)2=60+9+1=70
Если X = 5, общая стоимость была бы 71. Если X = 7, общая стоимость была бы 74.
Ограничения которые присутствуют в тестах:
Елибай для осмотра объекта под номером i заказывает такси из офиса в объект и обратно (суммарная дистанция из офиса в объект и обратно di). Он не может за одну поездку два раза пользоваться промо-кодом и для осмотра нового объекта каждый раз заказывает новый такси.
Так как Айсултан давний друг Елибая, он предложил ему самому выбрать число X, конечно же X должно быть неотрицательным целым числом.
Формат входных данных:
Первая строка входного файла будет содержать одно число N — количество объектов с которыми занимается бизнесмен.Во второй строке записаны N целых чисел d1,d2,…dn расстояние от офиса до i-го объекта и обратно.
Формат выходных данных:
Выведите одно целое число - минимальную суммарную количество денег Елибай должен заплатить если выберет число X оптимально.Примеры:
1.Вход:5 7 7 7 7 7Ответ:
352.Вход:
10 2 1 3 6 7 5 9 2 2 4Ответ:
703.Вход:
2 0 100Ответ:
199
Замечание:
Второй пример:Если X = 6, мы можем получить минимальную стоимость 70.
Суммарно 6×10+(9−6)2+(7−6)2=60+9+1=70
Если X = 5, общая стоимость была бы 71. Если X = 7, общая стоимость была бы 74.
Система оценки:
Задача содержит 50 тестов, каждая из которых весят 2 балла.Ограничения которые присутствуют в тестах:
- 4 теста: 1≤N≤2000, 0≤di≤1000. В добавок, расстояние до всех объектов одинаково. (di=d1 для i>1)
- 11 тестов: 1≤N≤2000, 0≤di≤1000
- 11 тестов: 1≤N≤2000, 0≤di≤106.
- 24 тестов: 1≤N≤200000, 0≤di≤106.
комментарий/решение(5)
(Тима и Рама) На доске в ряд написано N целых чисел. Темірлан и Рамазан играют в следующую игру:
Пока Темірлан отошел, Рамазан хочет стереть ровна K чисел. Он может стереть любые числа. Когда Темірлан вернется, они начнут играть как обычно, но на доске будет написано N−K чисел.
Для каждого из Q чисел K1,K2,...,KQ, Рамазан хочет узнать, какое значение у последнего оставшегося числа, если он заранее сотрет Ki чисел, и оба игрока играют оптимально?
Во второй строке находятся N целых числа A1,A2,...,AN(1≤Ai≤106) --- числа написанные на доске.
В третьей строке находится одно целое число Q.
В четвертой строке находятся Q целых числа K1,K2,...,KQ(0≤Ki≤N−1).
Ограничения которые присутствуют в тестах:
- Они будут ходить по очереди, первым начинает Темірлан.
- На каждом ходу игрок может стереть с доски любое ненулевое количество чисел с начала, или с конца. Но нельзя стереть все числа.
- Игра закончится, когда на доске останется ровно одно число. Темірлан хочет минимизировать последнее число, а Рамазан хочет максимизировать это число.
Пока Темірлан отошел, Рамазан хочет стереть ровна K чисел. Он может стереть любые числа. Когда Темірлан вернется, они начнут играть как обычно, но на доске будет написано N−K чисел.
Для каждого из Q чисел K1,K2,...,KQ, Рамазан хочет узнать, какое значение у последнего оставшегося числа, если он заранее сотрет Ki чисел, и оба игрока играют оптимально?
Формат входных данных:
В первой строке находится одно целое число N.Во второй строке находятся N целых числа A1,A2,...,AN(1≤Ai≤106) --- числа написанные на доске.
В третьей строке находится одно целое число Q.
В четвертой строке находятся Q целых числа K1,K2,...,KQ(0≤Ki≤N−1).
Формат выходных данных:
Выведите через пробел Q чисел, i-е из них, значения последнего оставшегося числа, если Рамазан заранее сотрет Ki чисел.Примеры:
1.Вход:4 1 4 2 3 4 0 1 2 3Ответ:
1 3 3 42.Вход:
3 5 5 5 3 0 1 2Ответ:
5 5 53.Вход:
6 2 7 5 4 8 10 3 3 5 2Ответ:
7 10 7
Замечание:
В первом тесте при K=3, Рамазану выгодно стереть первое,второе и четвертое числа.Система оценки:
Задача содержит 50 тестов, каждая из которых весят 2 балла.Ограничения которые присутствуют в тестах:
- 3 теста: Первые три теста является тестами из примеров
- 5 тестов: 1≤N≤3,Q=1,K1=0
- 10 тестов: 1≤N≤100,Q=1,K1=0
- 12 тестов: 1≤N≤105,1≤Q≤2,0≤Ki≤1
- 10 тестов: 1≤N≤105,1≤Q≤105,0≤Ki≤N−1
- 10 тестов: 1≤N≤106,1≤Q≤106,0≤Ki≤N−1
комментарий/решение(14)
(Склад ручек) Елдан работает охранником на складе с ручками. Все ручки на складе хранятся в запакованных коробках. Елдан заметил, что всего есть n типов коробок, в коробке типа i лежит ai ручек и на складе коробок каждого типа очень много (больше 1012). Скоро должен приехать грузовик, чтобы забрать s ручек в магазин. Елдану не сообщили, сколько ручек требуется в магазине, но он знает, что это значение не больше x. Поэтому он хочет подготовить минимальное количество коробок, чтобы мог отдать любое количество ручек от 1 до x, не открывая коробок. Помогите Елдану посчитать, какое минимальное количество коробок ему нужно подготовить, либо сообщите, что это невозможно.
При s=1 он отдаст одну коробку a2.
При s=2 он отдаст одну коробку a1.
При s=3 он отдаст две коробки a1,a2 (2 + 1 = 3).
Во втором примере Елдан подготовит одну коробку a1.
В третьем примере Елдан может подготовить коробки с типами a1,a1,a2,a2,a3.
При s=1 он отдаст коробку a3.
При s=2 он отдаст коробку a2.
При s=3 он отдаст коробки a2,a3.
При s=4 он отдаст коробки a2,a2.
При s=5 он отдаст коробки a2,a2,a3.
При s=6 он отдаст коробки a1,a3.
При s=7 он отдаст коробки a1,a2.
При s=8 он отдаст коробки a1,a2,a3.
При s=9 он отдаст коробки a1,a2,a2.
При s=10 он отдаст коробки a1,a1.
При s=11 он отдаст коробки a1,a1,a3.
При s=12 он отдаст коробки a1,a1,a2.
При s=13 он отдаст коробки a1,a1,a2,a3.
При s=14 он отдаст коробки a1,a1,a2,a2.
При s=15 он отдаст коробки a1,a1,a2,a2,a3.
Обратите внимание, что в данном тесте есть и другие варианты выбрать коробки, например a1,a1,a3,a3,a4.
В четвертом примере Елдан не может выбрать какие-либо коробки, чтобы отдать две ручки.
Ограничения которые присутствуют в тестах:
Формат входных данных:
В первой строке входных данных задано одно число n. Во второй строке заданы через пробел n различных чисел a1,a2,…,an. В третьей строке задано одно число x. Все числе во входных данных являются целыми положительными.Формат выходных данных:
Выведите ответ на задачу, если ответа не существует выведите −1.Примеры:
1.Вход:2 2 1 3Ответ:
22.Вход:
1 1 1Ответ:
13.Вход:
4 5 2 1 3 15Ответ:
54.Вход:
2 5 3 2Ответ:
-1
Замечание:
В первом примере Елдан может подготовить коробки с типами a1,a2.При s=1 он отдаст одну коробку a2.
При s=2 он отдаст одну коробку a1.
При s=3 он отдаст две коробки a1,a2 (2 + 1 = 3).
Во втором примере Елдан подготовит одну коробку a1.
В третьем примере Елдан может подготовить коробки с типами a1,a1,a2,a2,a3.
При s=1 он отдаст коробку a3.
При s=2 он отдаст коробку a2.
При s=3 он отдаст коробки a2,a3.
При s=4 он отдаст коробки a2,a2.
При s=5 он отдаст коробки a2,a2,a3.
При s=6 он отдаст коробки a1,a3.
При s=7 он отдаст коробки a1,a2.
При s=8 он отдаст коробки a1,a2,a3.
При s=9 он отдаст коробки a1,a2,a2.
При s=10 он отдаст коробки a1,a1.
При s=11 он отдаст коробки a1,a1,a3.
При s=12 он отдаст коробки a1,a1,a2.
При s=13 он отдаст коробки a1,a1,a2,a3.
При s=14 он отдаст коробки a1,a1,a2,a2.
При s=15 он отдаст коробки a1,a1,a2,a2,a3.
Обратите внимание, что в данном тесте есть и другие варианты выбрать коробки, например a1,a1,a3,a3,a4.
В четвертом примере Елдан не может выбрать какие-либо коробки, чтобы отдать две ручки.
Система оценки:
Задача содержит 50 тестов, каждая из которых весят 2 балла.Ограничения которые присутствуют в тестах:
- 4 теста: n=1, ai≤25,x≤25
- 6 тестов: n≤3, ai≤25,x≤25
- 6 тестов: n≤5, ai≤25,x≤25
- 14 тестов: n≤105,ai≤105,x≤105
- 20 тестов: n≤105,ai≤1012,x≤1012
комментарий/решение(1)
(Опять деревья) Дается неориентированное дерево из n вершин, определим расстояние между двумя вершинами как количество ребер в их кратчайшем пути. Диаметром дерева является максимальное расстояние среди всех пар вершин в дереве.
В данной задаче вам нужно минимизировать диаметр дерева применив не более k операций удаления.
Операция удаления представляет собой удаление вершины и всех ребер смежных с ней, при этом не разрешается удалять вершину если после операции граф станет безсвязным.
В следующих n−1 строках следует описание графа.
В каждой строке содержатся числа u и v (1≤u,v≤n) - означает что существует неориентированное ребро между вершиной u и вершиной v.
Ограничения которые присутствуют в тестах:
В данной задаче вам нужно минимизировать диаметр дерева применив не более k операций удаления.
Операция удаления представляет собой удаление вершины и всех ребер смежных с ней, при этом не разрешается удалять вершину если после операции граф станет безсвязным.
Формат входных данных:
В первой строке содержатся числа n и k (0≤k≤n−1) - количество вершин и максимальное количество вершин которое можно удалить.В следующих n−1 строках следует описание графа.
В каждой строке содержатся числа u и v (1≤u,v≤n) - означает что существует неориентированное ребро между вершиной u и вершиной v.
Формат выходных данных:
Выведите ровно одно число - минимальный диаметр который можно получить удалив не более k вершин.Примеры:
1.Вход:5 2 1 4 3 2 1 2 5 2Ответ:
22.Вход:
14 5 13 2 10 4 6 12 8 11 11 13 5 14 10 3 11 5 12 1 9 7 11 10 10 9 6 10Ответ:
3
Система оценки:
Задача содержит 100 тестов, каждая из которых весят 1 балл.Ограничения которые присутствуют в тестах:
- 10 теста: n≤20
- 10 тестов: n≤100
- 5 тестов: k=0
- 24 тестов: n≤2000
- 51 тестов: n≤5000
комментарий/решение
(Башни) У Алана есть n башен, у каждой из которых есть параметр ai - числитель рук и параметр bi - знаменатель рук. В q очень легких делах, которых он задумал, ему нужно определить руки у башен. Для этого, каждой башне он может сказать сделать целое количество рук - [aibi] или дробное количество рук - aibi. Для i-го дела, которые он задумал, Алану необходимо суммарно ровно xi рук. Для каждого из этих дел Алан берет все n башен, то есть суммарная \textit{рукость} всех башен должна равняться xi. Помогите Алану найти количество способов сделать это, для каждого из q легких дел.
Во второй строке дается n целых положительных чисел a1,a2,..,an (1≤ai≤100000)
В третьей строке дается n целых положительных чисел b1,b2,..,bn (1≤bi≤100000)
В следующей дается целое положительное число q (1≤q≤100000) - количество запросов.
В следующих q строках находится по одному целому числу x - запросы из условия (1≤x≤4000000)
Ограничения которые присутствуют в тестах:
Формат входных данных:
В первой строке дается целое положительное число n (1≤n≤40).Во второй строке дается n целых положительных чисел a1,a2,..,an (1≤ai≤100000)
В третьей строке дается n целых положительных чисел b1,b2,..,bn (1≤bi≤100000)
В следующей дается целое положительное число q (1≤q≤100000) - количество запросов.
В следующих q строках находится по одному целому числу x - запросы из условия (1≤x≤4000000)
Формат выходных данных:
Выведите q целых числе по одному в каждой строке - количество способов получить ровно xi целых рук.Примеры:
1.Вход:5 14 10 12 6 15 8 8 9 9 15 4 4 5 6 7Ответ:
2 4 2 02.Вход:
3 6 2 8 8 8 4 2 2 3Ответ:
2 2
Система оценки:
Задача содержит 100 тестов, каждая из которых весят 1 баллов.Ограничения которые присутствуют в тестах:
- 20 теста: (1≤n≤10,1≤q≤5)
- 31 тестов: (1≤n,q≤20)
- 49 тестов: (1≤n≤40,1≤q≤105)
комментарий/решение