Zharaskhan Aman
Задача №1. (Такси) В городе Алматы проживает преуспевающий бизнесмен по имени Елибай. С недавних пор он занимается строительством N объектов . Он каждый день ездит на своем автомобиле с головного офиса в объекты, осматривает объекты и возвращается обратно в офис. Он обязательно должен возвращаться в офис между походами в объекты, так как он должен заполнить некоторые документы. Сегодня у него случилась беда, у машины разрядился аккумулятор. Чтобы не опоздать он обратился к двум сервиса для заказа такси ZhureBER и Zhett. Тарифы у них оказались недешевыми. За d километров придется платить d2 тенге. Однако его друг Айсултан - который владеет сервисом такси предложил ему купить N промо-кодов для поездки на такси со стоимостью X, тогда ему придется платить за каждую поездку X тенге если X≥d, иначе X+(d−X)2 тенге.
Елибай для осмотра объекта под номером i заказывает такси из офиса в объект и обратно (суммарная дистанция из офиса в объект и обратно di). Он не может за одну поездку два раза пользоваться промо-кодом и для осмотра нового объекта каждый раз заказывает новый такси.
Так как Айсултан давний друг Елибая, он предложил ему самому выбрать число X, конечно же X должно быть неотрицательным целым числом.
Формат входных данных:
Первая строка входного файла будет содержать одно число N — количество объектов с которыми занимается бизнесмен.Во второй строке записаны N целых чисел d1,d2,…dn расстояние от офиса до i-го объекта и обратно.
Формат выходных данных:
Выведите одно целое число - минимальную суммарную количество денег Елибай должен заплатить если выберет число X оптимально.Примеры:
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.
Суммарно 6×10+(9−6)2+(7−6)2=60+9+1=70
Если X = 5, общая стоимость была бы 71. Если X = 7, общая стоимость была бы 74.
Система оценки:
Задача содержит 50 тестов, каждая из которых весят 2 балла.Ограничения которые присутствуют в тестах:
- 4 теста: 1≤N≤2000, 0≤di≤1000. В добавок, расстояние до всех объектов одинаково. (di=d1 для i>1)
- 11 тестов: 1≤N≤2000, 0≤di≤1000
- 11 тестов: 1≤N≤2000, 0≤di≤106.
- 24 тестов: 1≤N≤200000, 0≤di≤106.
комментарий/решение(5) олимпиада
Задача №2. (Такси) В городе Алматы проживает преуспевающий бизнесмен по имени Елибай. С недавних пор он занимается строительством N объектов . Он каждый день ездит на своем автомобиле с головного офиса в объекты, осматривает объекты и возвращается обратно в офис. Он обязательно должен возвращаться в офис между походами в объекты, так как он должен заполнить некоторые документы. Сегодня у него случилась беда, у машины разрядился аккумулятор. Чтобы не опоздать он обратился к двум сервиса для заказа такси ZhureBER и Zhett. Тарифы у них оказались недешевыми. За d километров придется платить d2 тенге. Однако его друг Айсултан - который владеет сервисом такси предложил ему купить N промо-кодов для поездки на такси со стоимостью X, тогда ему придется платить за каждую поездку X тенге если X≥d, иначе X+(d−X)2 тенге.
Елибай для осмотра объекта под номером i заказывает такси из офиса в объект и обратно (суммарная дистанция из офиса в объект и обратно di). Он не может за одну поездку два раза пользоваться промо-кодом и для осмотра нового объекта каждый раз заказывает новый такси.
Так как Айсултан давний друг Елибая, он предложил ему самому выбрать число X, конечно же X должно быть неотрицательным целым числом.
Формат входных данных:
Первая строка входного файла будет содержать одно число N — количество объектов с которыми занимается бизнесмен.Во второй строке записаны N целых чисел d1,d2,…dn расстояние от офиса до i-го объекта и обратно.
Формат выходных данных:
Выведите одно целое число - минимальную суммарную количество денег Елибай должен заплатить если выберет число X оптимально.Примеры:
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.
Суммарно 6×10+(9−6)2+(7−6)2=60+9+1=70
Если X = 5, общая стоимость была бы 71. Если X = 7, общая стоимость была бы 74.
Система оценки:
Задача содержит 50 тестов, каждая из которых весят 2 балла.Ограничения которые присутствуют в тестах:
- 4 теста: 1≤N≤2000, 0≤di≤1000. В добавок, расстояние до всех объектов одинаково. (di=d1 для i>1)
- 11 тестов: 1≤N≤2000, 0≤di≤1000
- 11 тестов: 1≤N≤2000, 0≤di≤106.
- 24 тестов: 1≤N≤200000, 0≤di≤106.
комментарий/решение(5) олимпиада
Задача №3. (Такси) В городе Алматы проживает преуспевающий бизнесмен по имени Елибай. С недавних пор он занимается строительством N объектов . Он каждый день ездит на своем автомобиле с головного офиса в объекты, осматривает объекты и возвращается обратно в офис. Он обязательно должен возвращаться в офис между походами в объекты, так как он должен заполнить некоторые документы. Сегодня у него случилась беда, у машины разрядился аккумулятор. Чтобы не опоздать он обратился к двум сервиса для заказа такси ZhureBER и Zhett. Тарифы у них оказались недешевыми. За d километров придется платить d2 тенге. Однако его друг Айсултан - который владеет сервисом такси предложил ему купить N промо-кодов для поездки на такси со стоимостью X, тогда ему придется платить за каждую поездку X тенге если X≥d, иначе X+(d−X)2 тенге.
Елибай для осмотра объекта под номером i заказывает такси из офиса в объект и обратно (суммарная дистанция из офиса в объект и обратно di). Он не может за одну поездку два раза пользоваться промо-кодом и для осмотра нового объекта каждый раз заказывает новый такси.
Так как Айсултан давний друг Елибая, он предложил ему самому выбрать число X, конечно же X должно быть неотрицательным целым числом.
Формат входных данных:
Первая строка входного файла будет содержать одно число N — количество объектов с которыми занимается бизнесмен.Во второй строке записаны N целых чисел d1,d2,…dn расстояние от офиса до i-го объекта и обратно.
Формат выходных данных:
Выведите одно целое число - минимальную суммарную количество денег Елибай должен заплатить если выберет число X оптимально.Примеры:
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.
Суммарно 6×10+(9−6)2+(7−6)2=60+9+1=70
Если X = 5, общая стоимость была бы 71. Если X = 7, общая стоимость была бы 74.
Система оценки:
Задача содержит 50 тестов, каждая из которых весят 2 балла.Ограничения которые присутствуют в тестах:
- 4 теста: 1≤N≤2000, 0≤di≤1000. В добавок, расстояние до всех объектов одинаково. (di=d1 для i>1)
- 11 тестов: 1≤N≤2000, 0≤di≤1000
- 11 тестов: 1≤N≤2000, 0≤di≤106.
- 24 тестов: 1≤N≤200000, 0≤di≤106.
комментарий/решение олимпиада
Задача №4.
Задача E. НурлашКО
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
АланашКО и НурлашКО играют с графом, и им нужна Ваша помощь. Игра начинается с ориентированного ациклического графа G, состоящий из n вершин, без ребер, во время игры игроки выполняют q операций. Операции бывают следующих типов:
- Добавить ориентированное ребро из вершины ui в вершину vi.
- Вывести xi, если существует ориентированный путь из вершины 1 в вершину xi, иначе 0.
Формат входного файла
Первая строка входных данных содержит три целых числа n, q и t (1<=n,q<=106,0<=t<=1) — количество вершин, количество операций и константное число. Каждая из следующих q строк содержит описание одного запроса.
- Запросы первого типа заданы в формате: 1 ai bi (0<=ai,bi<=2⋅109).
- Запросы второго типа заданы в формате: 2 ai (0<=ai<=2⋅109).
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 подзадач, в каждой подзадаче выполняются ограничения из условий:
- Тесты из условий. Оценивается в 0 баллов.
- n, q <= 10^3, u_i = 1, t = 0. Оценивается в 11 баллов.
- n, q <= 10^3. Оценивается в 18 баллов.
- t = 0. Оценивается в 39 баллов.
- Ограничения из условия. Оценивается в 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 операций. Операции бывают следующих типов:
- Добавить ориентированное ребро из вершины u_i в вершину v_i.
- Вывести x_i, если существует ориентированный путь из вершины 1 в вершину x_i, иначе 0.
Формат входного файла
Первая строка входных данных содержит три целых числа n, q и t (1 <= n, q <= 10^6, 0 <= t <= 1) — количество вершин, количество операций и константное число. Каждая из следующих q строк содержит описание одного запроса.
- Запросы первого типа заданы в формате: 1 a_i b_i (0 <= a_i, b_i <= 2\cdot10^9).
- Запросы второго типа заданы в формате: 2 a_i (0 <= a_i <= 2\cdot10^9).
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 подзадач, в каждой подзадаче выполняются ограничения из условий:
- Тесты из условий. Оценивается в 0 баллов.
- n, q <= 10^3, u_i = 1, t = 0. Оценивается в 11 баллов.
- n, q <= 10^3. Оценивается в 18 баллов.
- t = 0. Оценивается в 39 баллов.
- Ограничения из условия. Оценивается в 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) олимпиада