Школа программиста
Резервная копия - VPS Hoster 

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Положение] [Расписание] [Архив] [Содержание] [Задачи] [Рейтинг]

Задачи олимпиады "59 Краевая Всероссийская олимпиада школьников Красноярского края по информатике"

Задача A. Улучшение успеваемости

(Время: 1 сек. Память: 16 Мб Баллы: 100)

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

Примеры округления оценок приведены в таблице.

Оценки на урокахСреднее арифметическоеИтоговая оценка
2, 3, 5
2 + 3 + 5 = 31


33
3
3, 3, 4, 4
3 + 3 + 4 + 4 = 31


42
4
5, 5, 5, 3, 5
5 + 5 + 5 + 3 + 5 = 43


55
5

Все ученики лицея стремятся получить итоговую оценку по информатике не ниже 4 баллов. К сожалению, один из учеников получил на уроках a двоек, b троек и c четверок. Теперь он планирует получить несколько пятерок, причем хочет, чтобы итоговая оценка была не меньше 4 баллов. Ему надо понять, какое минимальное количество пятерок ему необходимо получить, чтобы добиться своей цели.

Требуется написать программу, которая по заданным целым неотрицательные числам a, b и c определяет минимальное количество пятерок, которое необходимо получить ученику, чтобы его итоговая оценка по информатике была не меньше 4 баллов.

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

Входной файл INPUT.TXT содержит три строки. Первая строка содержит целое неотрицательное число a, вторая строка содержит целое неотрицательное число b, третья строка содержит целое неотрицательное число c (0 ≤ a, b, c ≤ 1015, a + b + c ≥ 1).

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

В выходной файл OUTPUT.TXT выведите одно число: минимальное число пятерок, которое необходимо получить ученику, чтобы итоговая оценка была не меньше 4 баллов.

Пример

INPUT.TXTOUTPUT.TXT
12
0
0
2

Задача B. Квадраты и кубы

(Время: 2 сек. Память: 16 Мб Баллы: 100)

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

Пусть задано целое неотрицательное число k. Рассмотрим множество натуральных чисел от a до b, включительно. Будем называть k-плотностью этого множества количество пар натуральных чисел x и y, таких, что a ≤ x2 ≤ b, a ≤ y3 ≤ b, причем |x2 – y3| ≤ k.

Например, 2-плотность множества натуральных чисел от 1 до 30 равна 3, так как подходят следующие пары:

  • x = 1, y = 1, |x2 – y3| = |1 – 1| = 0;
  • x = 3, y = 2, |x2 – y3| = |9 – 8| = 1;
  • x = 5, y = 3, |x2 – y3| = |25 – 27| = 2.

Требуется написать программу, которая по заданным натуральным числам a и b, а также целому неотрицательному числу k, определяет k-плотность множества натуральных чисел от a до b, включительно.

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

Входной файл INPUT.TXT содержит три строки. Первая строка содержит натуральное число a, вторая строка содержит натуральное число b, третья строка содержит целое неотрицательное число k (1 ≤ a ≤ b ≤ 1018, 0 ≤ k ≤ 1018).

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

В выходной файл OUTPUT.TXT выведите одно целое число: искомую k-плотность множества натуральных чисел от a до b, включительно.

Пример

INPUT.TXTOUTPUT.TXT
11
30
2
3

Задача C. Лифт

(Время: 3 сек. Память: 16 Мб Баллы: 101)

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

В здании m этажей, пронумерованных от 1 до m снизу-вверх. Известно, что i-й сотрудник подходит к лифту в секунду ti на этаже ai, чтобы спуститься на первый этаж.

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

В каждый момент времени не более одного вызова является активным.

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

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

При движении вниз лифт останавливается на тех этажах, в которых был сделан вызов на момент проезда лифта мимо этого этажа. Все ожидающие лифт сотрудники заходят в него и вызов на этом этаже сбрасывается. Когда лифт завершает движение на первом этаже, все люди выходят из лифта, а лифт ожидает следующего вызова.

