Задания

I тур 2017-2018 учебного года

Задания олимпиады по информатике – 2017

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

Виртуальный кабинет

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

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

Ключевые даты

Этапы выполнения заданий 1 тура	Дата получения (начала выполнения) задания	Дата окончания выполнения задания
Выполнение заданий проекта, загрузка работ через Виртуальный кабинет	11-00 (мск) 16 октября 2017 г.	17-00 (мск) 25 октября 2017 г.
Публикация итогов проекта		17-00 (мск) 13 ноября 2017 г.
Команды отправляют отзыв о проекте из Виртуального кабинета.	15 ноября 2017 г.	17 ноября 2017 г.

Задачи теоретической части

В предложенных задачах требуется дать словесное описание алгоритма решения предложенной задачи (если не оговаривается что-то другое). При проверке решений (алгоритмов) будут учитываться следующие параметры:

1. четкость описания алгоритма,
2. результативность (алгоритм в любом случае должен давать некоторый результат),
3. корректность (алгоритм должен давать правильный ответ при любых корректных входных данных),
4. оптимальность (следует привести по возможности наиболее оптимальный по количеству шагов алгоритм; из нескольких корректных алгоритмов больше баллов получит наиболее оптимальный).

Решения задач теоретической части оформляются в виде документа Microsoft Word в соответствии с техническими требованиями и загружаются для проверки в Виртуальном кабинете.

Задача 1. Задача коммивояжера

В столь тяжелое и нестабильное время раем кажется жизнь в одномерной стране Лвалсоря, состоящей из 3 городов, каждый из которых находится на координатной прямой Ox. Город А расположен в точке с координатой a, город B расположен в точке с координатой b, город С расположен в точке c. Коммивояжер Витя изначально находится в городе A. В его планах – посетить сначала город B, потом – город C, а затем вернуться обратно в A. Витя хочет посчитать, какое расстояние ему придётся преодолеть в рамках этого путешествия. Помогите ему это сделать. Разработайте и опишите алгоритм, решающий данную задачу.

Ограничения на координаты: координата города – натуральное число, не превосходящее 1000.

Задача 2. Арифметика

А ведь до того, как Витя стал работать коммивояжером, у него было веселое и беззаботное детство, школа… В школах Лвалсоря обязательным предметом в школе является арифметика. Будучи шестиклассником, Витя проходил арифметику и учился вычислять остаток от деления числа, записанного в b-ичной системе счисления, на b-1:

7829₁₀ mod 9 = 8₁₀

123456₇ mod 6 = 3₇

123₄ mod 3 = 0₇

(Заметим, что 123456₇ = 22875₁₀, 123₄ = 27₁₀)

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

Ограничения: длина числа не превосходит 10⁶, b – натуральное число в пределах от 2 до 10.

Задача 3. Мозаика

Помимо математики и информатики Витя увлекается составлением мозаик. Сейчас у него есть кусочки двух типов: красные и синие. Витя хочет собрать квадрат размером N² x N² клеток по следующим правилам:

• В любой строке должно быть ровно K синих кусочков;
• В любом столбце должно быть ровно K красных кусочков;
• Если разрезать квадрат на квадраты размером N x N (всего их N x N штук), то любой полученный квадрат должен иметь ровно K синих клеток.

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

Ограничения: 1 ≤ N ≤ 30, 0 ≤ K ≤ N²

Задача 4. Стрельба

Круг хобби Вити исчисляется не только собиранием мозаик. В своё время Витя серьёзно занимался пулевой стрельбой. Во время службы в армии Витя был отправлен с секретным заданием. В случае провала он мог быть загнан в угол (левую нижнюю клетку) прямоугольного поля размера N x M, в остальных клетках которого находятся враги (можно считать, что враг занимает центр клетки). Однако Витя был настолько метким стрелком, что одним выстрелом убивал всех врагов, расположенных на одной прямой. Так как Витя был хорошим математиком, он всегда мог посчитать минимальное число патронов, которыми он мог уничтожить всех врагов. А получится ли это у вас?

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

Ограничения: 1 ≤ N, M ≤ 10⁶

Задача 5. Игра

В свободное время Витя любит играть в следующую игру. На бесконечном клетчатом поле закрашивают K клеток. Каждая клетка задается координатой (X_i, Y_i). Далее игра проводится следующим образом. Если есть такие четыре клетки, что три из них закрашены и все четыре клетки расположены углах прямоугольника, параллельного осям координат, то четвертая клетка закрашивается. Клетки закрашиваются до тех пор, пока это возможно. Разработайте и опишите эффективный алгоритм, который поможет Вите найти количество закрашенных по окончании игры клеток.

Ограничения: 1 ≤ K ≤ 5 x 10⁵, 0 ≤ |X_i|, |Y_i| ≤ 10¹⁸.

Задачи практической части

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

Для проверки принимаются только исходные тексты программ (файлы *.pas, *.c, *.cpp) в соответствии с техническими требованиями. Программы (исходные тексты) загружаются для проверки в Виртуальном кабинете, сразу компилируются и проверяются на наборе тестов, после чего участнику выдается результат. Допускается вносить изменения в программы произвольное количество раз и загружать программы для повторной проверки.

Внимание: загрузка работ будет возможна с 11:00 16 октября 2017 года. Загружается только исходный текст программы (файл *.pas, *.c, *.cpp) без архивирования.

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

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

