Школа программиста

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


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

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

Задача A. Два измерения

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

Ученые планируют провести важный эксперимент с использованием исследовательского модуля на планете X-2019. В процессе эксперимента будет проведено два измерения: основное и контрольное. Каждое измерение занимает ровно один час и должно начинаться спустя целое число часов после начала работы исследовательского модуля.

Данные эксперимента планируется немедленно передать на орбитальную станцию. Канал связи с орбитальной станцией будет установлен с l-го по r-й час от начала работы исследовательского модуля, включительно. Кроме того, согласно плану эксперимента между измерениями планета должна совершить целое число оборотов вокруг своей оси. Планета X-2019 осуществляет оборот вокруг своей оси за a часов.

Таким образом, если измерения осуществляются на i-м и j-м часу, то должно выполняться неравенство l ⩽ i < j ⩽ r, а величина (j - i) должна быть кратна a. Теперь учёным необходимо понять, сколько существует различных способов провести измерения.

Требуется написать программу, которая по заданным границам времени измерений l и r и периоду обращения планеты вокруг своей оси a определяет количество возможных способов провести измерения: количество пар целых чисел i и j, таких что l ⩽ i < j ⩽ r, и величина (j - i) кратна a.

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

Входной файл INPUT.TXT содержат три целых числа, по одному на строке: l, r и a (1 ⩽ l < r ⩽ 109, 1 ⩽ a ⩽ 109).

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

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

Примеры

INPUT.TXTOUTPUT.TXT
11
5
2
4
24
9
6
0

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

В первом примере можно провести измерения в следующие пары часов: (1, 3), (1, 5), (2, 4), (3, 5).

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


Задача B. Полные квадраты

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

С целью поиска закономерностей иногда полезно сгенерировать длинную последовательность по определенным правилам. Известно, например, что последовательность 0, 0+1, 0+1+3, 0+1+3+5, ... , 0+1+3+ ... +(2n-1), ... , составленная из сумм нескольких первых нечетных натуральных чисел, состоит из квадратов целых чисел: 0, 1, 4, 9, . . . , n2, ... .

Обобщим эту последовательность следующим образом: будем использовать вместо начального значения не ноль, а число k. Получим последовательность: k, k+1, k+1+3, k+1+3+5, ... , k+1+3+ ... +(2n-1), ... . В отличие от случая k = 0, в этой последовательности могут встречаться не только полные квадраты. Необходимо найти минимальное целое неотрицательное число, квадрат которого встречается в этой последовательности.

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

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

В единственной строке входного файла INPUT.TXT содержится целое число k — начальное число в последовательности (-1012 ⩽ k ⩽ 1012).

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

В выходной файл OUTPUT.TXT выведите минимальное неотрицательное целое число, квадрат которого встречается в описанной последовательности. Если в последовательности не встречается квадратов целых чисел, выведите «none».

Примеры

INPUT.TXTOUTPUT.TXT
100
2-52
32none

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

В первом примере каждое число последовательности является полным квадратом. Минимальный из них — 0, 02 = 0.

Во втором примере последовательность начинается так: -5, -4, -1, 4, 11, 20, . . .. Минимальное неотрицательное целое число, квадрат которого встречается в последовательности — 2, 22 = 4.

В третьем примере последовательность начинается так: 2, 3, 6, 11, 18, ... . В ней нет квадратов целых чисел.


Задача C. Автоматизация склада

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

Компания занимается автоматизацией склада. На складе хранятся n видов товаров, пронумерованных от 1 до n, каждый вид товара хранится в своём помещении. Товар вида i хранится в помещении с номером i.

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

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

В начале рабочего дня роботу поступил заказ на выдачу m товаров: a1, a2, ... , am. Робот должен выдать товары именно в этом порядке. Для этого он последовательно выполняет следующие действия: открывает помещение, в котором лежит очередной товар, берет товар, закрывает помещение и выдаёт товар клиенту. После этого робот переходит к выдаче следующего товара.