Если в момент, когда лифт освободился, есть хотя бы один необслуженный вызов, активируется вызов, который поступил раньше других. Если несколько вызовов поступило одновременно, активируется вызов от сотрудника с меньшим номером. Лифт продолжает обслуживание описанным образом, пока все n сотрудников не окажутся на первом этаже.

Будем считать, что люди входят и выходят из лифта мгновенно. Каждую секунду сначала люди подходят и вызывают лифт, а затем выполняются соответствующие действия (лифт перемещается на соседний этаж, в него входят или из него выходят люди, принимается решение, на какой вызов лифт должен отреагировать).

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

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

Первая строка входного файла INPUT.TXT содержит целые числа n и m – количество людей, вызывающих лифт, и количество этажей в здании (1 ≤ n ≤ 105, 2 ≤ m ≤ 109).

Следующие n строк описывают сотрудников, i-я из этих строк содержит два целых числа ti и ai – секунду, в которую i-й сотрудник подходит к лифту, и номер этажа, на котором это происходит (1 ≤ t1 ≤ t2 ≤ … ≤ tn ≤ 109, 2 ≤ ai ≤ m)

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

В выходной файл OUTPUT.TXT выведите n целых чисел: для каждого сотрудника требуется вывести секунду, в которую он выйдет из лифта на первом этаже.

Пример

INPUT.TXTOUTPUT.TXT
15 4
2 3
2 4
5 2
5 3
9 3
6
12
6
12
12

Пояснение к примеру

Пример работы лифта по шагам:

Время
1 этаж
2 этаж
3 этаж
4 этаж
0
[]
1
[]
2
[]↑3
1
2
3
[]↑3
1
2
4
[]←☺1
2
5
[☺1] ←☺3
4
2
6
[☺1→, ☺3→]↑4
4
2
7
[]↑4
4
2
8
[]↑44
2
9
45
[]←☺2
10
[☺2]←☺45
11
[☺2, ☺4, ☺5]
12
[☺2→, ☺4→, ☺5→]

Используемые обозначения:

Обозначение

Пояснение
[]
обозначение лифта
[]↑j
лифт движется на активный вызов, сделанный на j-м этаже
i
i-й сотрудник ждет лифта
←☺i
i-й сотрудник заходит в лифт
[☺i]
i-й сотрудник находится в лифте
[☺i→]
i-й сотрудник выходит из лифта

Задача D. Мониторинг труб

(Время: 5 сек. Память: 256 Мб Баллы: 100)

Газораспределительная система одного региона устроена следующим образом. Она содержит n узлов, пронумерованных от 1 до n, некоторые узлы соединены односторонними трубами. Узел с номером 1 соответствует центральному газохранилищу.

Система узлов описывается числами от p2, p3, …, pn. Для всех i от 2 до n узел с номером pi соединен односторонней трубой с узлом i, газ по этой трубе передается от узла pi к узлу i. Известно, что возможно доставить газ по трубам от центрального газохранилища до любого узла системы (возможно, с использованием промежуточных узлов). В системе используются трубы различных типов, тип трубы обозначается буквой английского алфавита от «a» до «z». Труба, соединяющая узел pi с узлом i, имеет тип ci.

Для проверки качества труб используется специальный робот. Он помещается в систему труб в одном из узлов и перемещается по трубам, каждый раз проверяя трубу, по которой он перемещается. Робот может перемещаться по трубам только в том же направлении, в котором по трубе передается газ. Совершив одно или несколько перемещений по трубам между узлами, робот извлекается из системы труб.

Каждый запуск робота должен соответствовать одной из m заданных спецификаций, пронумерованных от 1 до m. Спецификация с номером t представляет собой строку st, состоящую из строчных букв английского алфавита. Запуск соответствует спецификации st, если количество перемещений робота по трубам во время запуска совпадает с длиной st, и для всех j от 1 до длины st на j-м шаге робот перемещается по трубе, тип которой совпадает с st[j] —символом на позиции j в спецификации.

