Zharaskhan Aman


Задача №1. (Такси) В городе Алматы проживает преуспевающий бизнесмен по имени Елибай. С недавних пор он занимается строительством $N$ объектов . Он каждый день ездит на своем автомобиле с головного офиса в объекты, осматривает объекты и возвращается обратно в офис. Он обязательно должен возвращаться в офис между походами в объекты, так как он должен заполнить некоторые документы. Сегодня у него случилась беда, у машины разрядился аккумулятор. Чтобы не опоздать он обратился к двум сервиса для заказа такси ZhureBER и Zhett. Тарифы у них оказались недешевыми. За $d$ километров придется платить $d^2$ тенге. Однако его друг Айсултан - который владеет сервисом такси предложил ему купить $N$ промо-кодов для поездки на такси со стоимостью $X$, тогда ему придется платить за каждую поездку $X$ тенге если $X \ge d$, иначе $X + (d - X)^2$ тенге.
Елибай для осмотра объекта под номером $i$ заказывает такси из офиса в объект и обратно (суммарная дистанция из офиса в объект и обратно $d_i$). Он не может за одну поездку два раза пользоваться промо-кодом и для осмотра нового объекта каждый раз заказывает новый такси.
Так как Айсултан давний друг Елибая, он предложил ему самому выбрать число $X$, конечно же $X$ должно быть неотрицательным целым числом.
Формат входных данных:
Первая строка входного файла будет содержать одно число $N$ — количество объектов с которыми занимается бизнесмен.
Во второй строке записаны $N$ целых чисел $d_1, d_2, \ldots d_n$ расстояние от офиса до $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 \times 10 + {(9 - 6)}^2 + {(7 - 6)}^2 = 60 + 9 + 1 = 70 $
Если X = 5, общая стоимость была бы 71. Если X = 7, общая стоимость была бы 74.
Система оценки:
Задача содержит 50 тестов, каждая из которых весят 2 балла.
Ограничения которые присутствуют в тестах:
( Zharaskhan Aman )
комментарий/решение(5) олимпиада
Задача №2. (Такси) В городе Алматы проживает преуспевающий бизнесмен по имени Елибай. С недавних пор он занимается строительством $N$ объектов . Он каждый день ездит на своем автомобиле с головного офиса в объекты, осматривает объекты и возвращается обратно в офис. Он обязательно должен возвращаться в офис между походами в объекты, так как он должен заполнить некоторые документы. Сегодня у него случилась беда, у машины разрядился аккумулятор. Чтобы не опоздать он обратился к двум сервиса для заказа такси ZhureBER и Zhett. Тарифы у них оказались недешевыми. За $d$ километров придется платить $d^2$ тенге. Однако его друг Айсултан - который владеет сервисом такси предложил ему купить $N$ промо-кодов для поездки на такси со стоимостью $X$, тогда ему придется платить за каждую поездку $X$ тенге если $X \ge d$, иначе $X + (d - X)^2$ тенге.
Елибай для осмотра объекта под номером $i$ заказывает такси из офиса в объект и обратно (суммарная дистанция из офиса в объект и обратно $d_i$). Он не может за одну поездку два раза пользоваться промо-кодом и для осмотра нового объекта каждый раз заказывает новый такси.
Так как Айсултан давний друг Елибая, он предложил ему самому выбрать число $X$, конечно же $X$ должно быть неотрицательным целым числом.
Формат входных данных:
Первая строка входного файла будет содержать одно число $N$ — количество объектов с которыми занимается бизнесмен.
Во второй строке записаны $N$ целых чисел $d_1, d_2, \ldots d_n$ расстояние от офиса до $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 \times 10 + {(9 - 6)}^2 + {(7 - 6)}^2 = 60 + 9 + 1 = 70 $
Если X = 5, общая стоимость была бы 71. Если X = 7, общая стоимость была бы 74.
Система оценки:
Задача содержит 50 тестов, каждая из которых весят 2 балла.
Ограничения которые присутствуют в тестах:
( Zharaskhan Aman )
комментарий/решение(5) олимпиада
Задача №3. (Такси) В городе Алматы проживает преуспевающий бизнесмен по имени Елибай. С недавних пор он занимается строительством $N$ объектов . Он каждый день ездит на своем автомобиле с головного офиса в объекты, осматривает объекты и возвращается обратно в офис. Он обязательно должен возвращаться в офис между походами в объекты, так как он должен заполнить некоторые документы. Сегодня у него случилась беда, у машины разрядился аккумулятор. Чтобы не опоздать он обратился к двум сервиса для заказа такси ZhureBER и Zhett. Тарифы у них оказались недешевыми. За $d$ километров придется платить $d^2$ тенге. Однако его друг Айсултан - который владеет сервисом такси предложил ему купить $N$ промо-кодов для поездки на такси со стоимостью $X$, тогда ему придется платить за каждую поездку $X$ тенге если $X \ge d$, иначе $X + (d - X)^2$ тенге.
Елибай для осмотра объекта под номером $i$ заказывает такси из офиса в объект и обратно (суммарная дистанция из офиса в объект и обратно $d_i$). Он не может за одну поездку два раза пользоваться промо-кодом и для осмотра нового объекта каждый раз заказывает новый такси.
Так как Айсултан давний друг Елибая, он предложил ему самому выбрать число $X$, конечно же $X$ должно быть неотрицательным целым числом.
Формат входных данных:
Первая строка входного файла будет содержать одно число $N$ — количество объектов с которыми занимается бизнесмен.
Во второй строке записаны $N$ целых чисел $d_1, d_2, \ldots d_n$ расстояние от офиса до $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 \times 10 + {(9 - 6)}^2 + {(7 - 6)}^2 = 60 + 9 + 1 = 70 $
Если X = 5, общая стоимость была бы 71. Если X = 7, общая стоимость была бы 74.
Система оценки:
Задача содержит 50 тестов, каждая из которых весят 2 балла.
Ограничения которые присутствуют в тестах:
( Zharaskhan Aman )
комментарий/решение олимпиада
Задача №4. 

