Темы --> Информатика --> Структуры данных --> Деревья --> Дерево отрезков, RSQ, RMQ
---> 6 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников --> Заключительный этап
    2004(6 задач)
    2005(6 задач)
    2006(6 задач)
    2007(6 задач)
    2008(6 задач)
    2009(6 задач)
    2010(6 задач)
    2011(8 задач)
    2012(8 задач)
    2013(8 задач)
    2014(7 задач)
    2015(8 задач)
    2016(8 задач)
    2017(8 задач)
Страница: 1 2 >> Отображать по:
#1049
Горнолыжные соревнования
  
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
64 megabytes

Горнолыжник, готовясь к соревнованиям, нарисовал на бумаге схему горнолыжной трассы для выбора оптимального маршрута спуска. На схеме расположенные на трассе ворота представлены горизонтальными отрезками. Никакая пара ворот не имеет общих точек.

Маршрут должен представлять собой ломаную, начинающуюся в точке старта на вершине горы и заканчивающуюся в точке финиша у ее подножия. Маршрут выбирается таким образом, что y-координата каждой следующей вершины ломаной оказывается строго меньше y-координаты предыдущей вершины. Один из возможных маршрутов представлен на рисунке.

За каждые ворота, через которые не проходит маршрут, лыжнику начисляются штрафные очки. Общий штраф за спуск по маршруту вычисляется как сумма длины маршрута и штрафных очков за непройденные ворота.

Требуется написать программу, которая определяет, какой минимальный общий штраф горнолыжник может получить при прохождении трассы.

Входные данные

В первой строке входного файла задано число N - количество ворот на трассе (0 ≤ N ≤ 500), в следующих двух строках заданы Sx, Sy, Fx, Fy - координаты точек старта и финиша соответственно. В каждой из следующих N строк записаны четыре числа ai, bi, yi, ci - x-координаты левого и правого концов ворот, y-координата ворот и штраф за непрохождение данных ворот (ai < bi, Fy < yi < Sy, ci - целое число, 0 ≤ ci ≤ 10000). Все координаты - целые числа, не превосходящие по модулю 10000.

Выходные данные

В выходной файл выведите наименьший возможный общий штраф за прохождение трассы с точностью не менее 4 знаков после десятичной точки.

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

Потестовая.

Примеры
Входные данные
4
3 6
3 1
5 7 4 1
4 5 5 10
1 2 4 5
2 5 2 0
Выходные данные
7.8126
#2532
Ханты-Мансийск — Париж
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В 2050 году руководство Глобальной Телефонной Сети (ГТС) приняло решение о новой системе тарификации коротких текстовых сообщений. Теперь цена отправки одного сообщения зависит от количества совпадающих цифр в начале номеров телефонов отправителя и получателя. Если первые \(c\) цифр телефонов совпадают, а \((c+1)\)-я цифра различается, то стоимость сообщения составляет \((10-c)\) кредитов (\(0\le c\le9\)). Все номера телефонов — десятизначные. При этом ГТС разрешает каждому абоненту отправлять сообщение только в пределах часового пояса своего проживания или часовых поясов, отличающихся от него на 1 час.

Школьник Поликарп из Ханты-Мансийска (время +2 часа от московского) успешно решил все задания первого тура олимпиады школьников по информатике. Теперь он желает сообщить об этом в Париж (время −2 часа от московского) своему учителю — профессору де Коде́ру. Так как Ханты-Мансийск и Париж находятся не в соседних часовых поясах, Поликарп не может послать сообщение напрямую. Поэтому он пользуется тем, что у него есть друзья, которые проживают в Ханты-Мансийске, Париже, а также в промежуточных часовых поясах — в Дубае (время +1 час от московского), Москве и Калининграде (время −1 час от московского). Друзья Поликарпа по цепочке доставят профессору де Коде́ру столь важную информацию. Поликарп хочет организовать передачу информации таким образом, чтобы минимизировать суммарные расходы по отправке всех сообщений.