Исходно электронные карты лежат в отсеке в следующем порядке, от верхней к нижней: b1, b2, ... , bn. Для каждого помещения в отсеке лежит ровно одна карта.

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

Требуется написать программу, которая по заданным целым числам n и m, последовательности выдаваемых товаров a1, a2, ... , am и начальному положению карт в отсеке для хранения b1, b2, ... , bn определяет, какое минимальное количество действий придется совершить роботу, чтобы открыть все помещения в необходимом порядке. Для каждой вынутой карты необходимо также указать позицию, на которую её необходимо вернуть, чтобы добиться оптимального количества действий.

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

Первая строка входного файла INPUT.TXT содержит два целых числа n и m (1 ⩽ n, m ⩽ 3×105) — количество видов товаров и количество товаров, которые необходимо выдать со склада.

Вторая строка содержит m целых чисел a1, a2, ... , am (1 ⩽ ai ⩽ n) — типы товаров, которые необходимо выдать со склада, перечисленные в том порядке, в котором это необходимо сделать.

Третья строка содержит n различных целых чисел b1, b2, ... , bn (1 ⩽ bi ⩽ n) — порядок, в котором карты исходно находятся в отсеке для их хранения, перечисленные от верхней к нижней.

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

Первая строка выходного файла OUTPUT.TXT должна содержать число k — минимальное количество действий, которое потребуется совершить роботу, чтобы выдать товары в заданном порядке.

Далее выведите k чисел. Для каждого действия робота выведите одно число: позицию, на которую ему следует вернуть вынутую карту в отсек для хранения. Если карта возвращается на самую верхнюю позицию, следует вывести 1, если после одной карты, 2, и так далее, для последней позиции следует вывести n.

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

Примеры

INPUT.TXTOUTPUT.TXT
11 1
1
1
1
1
24 5
4 1 2 4 4
4 3 2 1
7
4 4 2 4 4 1 4
32 2
1 2
2 1
3
2 2 2

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

Во втором примере карты в отсеке робота перемещаются следующим образом:

ДействиеПеред действиемИзвлеченная картаОткрытое помещениеПозиция, куда помещается картаПосле действия
14, 3, 2, 14443, 2, 1, 4
23, 2, 1, 4342, 1, 4, 3
32, 1, 4, 3221, 2, 4, 3
41, 2, 4, 31142, 4, 3, 1
52, 4, 3, 12244, 3, 1, 2
64, 3, 1, 24414, 3, 1, 2
74, 3, 1, 24443, 1, 2, 4

Задача D. Машинное обучение

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

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

Были подготовлены обучающие наборы сложности от 0 до k. План обучения задаётся массивом целых чисел [a1, a2, ... , an], где ai задаёт сложность набора, используемого на i-й итерации обучения. Для всех i от 1 до n должно выполняться неравенство 0 ⩽ ai ⩽ k.

Выяснилось, что эффективность плана обучения зависит от битовых представлений сложностей обучающих наборов. Для того, чтобы план был эффективным, необходимо, чтобы для любых двух значений i и j, где 1 ⩽ i < j ⩽ n, выполнялось (ai and aj ) = ai . Напомним, что побитовое «и» (and) двух целых неотрицательных чисел устроено следующим образом: запишем оба числа в двоичной системе счисления, i-й двоичный разряд результата равен 1, если у обоих аргументов он равен 1. Например, (14 and 7) = (11102 and 01112) = 1102 = 6. Эта операция реализована во всех современных языках программирования, в языках C++, Java и Python она записывается как «&», в Паскале как «and».

Однако постоянное использование наборов одной сложности не даёт прогресса в обучении. Чтобы этого избежать, для плана обучения должны быть выполнены m требований следующего вида. Каждое требование задаётся двумя числами li и ri и означает, что ali ≠ ari.

