Processing math: 100%

Областная олимпиада по информатике, 2018 год, 10-11 класс


(k-я пара) Вам задан массив a, состоящий из n целых чисел a1, a2, ..., an.
Два элемента массива ai, aj с индексами (i,j) 1i<jn, могут образовать пару и силой этой пары назовем ai+aj. Найдите силу пары, являющейся k-й по счету, если отсортировать все пары по неубыванию силы.
Формат входных данных:
В первой строке заданы два целых числа n и k (1kn(n1)2).
Во второй строке через пробел заданы целые числа a1, a2, ..., an (0ai106).
Формат выходных данных:
Выведите ответ на задачу.
Примеры:
1.Вход:
3 3
7 1 4
Ответ:
11
2.Вход:
5 7
1 5 3 5 3
Ответ:
8
3.Вход:
10 32
0 0 0 0 0 0 0 0 0 0
Ответ:
0
4.Вход:
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 балла.
Ограничения которые присутствуют в тестах:

  • 10 тестов: 2n103
  • 20 тестов: 2n104
  • 20 тестов: 2n105

комментарий/решение(11)
(Такси) В городе Алматы проживает преуспевающий бизнесмен по имени Елибай. С недавних пор он занимается строительством N объектов . Он каждый день ездит на своем автомобиле с головного офиса в объекты, осматривает объекты и возвращается обратно в офис. Он обязательно должен возвращаться в офис между походами в объекты, так как он должен заполнить некоторые документы. Сегодня у него случилась беда, у машины разрядился аккумулятор. Чтобы не опоздать он обратился к двум сервиса для заказа такси ZhureBER и Zhett. Тарифы у них оказались недешевыми. За d километров придется платить d2 тенге. Однако его друг Айсултан - который владеет сервисом такси предложил ему купить N промо-кодов для поездки на такси со стоимостью X, тогда ему придется платить за каждую поездку X тенге если Xd, иначе X+(dX)2 тенге.
Елибай для осмотра объекта под номером i заказывает такси из офиса в объект и обратно (суммарная дистанция из офиса в объект и обратно di). Он не может за одну поездку два раза пользоваться промо-кодом и для осмотра нового объекта каждый раз заказывает новый такси.
Так как Айсултан давний друг Елибая, он предложил ему самому выбрать число X, конечно же X должно быть неотрицательным целым числом.
Формат входных данных:
Первая строка входного файла будет содержать одно число N — количество объектов с которыми занимается бизнесмен.
Во второй строке записаны N целых чисел d1,d2,dn расстояние от офиса до i-го объекта и обратно.
Формат выходных данных:
Выведите одно целое число - минимальную суммарную количество денег Елибай должен заплатить если выберет число X оптимально.
Примеры:
1.Вход:
5
7 7 7 7 7
Ответ:
35
2.Вход:
10
2 1 3 6 7 5 9 2 2 4
Ответ:
70
3.Вход:
2
0 100
Ответ:
199
Замечание:
Второй пример:
Если X = 6, мы можем получить минимальную стоимость 70.
Суммарно 6×10+(96)2+(76)2=60+9+1=70
Если X = 5, общая стоимость была бы 71. Если X = 7, общая стоимость была бы 74.
Система оценки:
Задача содержит 50 тестов, каждая из которых весят 2 балла.
Ограничения которые присутствуют в тестах:

  • 4 теста: 1N2000, 0di1000. В добавок, расстояние до всех объектов одинаково. (di=d1 для i>1)
  • 11 тестов: 1N2000, 0di1000
  • 11 тестов: 1N2000, 0di106.
  • 24 тестов: 1N200000, 0di106.

комментарий/решение(5)
(Тима и Рама) На доске в ряд написано N целых чисел. Темірлан и Рамазан играют в следующую игру:

  • Они будут ходить по очереди, первым начинает Темірлан.
  • На каждом ходу игрок может стереть с доски любое ненулевое количество чисел с начала, или с конца. Но нельзя стереть все числа.
  • Игра закончится, когда на доске останется ровно одно число. Темірлан хочет минимизировать последнее число, а Рамазан хочет максимизировать это число.

Пока Темірлан отошел, Рамазан хочет стереть ровна K чисел. Он может стереть любые числа. Когда Темірлан вернется, они начнут играть как обычно, но на доске будет написано NK чисел.
Для каждого из Q чисел K1,K2,...,KQ, Рамазан хочет узнать, какое значение у последнего оставшегося числа, если он заранее сотрет Ki чисел, и оба игрока играют оптимально?
Формат входных данных:
В первой строке находится одно целое число N.
Во второй строке находятся N целых числа A1,A2,...,AN(1Ai106) --- числа написанные на доске.
В третьей строке находится одно целое число Q.
В четвертой строке находятся Q целых числа K1,K2,...,KQ(0KiN1).
Формат выходных данных:
Выведите через пробел Q чисел, i-е из них, значения последнего оставшегося числа, если Рамазан заранее сотрет Ki чисел.
Примеры:
1.Вход:
4
1 4 2 3
4
0 1 2 3
Ответ:
1 3 3 4
2.Вход:
3
5 5 5
3
0 1 2
Ответ:
5 5 5
3.Вход:
6
2 7 5 4 8 10
3
3 5 2
Ответ:
7 10 7
Замечание:
В первом тесте при K=3, Рамазану выгодно стереть первое,второе и четвертое числа.
Система оценки:
Задача содержит 50 тестов, каждая из которых весят 2 балла.
Ограничения которые присутствуют в тестах:

  • 3 теста: Первые три теста является тестами из примеров
  • 5 тестов: 1N3,Q=1,K1=0
  • 10 тестов: 1N100,Q=1,K1=0
  • 12 тестов: 1N105,1Q2,0Ki1
  • 10 тестов: 1N105,1Q105,0KiN1
  • 10 тестов: 1N106,1Q106,0KiN1