Напишите программу, определяющую цепочку доставки, для которой суммарная стоимость отправленных сообщений минимальна.

Входные данные

Первые две строки входного файла содержат телефонные номера Поликарпа и профессора де Коде́ра. Далее следуют 5 блоков данных, описывающих друзей Поликарпа, живущих в Ханты-Мансийске, Дубае, Москве, Калининграде и Париже, соответственно. Каждый блок начинается со строки, содержащей одно число \(n_i\) (\(1\le n_i\le100\,000\)) — количество друзей Поликарпа в соответствующем городе, после которой следуют \(n_i\) строк — номера телефонов друзей. Все номера телефонов состоят ровно из 10 цифр. Гарантируется, что сумма всех \(n_i\) не превосходит 100 000. Все номера телефонов во входных данных различны.

Выходные данные

В первой строке выходного файла выведите минимальную возможную стоимость передачи информации \(w\) и количество задействованных в цепочке телефонных номеров \(k\). Далее выведите \(k\) номеров телефонов, описывающих саму цепочку, в порядке следования от Поликарпа к профессору де Коде́ру. Первый номер в цепочке должен совпадать с номером телефона Поликарпа, а последний — с номером телефона профессора де Коде́ра. Если решений несколько, выведите любое.

Система оценивания

  • Решения, корректно работающие при сумме \(n_i\), не превосходящей 500, будут оцениваться из 40 баллов.
  • Решения, корректно работающие при сумме \(n_i\), не превосходящей 5 000, будут оцениваться из 60 баллов.

    • Примеры
    Входные данные
    2099013166
7043239909
1
0258442145
1
0000000000
1
0000000001
1
0000000002
1
0147571204
    Выходные данные
    22 5
2099013166
0000000000
0000000001
0000000002
7043239909
    Входные данные
    4261802325
7967612531
1
8176476745
1
3084033164
1
1737248630
1
9447552231
1
2848478213
    Выходные данные
    40 5
4261802325
3084033164
1737248630
9447552231
7967612531
    #111225
    Мозаика
      
    ограничение по времени на тест
    2.0 second;
    ограничение по памяти на тест
    256 megabytes

    Все элементы магнитной мозаики фирмы «ABBYY» имеют прямоугольную форму. Два элемента можно соединить только в том случае, если у них совпадает хотя бы один из размеров: длина, ширина, или и то, и другое. Магнитные элементы поворачивать и переворачивать нельзя. Пару элементов мозаики, которые нельзя соединить, назовем негармоничной. Например, пара 1 × 2 и 2 × 3 является негармоничной, а пары 2 × 3 и 1 × 3 или 2 × 3 и 2 × 3 являются гармоничными. Дизайнеры «ABBYY» выложили все элементы мозаики в ряд, не соединяя их между собой. Назовем набором несколько подряд лежащих элементов мозаики в этом ряду. Они выбрали несколько наборов элементов, которые хотят оставить для создания инсталляции. Для каждого такого набора им нужно выяснить, есть ли в нем негармоничная пара элементов. Требуется написать программу, которая для различных наборов подряд лежащих элементов мозаики определит номера элементов, образующих негармоничную пару, или сообщит, что такой пары нет.

    Входные данные

    В первой строке входного файла записано одно число N – количество элементов, из которых состоит мозаика (2 ≤ N ≤ 100 000). В следующих N строках записаны по два целых числа Ai и Bi , задающих длину и ширину i-го элемента мозаики соответственно (1 ≤ Ai, Bi ≤ 109, 1 ≤ i ≤ N). В (N + 2)-й строке записано одно целое число K – количество наборов, в каждом из которых нужно определить номера двух негармоничных элементов (1 ≤ K ≤ 100 000). В следующих K строках записаны пары целых чисел N1 и N2 – номера первого и последнего элементов набора соответственно, в котором необходимо найти два негармоничных элемента мозаики (1 ≤ \(N_1\) < \(N_2\) ≤ N).

    Выходные данные

    Выходной файл должен содержать K строк, каждая из которых содержит два разделённых пробелом числа – номера элементов мозаики, образующих негармоничную пару в соответствующем наборе. Если решений несколько, можно вывести любое из них. Если в наборе негармоничная пара отсутствует, требуется вывести в соответствующей строке 0 0.

    Примечание

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

    1. (оценивается в 20 баллов) Количество элементов мозаики N ≤ 100, число наборов K ≤ 100.

    2. (оценивается в 30 баллов) Количество элементов мозаики N ≤ 1000, число наборов K ≤ 1000.

    3. (оценивается в 20 баллов) Количество элементов мозаики N ≤ 5000, число наборов K ≤ 5000.

    4. (оценивается в 30 баллов) Количество элементов мозаики N ≤ 100 000, число наборов K ≤ 100 000.

    Примеры
    Входные данные
    4