Задача E. НурлашКО

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

АланашКО и НурлашКО играют с графом, и им нужна Ваша помощь. Игра начинается с ориентированного ациклического графа $G$, состоящий из $n$ вершин, без ребер, во время игры игроки выполняют $q$ операций. Операции бывают следующих типов:
  1. Добавить ориентированное ребро из вершины $u_i$ в вершину $v_i$.
  2. Вывести $x_i$, если существует ориентированный путь из вершины 1 в вершину $x_i$, иначе $0$.
Гарантируется, после операции граф останется ациклическим. Ациклический граф - случай ориентированного графа, в котором отсутствуют ориентированные циклы.
Формат входного файла
Первая строка входных данных содержит три целых числа $n$, $q$ и $t$ $(1 <= n, q <= 10^6, 0 <= t <= 1)$ — количество вершин, количество операций и константное число. Каждая из следующих $q$ строк содержит описание одного запроса.
  1. Запросы первого типа заданы в формате: $1$ $a_i$ $b_i$ $(0 <= a_i, b_i <= 2\cdot10^9)$.
  2. Запросы второго типа заданы в формате: $2$ $a_i$ $(0 <= a_i <= 2\cdot10^9)$.
Обратите внимание, что вершины $u_i$, $v_i$ для запросов типа $1$ и вершина $x_i$ для запросов типа $2$ закодированы, и чтобы их получить нужно выполнить соответствующие преобразования: {
$u_i = (a_i \oplus (t*lastans)) \mod n + 1, \quad v_i = (b_i \oplus (t*lastans)) \mod n + 1$

$x_i = (a_i \oplus (t*lastans)) \mod n + 1$

} где $lastans$ — последний ответ на запрос типа $2$ (изначально $lastans$ равен $0$). Здесь $\oplus$ обозначает операцию побитового XOR или исключающего ИЛИ. Данная операция существует во всех современных языках программирования, например, в языках C++ и Java она обозначена как ^, в Pascal — как $xor$. Операция $a \mod b$ означает взятие остатка от деления $a$ на $b$. Гарантируется, что во входных данных присутствует хотя бы один запрос типа $2$.
Формат выходного файла
Для каждого запроса второго типа выведите ответ в отдельной строке.
Система оценки
Данная задача содержит 5 подзадач, в каждой подзадаче выполняются ограничения из условий:
  1. Тесты из условий. Оценивается в $0$ баллов.
  2. $n, q <= 10^3$, $u_i = 1$, $t = 0$. Оценивается в $11$ баллов.
  3. $n, q <= 10^3$. Оценивается в $18$ баллов.
  4. $t = 0$. Оценивается в $39$ баллов.
  5. Ограничения из условия. Оценивается в $32$ баллов.