Если запуск робота соответствует спецификации с номером t, то стоимость этого запуска составляет wt. Оператору системы необходимо проверить все трубы, для этого можно запускать робот несколько раз. Каждый раз выбирается спецификация и маршрут робота по трубам, соответствующие выбранной спецификации. Необходимо проверить все трубы так, чтобы суммарная стоимость запусков робота для проверки качества труб была минимальна. Одну и ту же трубу можно проверять несколько раз.

Требуется написать программу, которая по описанию системы труб и списку спецификаций определяет минимальную суммарную стоимость запусков робота, в результате которых все трубы будут проверены, а также список необходимых для этого запусков (по требованию).

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

В первой строке входного файла INPUT.TXT находятся три целых числа n, m и t — количество узлов системы труб, количество спецификаций запусков робота и параметр, указывающий, требуется ли вывести список запусков робота или только их минимальную суммарную стоимость (1 ≤ n ≤ 500, 1 ≤ m ≤ 105, t равно 0 или 1).

В последующих (n – 1) строках содержится информация о трубах, (i – 1)-я из этих строк содержит разделенные пробелом значения pi и ci, где pi — целое число, задающее номер узла, из которого ведет труба в i-й узел, а ci — строчная буква английского алфавита, задающая тип этой трубы (1 ≤ pi ≤ i – 1).

В последующих m строках содержится информация о спецификациях, i-я из этих строк содержит разделенные пробелом целое число wi — стоимость запуска робота в соответствии с этой спецификацией, и состоящую из строчных букв английского алфавита строку si — саму спецификацию (1 ≤ wi ≤ 109). Суммарная длина строк si не превышает 106.

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

Первая строка выходного файла OUTPUT.TXT должна содержать одно число – минимальную суммарную стоимость запусков робота, в результате которых все трубы будут проверены. Если проверить все трубы невозможно, требуется вывести «–1».

Если t = 0, то больше ничего выводить не требуется.

Если t = 1 и проверить трубы возможно, то далее следует вывести список описаний запусков робота. В этом случае вторая строка выходных данных должна содержать число k – количество запусков робота, которое необходимо выполнить для проверки труб. В следующих k строках необходимо вывести по три целых числа ai, bi и ci – номер узла, в котором начинается запуск, номер узла, в котором заканчивается запуск, и номер спецификации, которой соответствует запуск.

Если оптимальных способов проверки несколько, требуется вывести любой из них.

Примеры

INPUT.TXTOUTPUT.TXT
13 3 0
1 a
2 b
3 a
4 b
2 a
6
27 3 1
1 a
2 a
3 b
3 b
1 b
6 b
3 aab
5 b
2 ab
15
4
1 4 1
2 5 3
1 6 2
6 7 2

Пояснение к примеру №2

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

Необходимо обратить внимание на следующие моменты:

  • трубу можно проверять несколько раз, так в приведенном примере дважды проверена труба из узла 2 в узел 3;
  • одну и ту же спецификацию разрешается использовать несколько раз, в приведенном примере вторая спецификация используется дважды, для проверки труб из узла 1 в узел 6 и из узла 6 в узел 7;
  • робот может перемещаться по трубам только в том же направлении, по которому по трубе передается газ, спецификацию «ab» нельзя использовать для проверки труб по маршруту 2→1→6, так как робот не может переместиться из узла 2 в узел 1.

Задача E. Удаление чисел

(Время: 1 сек. Память: 16 Мб Баллы: 100)

В ряд выписаны натуральные числа от 1 до n и задано натуральное число k.

Выполняется один или несколько шагов по удалению чисел в этом ряду. На очередном шаге оставшиеся числа просматриваются в возрастающем порядке, и каждое k-е число удаляется. Если после очередного шага осталось меньше k чисел, то процесс удаления чисел завершается.

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

Например, пусть n = 13, k = 2.

  • На первом шаге будут удалены числа 2, 4, 6, 8, 10 и 12, останутся числа 1, 3, 5, 7, 9, 11 и 13.
  • На втором шаге будут удалены числа 3, 7 и 11, останутся числа 1, 5, 9 и 13.
  • На третьем шаге будут удалены числа 5 и 13, останутся числа 1 и 9.
  • На четвертом шаге будет удалено число 9, останется число 1. Поскольку осталось одно число, процесс завершается.

