Областная олимпиада по информатике, 2018 год, 10-11 класс
(k-я пара) Вам задан массив , состоящий из целых чисел , , ..., .
Два элемента массива , с индексами , могут образовать пару и силой этой пары назовем . Найдите силу пары, являющейся -й по счету, если отсортировать все пары по неубыванию силы.
Во второй строке через пробел заданы целые числа , , ..., ().
Во втором примере можно сделать десять пар с силами { + , + , + , + , + , + , + , + , + , + } = {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.
Ограничения которые присутствуют в тестах:
Два элемента массива , с индексами , могут образовать пару и силой этой пары назовем . Найдите силу пары, являющейся -й по счету, если отсортировать все пары по неубыванию силы.
Формат входных данных:
В первой строке заданы два целых числа и ().Во второй строке через пробел заданы целые числа , , ..., ().
Формат выходных данных:
Выведите ответ на задачу.Примеры:
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
Замечание:
В первом примере можно сделать три пары с силами { + , + , + } = {7 + 1, 7 + 4, 1 + 4} = {8, 11, 5}. Если их отсортировать по неубыванию силы, то получится {5, 8, 11} и третий элемент это 11.Во втором примере можно сделать десять пар с силами { + , + , + , + , + , + , + , + , + , + } = {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 тестов:
- 20 тестов:
- 20 тестов:
комментарий/решение(11)
(Такси) В городе Алматы проживает преуспевающий бизнесмен по имени Елибай. С недавних пор он занимается строительством объектов . Он каждый день ездит на своем автомобиле с головного офиса в объекты, осматривает объекты и возвращается обратно в офис. Он обязательно должен возвращаться в офис между походами в объекты, так как он должен заполнить некоторые документы. Сегодня у него случилась беда, у машины разрядился аккумулятор. Чтобы не опоздать он обратился к двум сервиса для заказа такси ZhureBER и Zhett. Тарифы у них оказались недешевыми. За километров придется платить тенге. Однако его друг Айсултан - который владеет сервисом такси предложил ему купить промо-кодов для поездки на такси со стоимостью , тогда ему придется платить за каждую поездку тенге если , иначе тенге.
Елибай для осмотра объекта под номером заказывает такси из офиса в объект и обратно (суммарная дистанция из офиса в объект и обратно ). Он не может за одну поездку два раза пользоваться промо-кодом и для осмотра нового объекта каждый раз заказывает новый такси.
Так как Айсултан давний друг Елибая, он предложил ему самому выбрать число , конечно же должно быть неотрицательным целым числом.
Во второй строке записаны целых чисел расстояние от офиса до -го объекта и обратно.
Если X = 6, мы можем получить минимальную стоимость 70.
Суммарно
Если X = 5, общая стоимость была бы 71. Если X = 7, общая стоимость была бы 74.
Ограничения которые присутствуют в тестах:
Елибай для осмотра объекта под номером заказывает такси из офиса в объект и обратно (суммарная дистанция из офиса в объект и обратно ). Он не может за одну поездку два раза пользоваться промо-кодом и для осмотра нового объекта каждый раз заказывает новый такси.
Так как Айсултан давний друг Елибая, он предложил ему самому выбрать число , конечно же должно быть неотрицательным целым числом.
Формат входных данных:
Первая строка входного файла будет содержать одно число — количество объектов с которыми занимается бизнесмен.Во второй строке записаны целых чисел расстояние от офиса до -го объекта и обратно.
Формат выходных данных:
Выведите одно целое число - минимальную суммарную количество денег Елибай должен заплатить если выберет число оптимально.Примеры:
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.
Суммарно
Если X = 5, общая стоимость была бы 71. Если X = 7, общая стоимость была бы 74.
Система оценки:
Задача содержит 50 тестов, каждая из которых весят 2 балла.Ограничения которые присутствуют в тестах:
- 4 теста: , . В добавок, расстояние до всех объектов одинаково. ( для )
- 11 тестов: ,
- 11 тестов: , .
- 24 тестов: , .
комментарий/решение(5)
(Тима и Рама) На доске в ряд написано целых чисел. Темірлан и Рамазан играют в следующую игру:
Пока Темірлан отошел, Рамазан хочет стереть ровна чисел. Он может стереть любые числа. Когда Темірлан вернется, они начнут играть как обычно, но на доске будет написано чисел.
Для каждого из чисел , Рамазан хочет узнать, какое значение у последнего оставшегося числа, если он заранее сотрет чисел, и оба игрока играют оптимально?
Во второй строке находятся целых числа --- числа написанные на доске.
В третьей строке находится одно целое число .
В четвертой строке находятся целых числа .
Ограничения которые присутствуют в тестах:
- Они будут ходить по очереди, первым начинает Темірлан.
- На каждом ходу игрок может стереть с доски любое ненулевое количество чисел с начала, или с конца. Но нельзя стереть все числа.
- Игра закончится, когда на доске останется ровно одно число. Темірлан хочет минимизировать последнее число, а Рамазан хочет максимизировать это число.
Пока Темірлан отошел, Рамазан хочет стереть ровна чисел. Он может стереть любые числа. Когда Темірлан вернется, они начнут играть как обычно, но на доске будет написано чисел.
Для каждого из чисел , Рамазан хочет узнать, какое значение у последнего оставшегося числа, если он заранее сотрет чисел, и оба игрока играют оптимально?
Формат входных данных:
В первой строке находится одно целое число .Во второй строке находятся целых числа --- числа написанные на доске.
В третьей строке находится одно целое число .
В четвертой строке находятся целых числа .
Формат выходных данных:
Выведите через пробел чисел, -е из них, значения последнего оставшегося числа, если Рамазан заранее сотрет чисел.Примеры:
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
Замечание:
В первом тесте при , Рамазану выгодно стереть первое,второе и четвертое числа.Система оценки:
Задача содержит 50 тестов, каждая из которых весят 2 балла.Ограничения которые присутствуют в тестах:
- 3 теста: Первые три теста является тестами из примеров
- 5 тестов:
- 10 тестов:
- 12 тестов:
- 10 тестов:
- 10 тестов:
комментарий/решение(14)
(Склад ручек) Елдан работает охранником на складе с ручками. Все ручки на складе хранятся в запакованных коробках. Елдан заметил, что всего есть типов коробок, в коробке типа лежит ручек и на складе коробок каждого типа очень много (больше ). Скоро должен приехать грузовик, чтобы забрать ручек в магазин. Елдану не сообщили, сколько ручек требуется в магазине, но он знает, что это значение не больше . Поэтому он хочет подготовить минимальное количество коробок, чтобы мог отдать любое количество ручек от до , не открывая коробок. Помогите Елдану посчитать, какое минимальное количество коробок ему нужно подготовить, либо сообщите, что это невозможно.
При он отдаст одну коробку .
При он отдаст одну коробку .
При он отдаст две коробки (2 + 1 = 3).
Во втором примере Елдан подготовит одну коробку .
В третьем примере Елдан может подготовить коробки с типами .
При он отдаст коробку .
При он отдаст коробку .
При он отдаст коробки .
При он отдаст коробки .
При он отдаст коробки .
При он отдаст коробки .
При он отдаст коробки .
При он отдаст коробки .
При он отдаст коробки .
При он отдаст коробки .
При он отдаст коробки .
При он отдаст коробки .
При он отдаст коробки .
При он отдаст коробки .
При он отдаст коробки .
Обратите внимание, что в данном тесте есть и другие варианты выбрать коробки, например .
В четвертом примере Елдан не может выбрать какие-либо коробки, чтобы отдать две ручки.
Ограничения которые присутствуют в тестах:
Формат входных данных:
В первой строке входных данных задано одно число . Во второй строке заданы через пробел различных чисел . В третьей строке задано одно число . Все числе во входных данных являются целыми положительными.Формат выходных данных:
Выведите ответ на задачу, если ответа не существует выведите .Примеры:
1.Вход:2 2 1 3Ответ:
22.Вход:
1 1 1Ответ:
13.Вход:
4 5 2 1 3 15Ответ:
54.Вход:
2 5 3 2Ответ:
-1
Замечание:
В первом примере Елдан может подготовить коробки с типами .При он отдаст одну коробку .
При он отдаст одну коробку .
При он отдаст две коробки (2 + 1 = 3).
Во втором примере Елдан подготовит одну коробку .
В третьем примере Елдан может подготовить коробки с типами .
При он отдаст коробку .
При он отдаст коробку .
При он отдаст коробки .
При он отдаст коробки .
При он отдаст коробки .
При он отдаст коробки .
При он отдаст коробки .
При он отдаст коробки .
При он отдаст коробки .
При он отдаст коробки .
При он отдаст коробки .
При он отдаст коробки .
При он отдаст коробки .
При он отдаст коробки .
При он отдаст коробки .
Обратите внимание, что в данном тесте есть и другие варианты выбрать коробки, например .
В четвертом примере Елдан не может выбрать какие-либо коробки, чтобы отдать две ручки.
Система оценки:
Задача содержит 50 тестов, каждая из которых весят 2 балла.Ограничения которые присутствуют в тестах:
- 4 теста: ,
- 6 тестов: ,
- 6 тестов: ,
- 14 тестов:
- 20 тестов:
комментарий/решение(1)
(Опять деревья) Дается неориентированное дерево из вершин, определим расстояние между двумя вершинами как количество ребер в их кратчайшем пути. Диаметром дерева является максимальное расстояние среди всех пар вершин в дереве.
В данной задаче вам нужно минимизировать диаметр дерева применив не более операций удаления.
Операция удаления представляет собой удаление вершины и всех ребер смежных с ней, при этом не разрешается удалять вершину если после операции граф станет безсвязным.
В следующих строках следует описание графа.
В каждой строке содержатся числа и () - означает что существует неориентированное ребро между вершиной и вершиной .
Ограничения которые присутствуют в тестах:
В данной задаче вам нужно минимизировать диаметр дерева применив не более операций удаления.
Операция удаления представляет собой удаление вершины и всех ребер смежных с ней, при этом не разрешается удалять вершину если после операции граф станет безсвязным.
Формат входных данных:
В первой строке содержатся числа и () - количество вершин и максимальное количество вершин которое можно удалить.В следующих строках следует описание графа.
В каждой строке содержатся числа и () - означает что существует неориентированное ребро между вершиной и вершиной .
Формат выходных данных:
Выведите ровно одно число - минимальный диаметр который можно получить удалив не более вершин.Примеры:
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 теста:
- 10 тестов:
- 5 тестов:
- 24 тестов:
- 51 тестов:
комментарий/решение
(Башни) У Алана есть башен, у каждой из которых есть параметр - числитель рук и параметр - знаменатель рук. В очень легких делах, которых он задумал, ему нужно определить руки у башен. Для этого, каждой башне он может сказать сделать целое количество рук - или дробное количество рук - . Для -го дела, которые он задумал, Алану необходимо суммарно ровно рук. Для каждого из этих дел Алан берет все башен, то есть суммарная \textit{рукость} всех башен должна равняться . Помогите Алану найти количество способов сделать это, для каждого из легких дел.
Во второй строке дается целых положительных чисел ()
В третьей строке дается целых положительных чисел ()
В следующей дается целое положительное число () - количество запросов.
В следующих строках находится по одному целому числу - запросы из условия ()
Ограничения которые присутствуют в тестах:
Формат входных данных:
В первой строке дается целое положительное число ().Во второй строке дается целых положительных чисел ()
В третьей строке дается целых положительных чисел ()
В следующей дается целое положительное число () - количество запросов.
В следующих строках находится по одному целому числу - запросы из условия ()
Формат выходных данных:
Выведите целых числе по одному в каждой строке - количество способов получить ровно целых рук.Примеры:
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 теста:
- 31 тестов:
- 49 тестов:
комментарий/решение