2 2
1 2
1 3
2 3
2
2 3
2 4
    Выходные данные
    0 0
4 2
    #111636
    Древние династии
      

    История Татаро-монгольского ханства богата на правителей. Каждый из N правителей принадлежал к одной из двух династий, причём власть часто переходила от одной династии к другой. Каждое восхождение правителя на престол отмечалось праздником, проводимым 26 марта. В летописях зафиксированы годы проведения этих праздников, причем известно, что правители первой династии устраивали для народа праздник кумыса, а второй — праздник мёда.

    На конференции по истории Татаро-монгольского ханства каждый из S учёных предложил свою версию толкования летописи. А именно, i-й историк утверждал, что от каждого праздника кумыса до следующего праздника кумыса проходило не менее KLi лет, но не более KRi лет, в то время как от каждого праздника мёда до следующего праздника мёда проходило не менее MLi лет, но не более MRi лет.

    Каждой предложенной версии может соответствовать несколько распределений правителей по династиям. Ученые договорились считать показателем сомнительности распределения число переходов власти к представителю той же самой династии.

    Требуется написать программу, которая найдёт распределение, соответствующее хотя бы одной из версий и имеющее наименьший показатель сомнительности, а также версию, которой оно соответствует.

    Входные данные

    В первой строке входного файла записано число N (2 ≤ N ≤ 200 000) — количество праздников в летописи. Следующая строка содержит целые числа X1, X2, ..., XN (1 ≤ X1 ≤ X2 ≤ ... ≤ XN ≤ 109) — годы проведения праздников.

    В третьей строке записано число учёных S (1 ≤ S ≤ 50). В каждой из последующих S строк записаны четыре натуральных числа KLi, KRi, MLi, MRi (1 ≤ KLi ≤ KRi ≤ 109), (1 ≤ MLi ≤ MRi ≤ 109).

    Выходные данные

    Первая строка выходного файла должна содержать числа P и Q, где P — номер учёного, версии которого соответствует распределение с наименьшим показателем сомнительности, а Q — показатель сомнительности этого распределения.

    Вторая строка должна состоять из N цифр 1 и 2, записанных без пробелов, означающих приход к власти представителя первой или второй династии соответственно. Если существует несколько решений с наименьшим показателем сомнительности Q, выведите любое из них.

    В случае, если ни в одной из версий учёных не существует способа распределения периодов правления между династиями так, чтобы не нарушались ограничения на промежутки времени между праздниками, выходной файл должен содержать единственное число 0.

    Примечание

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

    1. Тесты из условия. Подзадача оценивается в 0 баллов.

    2. 2 ≤ N ≤ 15, 1 ≤ S ≤ 10. Подзадача оценивается в 20 баллов.

    3. 2 ≤ N ≤ 2000, 1 ≤ S ≤ 50, N × S ≤ 2000. Подзадача оценивается в 20 баллов.

    4. 2 ≤ N ≤ 10 000, 1 ≤ S ≤ 50, N × S ≤ 10 000. Подзадача оценивается в 20 баллов.

    5. 2 ≤ N ≤ 200 000, 1 ≤ S ≤ 50, N × S ≤ 200 000. Подзадача оценивается в 20 баллов.

    6. 2 ≤ N ≤ 200 000, 1 ≤ S ≤ 50. Подзадача оценивается в 20 баллов.

    Примеры
    Входные данные
    3
