II этап отбора на престижные международные

олимпиады по информатике.
2-день. Ташкент, Узбекистан, 19-февраля 2023-год.

A. Площадь параллелограмма
У Зарифа есть любимое поле на декартовой системе координат. И как вы уже могли
догадаться, это поле в виде параллелограмма. Чтобы безошибочно дойти к нему, он
записал на бумажке координаты всех четырёх углов этого параллелограмма.
Но так получилось что его сестра случайно вычеркнула одно из этих координат на
бумажке.
Конечно-же, Зариф может потратить кое-какое время и восстановить зачёркнутую
координату, но одним из занятых людей. И прямо сейчас ему срочно понадобилось
узнать площадь этого поля.
Зная только оставшиеся 3 координаты углов параллелограмма (x1,y1,x 2,y 2,x 3,y3),
подсчитайте площадь параллелограмма. Только быстрее, он спешит.
Входные данные:
В первой строке входного потока даны две целых чисел - x1,y1(−1000 ≤ x1,y1 ≤ 1000);
Во втрой строке даны два две целых чисел - x 2,y 2(−1000 ≤ x 2,y 2 ≤ 1000);
В третьей строке даны два две целых чисел - x 3,y3(−1000 ≤ x 3,y3 ≤ 1000).
Выходные данные:
В единственной строке выведите одно целое число, ответ на задачу.

input output
41 12
54
01
-2 0 4
-1 1
20

Комментарий:
В первом тесте любимое поле Зарифа может выглядеть таким образом:

1
 II этап отбора на престижные международные
олимпиады по информатике.
2-день. Ташкент, Узбекистан, 19-февраля 2023-год.

B. Array X Array
У Адизбека есть массив A длины n состоящий из положительных целых чисел.
Суннатбек заинтересовался этим массивом и попросил у Адизбека одолжить его. Но
Адизбек поступил интересным способом. Ведь не надо забывать что Адизбек известен
своими загадками.
Адизбек построил матрицу S состоящий из n строк и n столбцов а также заполнил его
следующим образом:
- Для любых i ≠ j(1 ≤ i, j ≤ n) S[i ][ j ] = A[i ] * A[ j ] .
- Для любого i(1 ≤ i ≤ n) S[i ][i ] = − 1.
Суннатбек хочет восстановить массив A с помощью матрицы S.
Входные данные:
В первой строке входного потока дано одно целое число - n(1 ≤ n ≤ 500).
В последующих n строк даны по n чисел - элементы массива S.
Выходные данные:
В единственной строке выведите n чисел, элементы массива A.
Гарантируется что элементы массива A не превышают 1000.

input output
3 332
-1 9 6
9 -1 6
6 6 -1
4 7124
-1 7 14 28
7 -1 2 4
14 2 -1 8
28 4 8 -1

2
 II этап отбора на престижные международные
олимпиады по информатике.
2-день. Ташкент, Узбекистан, 19-февраля 2023-год.

C. Множество символов
Зачем задаче длинное условие, если она и так легка?
Множество символов, это множество состоящее только из строчных букв английского
алфавита.
Есть n множеств символов пронумерованное от 1 до n. До обработки запросов, все
множества пустые. Далее m раз задаются запросы. Они бывают двух видов:
- В первом виде запроса задаются число i d x и строка st. Гарантируется что в строке
st все символы уникальные(не повторяются). Для обработки этого запроса нужно
изменить множества следующим образом:
- Если символ x содержится в строке st, но не содержится во i d x-множестве,
добавьте символ x в i d x-множество.
- Если символ x содержится в и строке st, и во i d x-множестве, удалите символ x
в i d x-множестве.
- Если символ x не содержится в строке st, ничего делать не надо (x тут может
быть любая строчная буква английского алфавита).
- Во втором типе запроса даются два числа l и r. Для этого запроса вы должны
вывести максимальную длину строки которую можно сконструировать использовав
буквы во всех множествах на отрезке [l, r].
Создайте программу который обрабатывает все типы запроса и выводит ответ для
второго типа запроса.
Входные данные:
В первой строке входного потока даны две целых чисел - n, m(1 ≤ n, m ≤ 2 * 10 5).
В последующих m строк задаются параметры очередного запроса:
- Для запроса первого вида задаются 1 i d x st. Где i d x− натуральное число на
отрезке [1...n], st− строка состоящая из строчных букв английского алфавита.
Гарантируется что в строке st все символы уникальные(не повторяются).
- Для второго типа запроса задаются 2 l r. Где l, r − натуральные числа на отрезке
[1…n] и где l ≤ r.
Выходные данные:
Для всех запросов второго вида, выведите ответ на запрос в новой строке.