Таким образом, число 13 будет удалено на третьем шаге.

Требуется написать программу, которая по заданным числам n и k определяет, на каком шаге будет удалено число n.

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

Первая строка входного файла INPUT.TXT содержит целое число n (3 ≤ n ≤ 1018). Во второй строке записано целое число k (2 ≤ k ≤ 100, k < n).

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

В выходной файл OUTPUT.TXT выведите одно целое число – номер шага, на котором будет удалено число n, или число 0, если число n не будет удалено.

Пример

INPUT.TXTOUTPUT.TXT
113
2
3

Задача F. Старая книга

(Время: 2 сек. Память: 16 Мб Баллы: 100)

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

Книга содержит несколько страниц, каждая страница содержит либо текст, либо иллюстрацию. Первые k страниц книги точно содержат иллюстрации. Все страницы книги пронумерованы, но номер страницы написан только на страницах, содержащих текст. Сумма номеров страниц с текстом равна s.

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

Например, если k = 1, а s = 8, то страницы книги могли иметь следующее содержание (буквой «Т» обозначена страница, содержащая текст, а буквой «И» — страница, содержащая иллюстрацию):

  • И Т И И И Т, пронумерованы страницы 2 и 6, 4 иллюстрации;
  • И И Т И Т, пронумерованы страницы 3 и 5, 3 иллюстрации;
  • И И И И И И И Т, пронумерована страница 8, 7 иллюстраций.

Минимальное количество иллюстраций равно 3.

Требуется написать программу, которая по заданным целым числам k и s определяет минимальное количество иллюстраций, которое могло быть в книге.

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

Первая строка входного файла INPUT.TXT содержит целое число k (0 ≤ k ≤ 109). Вторая строка содержит целое число s (k + 1 ≤ s ≤ 1012).

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

В выходной файл OUTPUT.TXT выведите одно целое число – минимальное количество иллюстраций в книге.

Пример

INPUT.TXTOUTPUT.TXT
11
8
3

Задача G. Красота фейерверка

(Время: 1 сек. Память: 32 Мб Баллы: 100)

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

Корневое дерево содержит одну или несколько вершин. Одна из вершин выделена и называется корнем дерева, для каждой из остальных вершин ровно одна другая вершина является родителем. При этом от любой вершины можно добраться до корня, последовательно переходя от вершины к ее родителю. Вершина, которая не является родителем никакой другой вершины, называется листом. Если вершина x является родителем вершины y, то вершина y является ребенком вершины x. Будем говорить, что вершина и ее родитель соединены ребром.

На рис. 1 показан пример корневого дерева с корнем в вершине 1. Родителем вершин 2 и 3 является вершина 1, родителем вершины 4 является вершина 2. Вершины 2 и 3 — дети вершины 1, а вершина 4 — ребенок вершины 2. Листьями являются вершины 3 и 4.

Рис. 1. Пример корневого дерева с корнем в вершине 1, листьями 3 и 4.

Фейерверк задается своим базовым деревом T и мощностью m. Фейерверк представляется деревом, которое получается в результате возведения дерева T в степень m. Операция возведения дерева в степень устроена следующим образом. Если m = 1, то результат T1 — само дерево T. Для m > 1 рассмотрим дерево Tm – 1. Выполним следующую операцию: для каждого листа x дерева Tm – 1 создадим копию дерева T и назначим лист x родителем корня соответствующей копии. Получившееся дерево будет деревом Tm.

На рис. 2 показано дерево, представленное на рис. 1, в степенях 1, 2 и 3.

Рис. 2. Пример возведения дерева в степени 1, 2 и 3.

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

Для того, чтобы оценить красоту фейерверка, необходимо определить, какое максимальное количество вершин может содержать путь в дереве, которым представляется фейерверк. На рис. 3 приведен путь в дереве T2, содержащий максимальное количество вершин. Таким образом, красота фейерверка с базовым деревом T и мощностью 2 равна 10.