1 2 3
1
1 1 1 1
    Выходные данные
    1 1
211
    Входные данные
    4
1 6 9 13
2
1 2 2 3
6 7 3 3
    Выходные данные
    0
    Входные данные
    5
3 6 8 9 10
2
2 3 1 1
1 4 1 10
    Выходные данные
    2 0
21212
    #113545
    Иллюзия сортировки
      
    ограничение по времени на тест
    2.0 second;
    ограничение по памяти на тест
    512 megabytes

    Известный программист пробует себя в роли иллюзиониста. Его коронный фокус состоит в следующем.

    Для заданного массива из n целых неотрицательных чисел a1, a2, ..., an он быстро подбирает магическое число b. Целое неотрицательное число b называется магическим для массива, если применение операции побитового исключающего ИЛИ с этим числом к каждому элементу массива превращает его в отсортированный массив. Иначе говоря,

    \(\) (a_1\oplus b) \le (a_2\oplus b) \le ... \le (a_n\oplus b) \(\)

    где \(\oplus\) — операция побитового исключающего ИЛИ.

    Чтобы фокус был более эффектным, после предъявления магического числа для заданного массива иллюзионист q раз выполняет следующее действие. Он предлагает зрителям изменить один из элементов массива и после этого снова пытается предъявить магическое число. При этом программист настолько отточил свое мастерство иллюзиониста, что каждый раз предъявляет зрителям минимальное возможное магическое число. Иногда фокус не удаётся, так как для полученного массива невозможно подобрать магическое число.

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

    Примечание

    Исключающее ИЛИ — это логическая операция, обозначаемая знаком \(\oplus\), которая задаётся следующей таблицей истинности:

    Определим побитовое исключающее ИЛИ для двух неотрицательных целых чисел x и y. Запишем каждое из целых чисел x и y в двоичной системе счисления, дополнив при необходимости более короткое из чисел ведущими нулями до равной длины. Побитовое исключающее ИЛИ двух целых чисел \(x\) и \(y\), обозначаемое также как \(\oplus\), это целое неотрицательное число, каждый разряд которого в двоичной системе счисления является исключающим ИЛИ соответствующих разрядов чисел \(x\) и \(y\). Например, \(5\oplus22=101_2\oplus10110_2=10011_2=19\).

    Среди предложенных на олимпиаде языков программирования в языке Паскаль для обозначения исключающего ИЛИ используется оператор «xor», в остальных языках программирования используется оператор «^».

    Входные данные

    Первая строка входных данных содержит целое число n — количество чисел в массиве (1 ≤ n ≤ 106).

    Вторая строка содержит n целых чисел a1, a2, ..., an — элементы массива (0 ≤ ai < 230).

    Третья строка содержит целое число q — число изменений элемента массива (0 ≤ q ≤ 106).

    Следующие q строк содержат по два целых числа pi и vi, где pi — номер элемента массива, который следует заменить (1 ≤ pi ≤ n), а vi — новое значение этого элемента (0 ≤ vi < 230).

    Выходные данные

    Выходные данные должны содержать (q + 1) целых чисел b0, b1, ..., bq, по одному в строке.

    Значение b0 — либо минимальное возможное магическое число для исходного массива, либо  - 1, если такого числа не существует.

    Для i от 1 до q значение bi — либо минимальное возможное магическое число для массива после первых i изменений, либо  - 1, если такого числа не существует.

    Примеры
    Входные данные
    3
0 1 4
3
2 7
3 3
1 4
    Выходные данные
    0
2
-1
4
    Страница: 1 2 >> Отображать по:
    Выбрано
    :
    Отменить
    |
    Добавить в контест