Сотрудники лаборатории хотят найти количество эффективных планов, которые удовлетворяют всем требованиям. Так как это число может быть очень большим, нужно найти его остаток от деления на 109+7.

Требуется написать программу, которая по заданным целым числам n и k, а также m требованиям вида li, ri определяет количество эффективных планов, которые удовлетворяют всем требованиям, и выводит остаток от деления этого количества на число 109+7.

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

Первая строка входного файла INPUT.TXT содержит три целых числа n, m и k — количество итераций обучения, количество требований и максимальную сложность обучающего набора (1 ⩽ n ⩽ 3×105, 0 ⩽ m ⩽ 3×105, 0 ⩽ k ⩽ 1018). Следующие m строк описывают требования, i-я строка содержит два целых числа li, ri, которые означают, что ali ≠ ari (1 ⩽ li < ri ⩽ n). Гарантируется, что все требования различны.

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

В выходной файл OUTPUT.TXT выведите одно целое число — остаток от деления количества эффективных планов, удовлетворяющих всем требованиям, на число 109+7

Примеры

INPUT.TXTOUTPUT.TXT
12 0 39
23 1 2
1 2
2

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

Все возможные планы для первого теста: [0, 0], [0, 1], [0, 2], [0, 3], [1, 1], [1, 3], [2, 2], [2, 3], [3, 3].

Для второго теста: [0, 1, 1], [0, 2, 2].


Задача E. Неисправный марсоход

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

Марсоход, осуществляющий международную миссию на Марсе, неисправен. Для восстановления его работоспособности необходимо повысить мощность его батареи.

Мощность батареи марсохода задаётся целым положительным числом. Текущая мощность батареи равна a, для восстановления работоспособности марсохода необходимо повысить её мощность до значения b. Для изменения мощности батареи на марсоход с Земли можно передавать специальные сигналы двух типов: X и Y. Сигнал типа X увеличивает текущую мощность батареи на 1, а сигнал типа Y увеличивает текущую мощность батареи на 2.

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

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

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

Входной файл INPUT.TXT содержит три целых числа: a, b и c, по одному на строке (1 ⩽ a < b ⩽ 109, 2 ⩽ c ⩽ 109, a не кратно c, b не кратно c).

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

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

Примеры

INPUT.TXTOUTPUT.TXT
12
7
3
3
24
10
3
4

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

В первом примере можно действовать следующим образом: отправить на марсоход сигналы Y, X, Y. Мощность батареи меняется следующим образом: 2 → 4 → 5 → 7.

Во втором примере можно действовать следующим образом: отправить на марсоход сигналы X, Y, X, Y. Мощность батареи меняется следующим образом: 4 → 5 → 7 → 8 → 10.


Задача F. Интервальные тренировки

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

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

План тренировки представляет собой набор целых положительных чисел a1, a2, ... , am, где ai описывает нагрузку спортсмена в i-й день. Любые два соседних дня должны иметь различную нагрузку: ai ≠ ai+1. Чтобы рост нагрузки и её снижение чередовались, для i от 1 до m-2 должно выполняться следующее условие: если ai < ai+1, то ai+1 > ai+2, если же ai > ai+1, то ai+1 < ai+2.

Суммарная нагрузка в процессе выполнения плана должна составлять n, то есть a1 + a2 + ... + am = n. Ограничения на количество дней в плане нет, m может быть любым, но нагрузка в первый день тренировок зафиксирована: a1 = k.

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

Требуется написать программу, которая по заданным n и k определяет, сколько различных планов тренировок удовлетворяют описанным ограничениям, и выводит остаток от деления количества таких планов на число 109+7.

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

В первой строке входного файла INPUT.TXT находятся целые числа n и k (1 ⩽ n ⩽ 5000, 1 ⩽ k ⩽ n).

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

В выходной файл OUTPUT.TXT выведите одно число: остаток от деления количества планов тренировок на 109+7.

Примеры