3
 II этап отбора на престижные международные
олимпиады по информатике.
2-день. Ташкент, Узбекистан, 19-февраля 2023-год.

input output
3 6 6
1 1 abc 0
1 3 bar 2
2 1 3
2 2 2
1 1 a
2 1 1
1 3 8
1 1 salom
1 1 dunyo
2 11

Комментарий:
В первом тесте:
До обработки запросов множества выглядят следующим образом: {} {} {}
После обработки первого запроса множества выглядят следующим образом:
{a b c} {} {}
После обработки второго запроса множества выглядят следующим образом:
{a b c} {} {a b r}
После обработки пятого запроса множества выглядят следующим образом:
{b c} {} {a b r}

Во втором тесте:
После обработки всех запросов множества выглядят следующим образом:
{a d l m n s u y}

4
 II этап отбора на престижные международные
олимпиады по информатике.
2-день. Ташкент, Узбекистан, 19-февраля 2023-год.

D. Найди вершину!
Это интерактивная задача!
Существует дерево вершины которых пронумерованы от 1 до n. В этом дереве
выбрали две различных вершин a и b. Но они скрыты, и вы не знаете значения a и b.
Для любой вершины u определим что
dis[u] = (минимальное расстояние от вершины a до вершины u)+
(минимальное расстояние от вершины b до вершины u)
Вы можете задавать два вида запросов системе. В сумме количество ваших запросов
не должно превышать 60.
• ? 1 x. Система для запроса этого типа, ответить значением dis[x].
• ? 2 x. Система для запроса этого типа, ответит числами k y1 y 2 y3 . . . yk. Где
k - количество соседей вершины x. А y1, y 2, y3, . . . yk это такая перестановка
списка соседей вершины x что для них выполняется условие
dis[y1] ≤ dis[y 2] ≤ dis[y3] ≤ . . . ≤ dis[yk ].
Ваша задача найти либо a, либо b, либо любую вершины которую лежит на
кратчайшем пути от вершины a до вершины b. Выведите ответ на задачу в
формате ! v.
Входные данные:
В первой строке дано единственное целое число - n(2 ≤ n ≤ 2 * 10 5).
В последующих n − 1 задаются по две целых чисел - u, v(1 ≤ u, v ≤ n, u ≠ v)
характеризующие ребра дерево. Это означает что существует ребро от вершины
u к вершине v.
Работа с системой:
Считайте входные данные с входного потока.
Для того чтобы задать запрос выведите ? 1 x или ? 2 x в выходной поток (1 ≤ x ≤ n),
и очистите буфер выходного потока (На языках C/С++: ush(stdout) или
cout. ush()).
Ответы на запросы можете считывать с входного потока.
Если ваши количество ваших запросов превысят 60, или если вы не выведите ответ в
виде ! v (1 ≤ v ≤ n) то система выдаст TLE. Как только вы выведите ответ на задачу
система остановится и ваша программа тоже должна остановится. Вывод ответа не
считается запросом.

5
fl
ffl
 II этап отбора на престижные международные
олимпиады по информатике.
2-день. Ташкент, Узбекистан, 19-февраля 2023-год.

input output
5
1 4
4 3
2 4
5 1
?13
5
?24
3213
?15
3
?25
11
!4

Комментрий:
В первом тесте n = 5 и были выбраны a = 2, b = 5.

d i s[1] = (м.р. от вершины 1 до вершины 2) + (м.р. от вершины 1 до вершины 5) = 2+1 = 3;

d i s[2] = (м.р. от вершины 2 до вершины 2) + (м.р. от вершины 2 до вершины 5) = 0+3 = 3;
d i s[3] = (м.р. от вершины 3 до вершины 2) + (м.р. от вершины 3 до вершины 5) = 2+3 = 5;
d i s[4] = (м.р. от вершины 4 до вершины 2) + (м.р. от вершины 4 до вершины 5) = 1+2 = 3;
d i s[5] = (м.р. от вершины 5 до вершины 2) + (м.р. от вершины 5 до вершины 5) = 3+0 = 3;
Ответом на запрос ? 2 4: могут быть 3 1 2 3 или 3 2 1 3. Потому что
dis[1] = dis[2] < dis3.
Ответ на задачу мог быть любая вершина кроме 3-вершины. Что означает только
ответ ! 3 система не приняла бы система.