Примеры:
Вход 
5 9 0
2 0
2 1
1 0 1
2 1
1 2 3
1 2 3
2 3
1 1 2
2 3
Ответ
1
0
2
0
4
Вход 
5 9 1
2 0
2 0
1 0 1
2 1
1 0 1
1 0 1
2 1
1 1 2
2 3
Ответ
1
0
2
0
4
( Zharaskhan Aman )
комментарий/решение(4) олимпиада
Задача №5. 

Задача E. НурлашКО

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

АланашКО и НурлашКО играют с графом, и им нужна Ваша помощь. Игра начинается с ориентированного ациклического графа $G$, состоящий из $n$ вершин, без ребер, во время игры игроки выполняют $q$ операций. Операции бывают следующих типов:
  1. Добавить ориентированное ребро из вершины $u_i$ в вершину $v_i$.
  2. Вывести $x_i$, если существует ориентированный путь из вершины 1 в вершину $x_i$, иначе $0$.
Гарантируется, после операции граф останется ациклическим. Ациклический граф - случай ориентированного графа, в котором отсутствуют ориентированные циклы.
Формат входного файла
Первая строка входных данных содержит три целых числа $n$, $q$ и $t$ $(1 <= n, q <= 10^6, 0 <= t <= 1)$ — количество вершин, количество операций и константное число. Каждая из следующих $q$ строк содержит описание одного запроса.
  1. Запросы первого типа заданы в формате: $1$ $a_i$ $b_i$ $(0 <= a_i, b_i <= 2\cdot10^9)$.
  2. Запросы второго типа заданы в формате: $2$ $a_i$ $(0 <= a_i <= 2\cdot10^9)$.
Обратите внимание, что вершины $u_i$, $v_i$ для запросов типа $1$ и вершина $x_i$ для запросов типа $2$ закодированы, и чтобы их получить нужно выполнить соответствующие преобразования: {
$u_i = (a_i \oplus (t*lastans)) \mod n + 1, \quad v_i = (b_i \oplus (t*lastans)) \mod n + 1$

$x_i = (a_i \oplus (t*lastans)) \mod n + 1$

} где $lastans$ — последний ответ на запрос типа $2$ (изначально $lastans$ равен $0$). Здесь $\oplus$ обозначает операцию побитового XOR или исключающего ИЛИ. Данная операция существует во всех современных языках программирования, например, в языках C++ и Java она обозначена как ^, в Pascal — как $xor$. Операция $a \mod b$ означает взятие остатка от деления $a$ на $b$. Гарантируется, что во входных данных присутствует хотя бы один запрос типа $2$.
Формат выходного файла
Для каждого запроса второго типа выведите ответ в отдельной строке.
Система оценки
Данная задача содержит 5 подзадач, в каждой подзадаче выполняются ограничения из условий:
  1. Тесты из условий. Оценивается в $0$ баллов.
  2. $n, q <= 10^3$, $u_i = 1$, $t = 0$. Оценивается в $11$ баллов.
  3. $n, q <= 10^3$. Оценивается в $18$ баллов.
  4. $t = 0$. Оценивается в $39$ баллов.
  5. Ограничения из условия. Оценивается в $32$ баллов.
Примеры:
Вход 
5 9 0
2 0
2 1
1 0 1
2 1
1 2 3
1 2 3
2 3
1 1 2
2 3
Ответ
1
0
2
0
4
Вход 
5 9 1
2 0
2 0
1 0 1
2 1
1 0 1
1 0 1
2 1
1 1 2
2 3
Ответ
1
0
2
0
4
( Zharaskhan Aman )
комментарий/решение(4) олимпиада