INPUT.TXTOUTPUT.TXT
16 24
23 31

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

В первом примере подходят следующие планы: [2, 1, 2, 1], [2, 1, 3], [2, 3, 1], [2, 4].

Во втором примере единственный подходящий план [3].


Задача G. Экспедиция

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

Планируется отправить экспедицию к соседней звёздной системе. Были отобраны n кандидатов, пронумерованных от 1 до n, среди которых необходимо выбрать участников экспедиции. Организаторы хотят отправить в экспедицию как можно больше кандидатов.

Среди кандидатов был проведён опрос, в процессе которого каждый мог указать не более, чем одного из остальных кандидатов, с которым он не готов отправиться в экспедицию. Результатом опроса для i-го кандидата является целое число ai, которое равно номеру кандидата, с которым i-й кандидат не готов отправиться в экспедицию, либо -1, если i-й кандидат готов отправиться в экспедицию в любом составе.

Теперь организаторы должны выбрать, кто из кандидатов отправится в экспедицию. Решено было выбрать участников экспедиции так, что если туда входит некоторый кандидат i, и ai ≠ -1, то туда не входит кандидат ai. Организаторы хотят выбрать максимальное количество участников экспедиции.

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

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

В первой строке входного файла INPUT.TXT находится целое число n − количество кандидатов (1 ⩽ n ⩽ 300 000).

В следующих n строках даны результаты опроса, i-я из этих строк содержит результат опроса i-го кандидата, целое число ai (ai = -1 или 1 ⩽ ai ⩽ n, ai ≠ i).

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

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

Примеры

INPUT.TXTOUTPUT.TXT
14
2
4
2
1
2
23
2
-1
2
2

Задача H. Разбиение на пары

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

Космические археологи обнаружили на планете в соседней звездной системе n древних артефактов, которые они пронумеровали от 1 до n. Каждый артефакт имеет k различных параметров,каждый параметр характеризуется целым числом. Артефакт i имеет параметры ai,1, ai,2, ... , ai,k. Оказалось, что первые параметры у всех артефактов различны: для всех i ≠ j выполнено ai,1 ≠ aj,1, при этом другие параметры у артефактов могут совпадать.

Учёные также обнаружили текст, в соответствии с которым для активации артефактов их необходимо особым образом разбить на пары и совместить. Разбиение артефактов на пары является корректным, если для каждого t от 1 до k можно выбрать такое число bt, что оно лежит на отрезке между значениями t-го параметра артефактов каждой пары. То есть, если артефакты i и j образуют пару, должно выполняться условие ai,t ⩽ bt ⩽ aj,t или условие ai,t ⩾ bt ⩾ aj,t.

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

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

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

В первой строке входного файла INPUT.TXT заданы целые числа n и k — количество артефактов и количество параметров (2 ⩽ n ⩽ 2×105, n чётно, 1 ⩽ k ⩽ 7).

В следующих n строках задано по k целых чисел ai,1, ai,2, ... , ai,k — параметры артефактов (-109 ⩽ ai,j ⩽ 109, все значения ai,1 различны).

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

В выходной файл OUTPUT.TXT выведите «NO», если требуемого разбиения на пары не существует.

В противном случае выведите «YES» в первой строке. Далее выведите n/2 строк, в каждой строке выведите по два числа — номера артефактов, из которых следует составить пару. Каждый артефакт должен быть выведен ровно один раз.

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

Примеры

INPUT.TXTOUTPUT.TXT
16 2
8 6
1 5
6 3
3 1
4 7
7 2
YES
1 4
2 6
3 5
24 3
1 -1 -1
2 1 1
3 -1 1
4 1 -1
NO

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

В первом примере пары имеют следующие параметры (8,6) − (3,1), (1,5) − (7,2), (6,3) − (4,7). При указанном разбиении на пары подойдут, например, значения b1 = 4, b2 = 4.

Во втором примере требуемого разбиения на пары не существует.



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