Рис. 3. Путь в дереве T2, содержащий максимальное количество вершин.

Требуется написать программу, которая по описанию дерева T и натуральному числу m определяет красоту фейерверка с базовым деревом T и мощностью m.

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

Первая строка входного файла INPUT.TXT содержит два натуральных числа n и m – количество вершин в базовом дереве фейерверка T и его мощность (3 ≤ n ≤ 200 000, 1 ≤ m ≤ 200 000).

Вторая строка описывает дерево T и содержит (n – 1) целых чисел: p2, p3, …, pn – номера родителей вершин 2, 3, …, n, соответственно (1 ≤ pi ≤ i – 1).

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

В выходной файл OUTPUT.TXT выведите одно целое число – красоту фейерверка, представляемого деревом Tm.

Пример

INPUT.TXTOUTPUT.TXT
14 2
1 1 2
10

Задача H. Обработка больших данных

(Время: 8 сек. Память: 128 Мб Баллы: 100)

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

Суперкомпьютер имеет 2k ячеек памяти, пронумерованных от 0 до 2k – 1. Отрезком [L, R] называется последовательность подряд идущих ячеек памяти с номерами от L до R, включительно.

Некоторые отрезки памяти являются корректными. Отрезок памяти [L, R] является корректным, если его длина (R – L + 1) равна 2i для некоторого i, а число L делится на 2i. Например, если k = 3, то ячейки памяти пронумерованы от 0 до 7, а корректными являются отрезки [0, 7], [0, 3], [4, 7], [0, 1], [2, 3], [4, 5], [6, 7], [0, 0], [1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6, 6] и [7, 7].

Ключевой операцией в новой архитектуре является операция STORE, которая за одно действие присваивает одно и то же значение всем ячейкам памяти некоторого корректного отрезка.

Исходно все ячейки памяти содержат значение 0. В лаборатории планируют запустить на суперкомпьютере программу обработки данных, но перед её запуском необходимо инициализировать память определенным образом. А именно: первые с1 ячеек памяти необходимо заполнить значениями v1, следующие c2 ячеек — значениями v2, и так далее, последние cn ячеек памяти необходимо заполнить значениями vn, где 1 ≤ vi ≤ m.

Ученым надо выяснить, какое минимальное количество операций STORE необходимо выполнить, чтобы проинициализировать память требуемым образом.

Например, если k = 3, n = 3, m = 2, c1 = 1, v1 = 1, c2 = 2, v2 = 2, c3 = 5, v3 = 1, то итоговое содержимое памяти должно быть следующим: [1, 2, 2, 1, 1, 1, 1, 1]. В этом случае для инициализации памяти достаточно трех операций STORE:

  • STORE([0, 7], 1), после этой операции все ячейки памяти содержат значение 1;
  • STORE([1, 1], 2), после этой операции содержимое памяти [1, 2, 1, 1, 1, 1, 1, 1];
  • STORE([2, 2], 2) , после этой операции содержимое памяти [1, 2, 2, 1, 1, 1, 1, 1], как и требуется.

Заметим, что операцию STORE([1, 2], 2) выполнить нельзя, потому что [1, 2] не является корректным отрезком памяти.

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

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

Первая строка входных данных содержит три целых числа: k, n и m (0 ≤ k ≤ 30, 1 ≤ n ≤ 105, 1 ≤ m ≤ 109).

Следующие n строк содержат по два целых числа, i-я из этих строк содержит числа ci и vi (1 ≤ ci ≤ 2k, 1 ≤ vi ≤ m, c1 + c2 + … + cn = 2k).

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

Требуется вывести одно целое число – минимальное количество операций STORE, которое необходимо выполнить для инициализации памяти заданным образом.

Пример

INPUT.TXTOUTPUT.TXT
13 3 2
1 1
2 2
5 1
3


Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483, E-mail: admin@acmp.ru



Работники Термеза все резюме Термеза.   Устрой, вслед за тем купить диплом в москве diplomas-room.com/ данных.   Крупные батареи салютов для корпоративных мероприятий