Задания

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

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

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

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

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

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

 

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

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

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

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

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

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

Задача 1. Суммы

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

Задача 2. Ладьи

Имеется поле размера w * h (1 ≤ w, h ≤ 40000), на котором расставлены N ладей (0 ≤ N ≤ min(w, h)). Каждая ладья задаётся координатой
(x, y) (1≤ x ≤ w, 1 ≤ y ≤ h) на поле и бьёт все клетки, находящиеся с ней на одной горизонтали или вертикали. Опишите эффективный алгоритм нахождения максимального по площади прямоугольника, клетки которого не бьёт ни одна из ладей.

Задача 3. Последовательность

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

Примеры:

1317819 – 6 чисел (1 3 1 7 81 9)

040 – разбиение невозможно

101 – 1 число (101)

Задача 4. Количество счастья

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

Количество таких комбинаций называется степенью счастливости билета.

Например:

У Михаила есть билет с номером 114222. Степень счастливости этого билета равна восьми, т.к.

-1-1-4=-2-2-2,

-1-1+4=2+2-2,

-1-1+4=2-2+2,

-1-1+4=-2+2+2,

1+1-4=2-2-2,

1+1-4=-2+2-2,

1+1-4=-2-2+2,

1+1+4=2+2+2.

Миша хочет узнать суммарную величину счастья, которая содержится в целом рулоне билетов. Суммарное счастье — это сумма степеней всех псевдосчастливых билетов. Билеты нумеруются с 0…0 до 9…9, в билете 2N цифр. Опишите эффективный алгоритм, который определит суммарное счастье в рулоне по заданному числу N.

Задача 5. Рациональные числа

Определим бесконечное бинарное дерево из положительных рациональных чисел:

1. Значение в корне – 1/1
2. В левом сыне вершины, в которой записано число p/q, записано значение p/(p+q)
3. В правом сыне вершины, в которой записано число p/q, записано значение (p+q)/q

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

Занумеруем вершины дерева слева направо, сверху вниз и определим последовательность положительных рациональных чисел: F(1)=1/1, F(2)=1/2, F(3)=2/1, F(4)=1/3, F(5)=3/2, F(6)=2/3, …

Опишите эффективный алгоритм нахождения номера дроби p/q в последовательности F, то есть найти такое n, что F(n)=p/q, если гарантируется, что (1 <= p, q <= 2³¹-1).

 

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

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

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

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

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

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

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

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

Задача 1. Тренировки

Тренер хочет, чтобы спортсмены из его команды взбежали по ступенькам стадиона, используя большие (2 ступеньки) и малые (1 ступенька) шаги следующим образом:

1. Количество больших шагов, сделанных каждой ногой спортсмена, было одинаково;
2. Количество малых шагов, сделанных каждой ногой спортсмена, было одинаково;
3. Количество больших шагов должно быть не меньше количества малых шагов;
4. Спортсмен начинает шагать с левой ноги.

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

Например, при n=6 существуют 4 таких способа:

2211, 2112, 1221, 1122 (жирным выделены шаги, которые спортсмены делают правой ногой)

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

Ограничения: 0<N<101

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

input.txt	output.txt
2	0
6	4

 

Задача 2. Солярис

Для изучения океана планеты Солярис было построено N исследовательских станций. Каждая из станций задаётся координатами (x_i, y_i, z_i) в пространстве. Для быстрого перемещения между станциями запланировано построить N-1 телепорт, каждый из которых будет соединять две станции и позволит перемещаться между ними в произвольном направлении. Набор телепортов должен соединять все станции, то есть так, чтобы с любой станции до любой другой можно было переместиться либо непосредственно через соединяющий их телепорт, либо использовав несколько телепортов с посещением произвольных станций. Стоимость постройки телепорта между станциями i и j равна c_ij = min(|x_i – x_j|, |y_i – y_j|, |z_i – z_j|).

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

Вход: файл input.txt, в первой строке содержится число N – количество исследовательских станций. В следующих N строках содержится описание очередной станции, задаваемой координатами (x_i, y_i, z_i). Координаты разделяются пробелом.

Ограничения: 2≤N≤10⁵, -10⁹≤ x_i, y_i, z_i ≤10⁹

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

input.txt	output.txt
2 1 5 10 7 8 2	3
3 -1 -1 -1 5 5 5 10 10 10	11

 

Задача 3. Ралли

Миша не очень любит компьютерные игры, но в игру "Ралли" он играет с удовольствием. Игра происходит на поле из NxM квадратиков. Необходимо проехать из клетки с координатами (1,1) в клетку с координатами (N,M) за минимальное количество шагов. Перемещаться можно только в соседние по горизонтали или вертикали клетки. При этом на игровом поле есть непроходимые места, на которые заезжать нельзя. Казалось бы, простая задача. Но ведь вы знаете, что машина не ездят на воздухе, им нужен бензин. У нашей машины бак объемом K литров, стартует она с полным баком. Конечно, не всегда можно добраться с K литрами бензина до финиша, но в некоторых клетках есть заправочные станции, которые заливают 5 литров бензина в бак. Заправка 5-ти литров происходит в тот момент, когда вы заехали на клетку с заправкой. Заправляться на одной и той же заправке можно неограниченное количество раз. Но запомните, что каждый ход машина должна перемещаться на одну клетку и тратит один литр бензина на перемещение. И, естественно, нельзя залить бензина больше, чем объем бака. Ваша программа должна найти минимальное количество шагов, которые должен сделать игрок для проезда из клетки (1,1) (левый верхний угол) в клетку (N,M) (правый нижний угол). Если проехать не получится, то выведите "-1".

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

У карты следующая легенда:

"*" – область, в которой можно ездить;

"#" – область, в которой нельзя ездить;

"X" – область, в которой заливается 5 литров бензина.

Ограничения: 1<N<101, 1<M<101, 0<K<201.

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

input.txt	output.txt
9 5 2 **X** ***** **X** ***** X*X** ***** X**** ***** X*X**	16
5 5 1 *XX** **XX* ***X* **### *****	-1