комментарий/решение(14)
(Склад ручек) Елдан работает охранником на складе с ручками. Все ручки на складе хранятся в запакованных коробках. Елдан заметил, что всего есть n типов коробок, в коробке типа i лежит ai ручек и на складе коробок каждого типа очень много (больше 1012). Скоро должен приехать грузовик, чтобы забрать s ручек в магазин. Елдану не сообщили, сколько ручек требуется в магазине, но он знает, что это значение не больше x. Поэтому он хочет подготовить минимальное количество коробок, чтобы мог отдать любое количество ручек от 1 до x, не открывая коробок. Помогите Елдану посчитать, какое минимальное количество коробок ему нужно подготовить, либо сообщите, что это невозможно.
Формат входных данных:
В первой строке входных данных задано одно число n. Во второй строке заданы через пробел n различных чисел a1,a2,,an. В третьей строке задано одно число x. Все числе во входных данных являются целыми положительными.
Формат выходных данных:
Выведите ответ на задачу, если ответа не существует выведите 1.
Примеры:
1.Вход:
2
2 1
3
Ответ:
2
2.Вход:
1
1
1
Ответ:
1
3.Вход:
4
5 2 1 3
15
Ответ:
5
4.Вход:
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, ai25,x25
  • 6 тестов: n3, ai25,x25
  • 6 тестов: n5, ai25,x25
  • 14 тестов: n105,ai105,x105
  • 20 тестов: n105,ai1012,x1012

комментарий/решение(1)
(Опять деревья) Дается неориентированное дерево из n вершин, определим расстояние между двумя вершинами как количество ребер в их кратчайшем пути. Диаметром дерева является максимальное расстояние среди всех пар вершин в дереве.
В данной задаче вам нужно минимизировать диаметр дерева применив не более k операций удаления.
Операция удаления представляет собой удаление вершины и всех ребер смежных с ней, при этом не разрешается удалять вершину если после операции граф станет безсвязным.
Формат входных данных:
В первой строке содержатся числа n и k (0kn1) - количество вершин и максимальное количество вершин которое можно удалить.
В следующих n1 строках следует описание графа.
В каждой строке содержатся числа u и v (1u,vn) - означает что существует неориентированное ребро между вершиной u и вершиной v.
Формат выходных данных:
Выведите ровно одно число - минимальный диаметр который можно получить удалив не более k вершин.
Примеры:
1.Вход:
5 2
1 4
3 2
1 2
5 2
Ответ:
2
2.Вход:
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 теста: n20
  • 10 тестов: n100
  • 5 тестов: k=0
  • 24 тестов: n2000
  • 51 тестов: n5000

комментарий/решение
(Башни) У Алана есть n башен, у каждой из которых есть параметр ai - числитель рук и параметр bi - знаменатель рук. В q очень легких делах, которых он задумал, ему нужно определить руки у башен. Для этого, каждой башне он может сказать сделать целое количество рук - [aibi] или дробное количество рук - aibi. Для i-го дела, которые он задумал, Алану необходимо суммарно ровно xi рук. Для каждого из этих дел Алан берет все n башен, то есть суммарная \textit{рукость} всех башен должна равняться xi. Помогите Алану найти количество способов сделать это, для каждого из q легких дел.
Формат входных данных:
В первой строке дается целое положительное число n (1n40).
Во второй строке дается n целых положительных чисел a1,a2,..,an (1ai100000)
В третьей строке дается n целых положительных чисел b1,b2,..,bn (1bi100000)
В следующей дается целое положительное число q (1q100000) - количество запросов.
В следующих q строках находится по одному целому числу x - запросы из условия (1x4000000)
Формат выходных данных:
Выведите q целых числе по одному в каждой строке - количество способов получить ровно xi целых рук.
Примеры:
1.Вход:
5
14 10 12 6 15
8 8 9 9 15
4
4
5
6
7
Ответ:
2
4
2
0
2.Вход:
3
6 2 8
8 8 4
2
2
3
Ответ:
2
2
Система оценки:
Задача содержит 100 тестов, каждая из которых весят 1 баллов.
Ограничения которые присутствуют в тестах:

  • 20 теста: (1n10,1q5)
  • 31 тестов: (1n,q20)
  • 49 тестов: (1n40,1q105)

комментарий/решение