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

Задача

(k-я пара) Вам задан массив

a

$a$ , состоящий из

n

$n$ целых чисел

a_{1}

$a_1$ ,

a_{2}

$a_2$ , ...,

a_{n}

$a_n$ .
Два элемента массива

a_{i}

$a_i$ ,

a_{j}

$a_j$ с индексами

(i, j)

$(i, j)$

1 \leq i < j \leq n

$1 \le i < j \le n$ , могут образовать пару и силой этой пары назовем

a_{i} + a_{j}

$a_i + a_j$ . Найдите силу пары, являющейся

k

$k$ -й по счету, если отсортировать все пары по неубыванию силы.

Формат входных данных:

В первой строке заданы два целых числа

n

$n$ и

k

$k$ (

1 \leq k \leq \frac{n * (n - 1)}{2}

$1 \le k \le \frac{n * (n - 1)}{2}$ ).
Во второй строке через пробел заданы целые числа

a_{1}

$a_1$ ,

a_{2}

$a_2$ , ...,

a_{n}

$a_n$ (

0 \leq a_{i} \leq 10^{6}

$0 \le a_i \le 10^6$ ).

Формат выходных данных:

Выведите ответ на задачу.

Примеры:

1.Вход:

3 3
7 1 4

Ответ:

2.Вход:

5 7
1 5 3 5 3

Ответ:

3.Вход:

10 32
0 0 0 0 0 0 0 0 0 0

Ответ:

4.Вход:

9 15
5 6 3 0 0 4 1 4 1

Ответ:

Замечание:

В первом примере можно сделать три пары с силами {

a_{1}

$a_1$ +

a_{2}

$a_2$ ,

a_{1}

$a_1$ +

a_{3}

$a_3$ ,

a_{2}

$a_2$ +

a_{3}

$a_3$ } = {7 + 1, 7 + 4, 1 + 4} = {8, 11, 5}. Если их отсортировать по неубыванию силы, то получится {5, 8, 11} и третий элемент это 11.
Во втором примере можно сделать десять пар с силами {

a_{1}

$a_1$ +

a_{2}

$a_2$ ,

a_{1}

$a_1$ +

a_{3}

$a_3$ ,

a_{1}

$a_1$ +

a_{4}

$a_4$ ,

a_{1}

$a_1$ +

a_{5}

$a_5$ ,

a_{2}

$a_2$ +

a_{3}

$a_3$ ,

a_{2}

$a_2$ +

a_{4}

$a_4$ ,

a_{2}

$a_2$ +

a_{5}

$a_5$ ,

a_{3}

$a_3$ +

a_{4}

$a_4$ ,

a_{3}

$a_3$ +

a_{5}

$a_5$ ,

a_{4}

$a_4$ +

a_{5}

$a_5$ } = {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 тестов: $2 \le n \le 10^3$
20 тестов: $2 \le n \le 10^4$
20 тестов: $2 \le n \le 10^5$

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

Задача

(Такси) В городе Алматы проживает преуспевающий бизнесмен по имени Елибай. С недавних пор он занимается строительством

N

$N$ объектов . Он каждый день ездит на своем автомобиле с головного офиса в объекты, осматривает объекты и возвращается обратно в офис. Он обязательно должен возвращаться в офис между походами в объекты, так как он должен заполнить некоторые документы. Сегодня у него случилась беда, у машины разрядился аккумулятор. Чтобы не опоздать он обратился к двум сервиса для заказа такси ZhureBER и Zhett. Тарифы у них оказались недешевыми. За

d

$d$ километров придется платить

d^{2}

$d^2$ тенге. Однако его друг Айсултан - который владеет сервисом такси предложил ему купить

N

$N$ промо-кодов для поездки на такси со стоимостью

X

$X$ , тогда ему придется платить за каждую поездку

X

$X$ тенге если

X \geq d

$X \ge d$ , иначе

X + (d - X)^{2}

$X + (d - X)^2$ тенге.
Елибай для осмотра объекта под номером

i

$i$ заказывает такси из офиса в объект и обратно (суммарная дистанция из офиса в объект и обратно

d_{i}

$d_i$ ). Он не может за одну поездку два раза пользоваться промо-кодом и для осмотра нового объекта каждый раз заказывает новый такси.
Так как Айсултан давний друг Елибая, он предложил ему самому выбрать число

X

$X$ , конечно же

X

$X$ должно быть неотрицательным целым числом.

Формат входных данных:

Первая строка входного файла будет содержать одно число

N

$N$ — количество объектов с которыми занимается бизнесмен.
Во второй строке записаны

N

$N$ целых чисел

d_{1}, d_{2}, \dots d_{n}

$d_1, d_2, \ldots d_n$ расстояние от офиса до

i

$i$ -го объекта и обратно.

Формат выходных данных:

Выведите одно целое число - минимальную суммарную количество денег Елибай должен заплатить если выберет число

X

$X$ оптимально.

Примеры:

1.Вход:

5
7 7 7 7 7

Ответ:

2.Вход:

10
2 1 3 6 7 5 9 2 2 4

Ответ:

3.Вход:

2
0 100

Ответ:

Замечание:

Второй пример:
Если X = 6, мы можем получить минимальную стоимость 70.
Суммарно

6 \times 10 + {(9 - 6)}^{2} + {(7 - 6)}^{2} = 60 + 9 + 1 = 70

$6 \times 10 + {(9 - 6)}^2 + {(7 - 6)}^2 = 60 + 9 + 1 = 70$
Если X = 5, общая стоимость была бы 71. Если X = 7, общая стоимость была бы 74.

Система оценки:

Задача содержит 50 тестов, каждая из которых весят 2 балла.
Ограничения которые присутствуют в тестах:

4 теста: $1 \le N \le 2000$ , $0 \le d_i \le 1000$ . В добавок, расстояние до всех объектов одинаково. ( $d_i = d_1$ для $i > 1$ )
11 тестов: $1 \le N \le 2000$ , $0 \le d_i \le 1000$
11 тестов: $1 \le N \le 2000$ , $0 \le d_i \le 10^6$ .
24 тестов: $1 \le N \le 200000$ , $0 \le d_i \le 10^6$ .

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

Задача

(Тима и Рама) На доске в ряд написано

N

$N$ целых чисел. Темірлан и Рамазан играют в следующую игру:

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

Пока Темірлан отошел, Рамазан хочет стереть ровна

K

$K$ чисел. Он может стереть любые числа. Когда Темірлан вернется, они начнут играть как обычно, но на доске будет написано

N - K

$N-K$ чисел.
Для каждого из

Q

$Q$ чисел

K_{1}, K_{2}, . . ., K_{Q}

$K_1,K_2, ..., K_Q$ , Рамазан хочет узнать, какое значение у последнего оставшегося числа, если он заранее сотрет

K_{i}

$K_i$ чисел, и оба игрока играют оптимально?

Формат входных данных:

В первой строке находится одно целое число

N

$N$ .
Во второй строке находятся

N

$N$ целых числа

A_{1}, A_{2}, . . ., A_{N} (1 \leq A_{i} \leq 10^{6})

$A_1,A_2,...,A_N (1 \le A_i \le 10^6)$ --- числа написанные на доске.
В третьей строке находится одно целое число

Q

$Q$ .
В четвертой строке находятся

Q

$Q$ целых числа

K_{1}, K_{2}, . . ., K_{Q} (0 \leq K_{i} \leq N - 1)

$K_1,K_2,...,K_Q(0 \le K_i \le N - 1)$ .

Формат выходных данных:

Выведите через пробел

Q

$Q$ чисел,

i

$i$ -е из них, значения последнего оставшегося числа, если Рамазан заранее сотрет

K_{i}

$K_i$ чисел.

Примеры:

1.Вход:

Ответ:

1 3 3 4

2.Вход:

Ответ:

5 5 5

3.Вход:

6
2 7 5 4 8 10
3
3 5 2

Ответ:

7 10 7

Замечание:

В первом тесте при

K = 3

$K=3$ , Рамазану выгодно стереть первое,второе и четвертое числа.

Система оценки:

Задача содержит 50 тестов, каждая из которых весят 2 балла.
Ограничения которые присутствуют в тестах:

3 теста: Первые три теста является тестами из примеров
5 тестов: $1 \le N \le 3, Q = 1, K_1 = 0$
10 тестов: $1 \le N \le 100, Q = 1, K_1 = 0$
12 тестов: $1 \le N \le 10^5, 1\le Q \le 2, 0 \le K_i \le 1$
10 тестов: $1 \le N \le 10^5, 1 \le Q \le 10^5,0 \le K_i \le N - 1$
10 тестов: $1 \le N \le 10^6, 1 \le Q \le 10^6, 0 \le K_i \le N - 1$

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

Задача

(Склад ручек) Елдан работает охранником на складе с ручками. Все ручки на складе хранятся в запакованных коробках. Елдан заметил, что всего есть

n

$n$ типов коробок, в коробке типа

i

$i$ лежит

a_{i}

$a_i$ ручек и на складе коробок каждого типа очень много (больше

10^{12}

$10^{12}$ ). Скоро должен приехать грузовик, чтобы забрать

s

$s$ ручек в магазин. Елдану не сообщили, сколько ручек требуется в магазине, но он знает, что это значение не больше

x

$x$ . Поэтому он хочет подготовить минимальное количество коробок, чтобы мог отдать любое количество ручек от

1

$1$ до

x

$x$ , не открывая коробок. Помогите Елдану посчитать, какое минимальное количество коробок ему нужно подготовить, либо сообщите, что это невозможно.

Формат входных данных:

В первой строке входных данных задано одно число

n

$n$ . Во второй строке заданы через пробел

n

$n$ различных чисел

a_{1}, a_{2}, \dots, a_{n}

$a_1, a_2, \dots, a_n$ . В третьей строке задано одно число

x

$x$ . Все числе во входных данных являются целыми положительными.

Формат выходных данных:

Выведите ответ на задачу, если ответа не существует выведите

- 1

$-1$ .

Примеры:

1.Вход:

2
2 1
3

Ответ:

2.Вход:

1
1
1

Ответ:

3.Вход:

4
5 2 1 3
15

Ответ:

4.Вход:

2
5 3
2

Ответ:

-1

Замечание:

В первом примере Елдан может подготовить коробки с типами

a_{1}, a_{2}

${a_1, a_2}$ .
При

s = 1

$s = 1$ он отдаст одну коробку

a_{2}

$a_2$ .
При

s = 2

$s = 2$ он отдаст одну коробку

a_{1}

$a_1$ .
При

s = 3

$s = 3$ он отдаст две коробки

a_{1}, a_{2}

$a_1, a_2$ (2 + 1 = 3).
Во втором примере Елдан подготовит одну коробку

a_{1}

${a_1}$ .
В третьем примере Елдан может подготовить коробки с типами

a_{1}, a_{1}, a_{2}, a_{2}, a_{3}

${a_1, a_1, a_2, a_2, a_3}$ .
При

s = 1

$s = 1$ он отдаст коробку

a_{3}

$a_3$ .
При

s = 2

$s = 2$ он отдаст коробку

a_{2}

$a_2$ .
При

s = 3

$s = 3$ он отдаст коробки

a_{2}, a_{3}

$a_2, a_3$ .
При

s = 4

$s = 4$ он отдаст коробки

a_{2}, a_{2}

$a_2, a_2$ .
При

s = 5

$s = 5$ он отдаст коробки

a_{2}, a_{2}, a_{3}

$a_2, a_2, a_3$ .
При

s = 6

$s = 6$ он отдаст коробки

a_{1}, a_{3}

$a_1, a_3$ .
При

s = 7

$s = 7$ он отдаст коробки

a_{1}, a_{2}

$a_1, a_2$ .
При

s = 8

$s = 8$ он отдаст коробки

a_{1}, a_{2}, a_{3}

$a_1, a_2, a_3$ .
При

s = 9

$s = 9$ он отдаст коробки

a_{1}, a_{2}, a_{2}

$a_1, a_2, a_2$ .
При

s = 10

$s = 10$ он отдаст коробки

a_{1}, a_{1}

$a_1, a_1$ .
При

s = 11

$s = 11$ он отдаст коробки

a_{1}, a_{1}, a_{3}

$a_1, a_1, a_3$ .
При

s = 12

$s = 12$ он отдаст коробки

a_{1}, a_{1}, a_{2}

$a_1, a_1, a_2$ .
При

s = 13

$s = 13$ он отдаст коробки

a_{1}, a_{1}, a_{2}, a_{3}

$a_1, a_1, a_2, a_3$ .
При

s = 14

$s = 14$ он отдаст коробки

a_{1}, a_{1}, a_{2}, a_{2}

$a_1, a_1, a_2, a_2$ .
При

s = 15

$s = 15$ он отдаст коробки

a_{1}, a_{1}, a_{2}, a_{2}, a_{3}

$a_1, a_1, a_2, a_2, a_3$ .
Обратите внимание, что в данном тесте есть и другие варианты выбрать коробки, например

a_{1}, a_{1}, a_{3}, a_{3}, a_{4}

${a_1, a_1, a_3, a_3, a_4}$ .
В четвертом примере Елдан не может выбрать какие-либо коробки, чтобы отдать две ручки.

Система оценки:

Задача содержит 50 тестов, каждая из которых весят 2 балла.
Ограничения которые присутствуют в тестах:

4 теста: $n = 1$ , $a_i \le 25, x \le 25$
6 тестов: $n \le 3$ , $a_i \le 25, x \le 25$
6 тестов: $n \le 5$ , $a_i \le 25, x \le 25$
14 тестов: $n \le 10^5, a_i \le 10^5, x \le 10^5$
20 тестов: $n \le 10^5, a_i \le 10^{12}, x \le 10^{12}$

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

Задача

(Опять деревья) Дается неориентированное дерево из

n

$n$ вершин, определим расстояние между двумя вершинами как количество ребер в их кратчайшем пути. Диаметром дерева является максимальное расстояние среди всех пар вершин в дереве.
В данной задаче вам нужно минимизировать диаметр дерева применив не более

k

$k$ операций удаления.
Операция удаления представляет собой удаление вершины и всех ребер смежных с ней, при этом не разрешается удалять вершину если после операции граф станет безсвязным.

Формат входных данных:

В первой строке содержатся числа

n

$n$ и

k

$k$ (

0 \leq k \leq n - 1

$0 \le k \le n - 1$ ) - количество вершин и максимальное количество вершин которое можно удалить.
В следующих

n - 1

$n-1$ строках следует описание графа.
В каждой строке содержатся числа

u

$u$ и

v

$v$ (

1 \leq u, v \leq n

$1 \le u, v \le n$ ) - означает что существует неориентированное ребро между вершиной

u

$u$ и вершиной

v

$v$ .

Формат выходных данных:

Выведите ровно одно число - минимальный диаметр который можно получить удалив не более

k

$k$ вершин.

Примеры:

1.Вход:

Ответ:

2.Вход:

Ответ:

Система оценки:

Задача содержит 100 тестов, каждая из которых весят 1 балл.
Ограничения которые присутствуют в тестах:

10 теста: $n \le 20$
10 тестов: $n \le 100$
5 тестов: $k = 0$
24 тестов: $n \le 2000$
51 тестов: $n \le 5000$

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

Задача

(Башни) У Алана есть

n

$n$ башен, у каждой из которых есть параметр

a_{i}

$a_i$ - числитель рук и параметр

b_{i}

$b_i$ - знаменатель рук. В

q

$q$ очень легких делах, которых он задумал, ему нужно определить руки у башен. Для этого, каждой башне он может сказать сделать целое количество рук -

[\frac{a_{i}}{b_{i}}]

$[\frac{a_i}{b_i}]$ или дробное количество рук -

\frac{a_{i}}{b_{i}}

$\frac{a_i}{b_i}$ . Для

i

$i$ -го дела, которые он задумал, Алану необходимо суммарно ровно

x_{i}

$x_i$ рук. Для каждого из этих дел Алан берет все

n

$n$ башен, то есть суммарная \textit{рукость} всех башен должна равняться

x_{i}

$x_i$ . Помогите Алану найти количество способов сделать это, для каждого из

q

$q$ легких дел.

Формат входных данных:

В первой строке дается целое положительное число

n

$n$ (

1 \leq n \leq 40

$1 \le n \le 40$ ).
Во второй строке дается

n

$n$ целых положительных чисел

a_{1}, a_{2}, . ., a_{n}

$a_1, a_2, .., a_n$ (

1 \leq a_{i} \leq 100000

$1 \le a_i \le 100000$ )
В третьей строке дается

n

$n$ целых положительных чисел

b_{1}, b_{2}, . ., b_{n}

$b_1, b_2, .., b_n$ (

1 \leq b_{i} \leq 100000

$1 \le b_i \le 100000$ )
В следующей дается целое положительное число

q

$q$ (

1 \leq q \leq 100000

$1 \le q \le 100000$ ) - количество запросов.
В следующих

q

$q$ строках находится по одному целому числу

x

$x$ - запросы из условия (

1 \leq x \leq 4000000

$1 \le x \le 4000000$ )

Формат выходных данных:

Выведите

q

$q$ целых числе по одному в каждой строке - количество способов получить ровно

x_{i}

$x_i$ целых рук.

Примеры:

1.Вход:

5
14 10 12 6 15
8 8 9 9 15
4
4
5
6
7

Ответ:

2.Вход:

Ответ:

2
2

Система оценки:

Задача содержит 100 тестов, каждая из которых весят 1 баллов.
Ограничения которые присутствуют в тестах:

20 теста: $(1 \le n \le 10, 1 \le q \le 5)$
31 тестов: $(1 \le n,q \le 20)$
49 тестов: $(1 \le n \le 40, 1 \le q \le 10^5)$

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