Пример оформления кода, использующий корректный ввод/вывод данных. Обратите внимание: перед сдачей решений на C/C++ при использовании функции freopen следует подключать библиотеку stdio.h/cstdio. 

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

Задача 1. Очередь в ВУЗ

И вот настал этот день — Витя пошёл относить документы! Но, придя в приёмную комиссию, Витя увидел длинную очередь таких же абитуриентов, как и он. Очередь была настолько длинная, что он решил, что не успеет сегодня подать документы, и ушёл ни с чем. На следующий день очередь только выросла — ещё бы, ведь скоро заканчивается приёмная кампания! Так шёл день за днём, пока не наступил последний день приёмной кампании. В этот день Витя точно решил досидеть до конца, потому что иначе он не сможет поступить в выбранный ВУЗ. Про приёмную комиссию известно следующее:

1. В приёмной комиссии есть M типов кабинетов, которые надо пройти в порядке возрастания типа кабинета.
2. Кабинетов каждого типа K штук.
3. Время прохождения каждого кабинета составляет T минут.

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

К сожалению, Витя очень рассеянный мальчик, и, пока он сидел в очереди, он забыл свой регистрационный номер. Однако для каждого номера он помнит время, в которое студент с этим номером пришёл в ВУЗ. Также ему известно, что в очереди он просидит дольше всех (т.е. не существует студента, который просидит дольше него), и что среди всех таких студентов его номер минимальный. Помогите Вите по этой информации определить его номер.

Вход: файл input.txt, в первой строке вам даны 4 целых числа — N, M, K, T – количество студентов, типов кабинетов, количество кабинетов каждого типа и время прохождения каждого кабинета. Далее во второй строчке следуют N чисел T_i – время прихода студента с номером i

Ограничения: 1 ≤ N ≤ 10⁵, 1 ≤ M ≤ 10⁵, 1 ≤ K ≤ 10⁹, 0 ≤ T ≤ 10¹², T_i ≤ 10¹²

Выход: файл output.txt, в единственной строке которого нужно вывести номер Вити.

input.txt	output.txt
3 1 1 113 0 0 0	3
4 2 2 4 0 1 5 5	1

Задача 2. Перестановки со спусками

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

Обозначим каждое из чисел в перестановке как p_i (i=1,…,n). Спуском перестановки  назовём такое число k, что p_k > p_k+1. К примеру, перестановка (5 6 2 4 7 1 3) имеет два спуска: 2 (6 > 2) и 5 (7 > 1). 

Обозначим через D(p) количество спусков в перестановке p. Например, D(5 6 2 4 7 1 3) = 2.Тождественная перестановка является единственной, у которой D(p)=0, а обратная – единственной, у которой D(p) = N–1.

Перед Витей поставлена следующая задача: ему даны числа N – количество чисел в перестановке, v – количество спусков в перестановке, требуется найти число перестановок длины N, имеющих ровно v спусков. Например, есть 4 перестановки длины 3 с 1 спуском: 
(1 3 2), (2 1 3), (2 3 1), (3 1 2). В то же время есть только по 1 перестановке с 0 и 2 спусками – (1 2 3) и (3 2 1) соответственно. Но, так как это число может быть очень большим, то от Вити требуется найти это количество по модулю 10⁹+7.

Вход: файл input.txt, в единственной строке которого содержатся числа N и v

Ограничения: 1 ≤ N ≤ 100, 0 ≤ v≤ N–1

Выход: файл output.txt, в единственной строке которого нужно количество перестановок по модулю 10⁹+7 (т. е. остаток от деления количества перестановок на 10⁹+7)

input.txt	output.txt
3 0	1
3 1	4
3 2	1

Задача 3. Счастье студента

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

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

1. В комнате с номером i происходит нашествие из Q тараканов. В таком случае несчастье всех комнат увеличивается на max(0, Q – D), где D – расстояние до комнаты, в которой произошло нашествие.
2. В комнатах с номерами с L по R травят тараканов с силой X. В этом случае несчастье всех комнат на этом отрезке уменьшается на X.
3. Ко Мендант просит Витю посчитать суммарное несчастье студентов на отрезке с L по R.

Помогите Вите ответить на все вопросы Ко Менданта.

Вход: файл input.txt, в первой строке которого даны два числа – N и M - количество комнат и событий соответственно. В следующих M строках идут запросы. Каждый запрос имеет один из следующих типов:

1. ? L R – Ко Мендант интересуется суммарным несчастьем студентов на отрезке с L по R.
2. R i Q – В комнате с номером i произошло нашествие Q тараканов.
3. C L R X – в комнатах с L по R травят тараканов с силой X.

Ограничения: 1 ≤ N, M ≤ 10⁵, 1 ≤ L ≤ R ≤ N, 1 ≤ i ≤ N, 0 ≤ Q ≤ 10⁸, 0 ≤ X ≤ 10⁸

Выход: файл output.txt, в котором на каждый запрос первого типа вам надо вывести в отдельной строке единственное число – суммарное несчастье комнат на данном отрезке.

input.txt	output.txt
4 4 R 2 3 C 2 2 2 ? 1 2 ? 4 4	3 1
5 6 R 4 3 R 2 2 C 1 3 3 ? 1 3 R 1 1 ? 1 5	-2 4