*На примере выше добавлены дополнительные пустые строки только для визуального
вида. На самом деле между числами не присутствуют пустые строки.

6
 II этап отбора на престижные международные
олимпиады по информатике.
2-день. Ташкент, Узбекистан, 19-февраля 2023-год.

E. Доставка продовольствии
В нашей стране, особенно в Ташкенте службы доставки крайне улучшились в
последние годы. Сегодня на дом можно заказать не только еду из фаст-фудов но и
продукты из магазинов.
Азимжон тоже работает менеджером в одной из таких служб доставки. Менеджеры в
основном указывают что делать водителям (доставщикам).
Каждый заказ можно описать двумя параметрами: p - координата где расположен
дом куда надо доставить продукты(адрес заказчика) и k - сколько кг продовольствии
заказал клиент. Не забывайте что город Азимжона расположен на одной прямой.
По дороге расположены n супермаркетов. i(1 ≤ i ≤ n)-супермаркет находится на точке
xi. Каждый кг продовольствия в этом магазине стоит ai единиц денег. А также
воспользоваться парковой рядом с этим супермаркетом будет стоить bi единиц денег.
Офис расположен на точке 0.
Доставка всегда осуществляется по следующему сценарию:
- Водитель выезжает из офиса (из точки 0) к дому заказчика;
- Менеджер выбирает один из супермаркетов расположенный именно на пути
водителя (на отрезке [0...p]);
- Водитель паркуется на парковочное место рядом с супермаркетом и платить
соответствующую плату за это. Потом он закупает нужное количество
продовольствии в этом супермаркете по цене в супермаркете за кг и возвращается к
машине;
- Купленные продукты он отвезёт заказчику и получит за это плату;
- Водитель вернётся в офис.
Если менеджер может выбрать супермаркет который будет тратить наименьшее
количество денег, то считается что он хороший работник. Но у Азимжона не всегда
это получается. Поэтому он попросил вас помочь.
Сегодня будут q заказов. Если вы будете знать значения параметров k и p для
каждого запроса, определите минимальное количество денег которое может потратить
водитель.
Входные данные:
В первой строке даны две целых чисел - n, q(1 ≤ n, q ≤ 2 * 10 5) число супермаркетов и
число заказов.
Во второй строке даны n целых чисел - xi(1 ≤ x1 < x 2 . . . < xn ≤ 109) координаты
каждого супермаркета относительно офиса.
В третьей строке даны n целых чисел - ai(1 ≤ ai ≤ 109) стоимость 1 кг продовольствия
в супермаркетах.

7
 II этап отбора на престижные международные
олимпиады по информатике.
2-день. Ташкент, Узбекистан, 19-февраля 2023-год.

В четвёртой строке даны n целых чисел - bi(1 ≤ bi ≤ 109) стоимость использование

парковкой рядом с супермаркетом.
В последующих q строках даны по два целых чисел - p, k (1 ≤ p ≤ 109, k ≤ 3 * 106 )
значение параметров очередного запроса.
Выходные данные:
Для каждого заказа выведите минимальное количество денег которое может
потратить водитель. Если между офисом и домом заказчика не найдётся ни одного
супермаркета, выведите слово “IMPOSSIBLE” без кавычек.

input output
59 14
1 3 5 8 12 28
5 7 8 2 12 58
18 13 25 42 2 43
13 1 68
12 20
18 20
35 242
4 10 20
31
71
8 100
10 1
12 10
10 IMPOSSIBLE
1
3
10 7
8 15

Комментарий:
В первом тесте:
Для первого запроса менеджер выберет 5-супермаркет. Водитель заплатит 2 единиц
денег за парковку, заплатит за 1 кг продуктов 12 единиц денег. Итого он заплатит 14
единиц денег. Модно доказать что это минимальное количество денег которое можно
использовать.
Для второго заказа менеджер выберет 1-супермаркет, потому что по пути водителя
нету других супермаркетов крому этого.
Для восьмого заказа менеджер выберет 4-супермаркет.
Во втором тесте:
Для второго заказа нельзя выбрать супермаркет по дороге.
8