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

Задача A. Ролевая игра

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

Для обозначения уровня планируется использовать специальные значки двух цветов. Белый значок обозначает один уровень, а красный значок – k уровней. Игрок, изображающий персонажа с уровнем x, должен иметь a белых значков и b красных значков, чтобы сумма (a + b*k) была равна x. При этом персонажу не разрешается иметь более чем (k – 1) белых значков.

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

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

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

Входной файл INPUT.TXT содержит расположенные в одной строке три целых числа: n, m и k (1 ≤ n ≤ 10⁴, 1 ≤ m ≤ 10⁵, 1 ≤ k ≤ 10⁵).

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

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

Пример

Задача B. Колесо Фортуны

Развлекательный телеканал транслирует шоу «Колесо Фортуны». В процессе игры участники шоу крутят большое колесо, разделенное на сектора. В каждом секторе этого колеса записано число. После того как колесо останавливается, специальная стрелка указывает на один из секторов. Число в этом секторе определяет выигрыш игрока.

Юный участник шоу заметил, что колесо в процессе вращения замедляется из-за того, что стрелка задевает за выступы на колесе, находящиеся между секторами. Если колесо вращается с угловой скоростью v градусов в секунду, и стрелка, переходя из сектора X к следующему сектору, задевает за очередной выступ, то текущая угловая скорость движения колеса уменьшается на k градусов в секунду. При этом если v ≤ k, то колесо не может преодолеть препятствие и останавливается. Стрелка в этом случае будет указывать на сектор X.

Юный участник шоу собирается вращать колесо. Зная порядок секторов на колесе, он хочет заставить колесо вращаться с такой начальной скоростью, чтобы после остановки колеса стрелка указала на как можно большее число. Колесо можно вращать в любом направлении и придавать ему начальную угловую скорость от a до b градусов в секунду.

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

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

Первая строка входного файла INPUT.TXT содержит целое число n – количество секторов колеса (3 ≤ n ≤ 100). Вторая строка входного файла содержит n положительных целых чисел, каждое из которых не превышает 1000 — числа, записанные в секторах колеса. Числа приведены в порядке следования секторов по часовой стрелке. Изначально стрелка указывает на первое число.

Третья строка содержит три целых числа: a, b и k (1 ≤ a ≤ b ≤ 10⁹, 1 ≤ k ≤ 10⁹).

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

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

Примеры

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

В первом примере возможны следующие варианты: можно придать начальную скорость колесу равную 3 или 4, что приведет к тому, что стрелка преодолеет одну границу между секторами, или придать начальную скорость равную 5, что позволит стрелке преодолеть 2 границы между секторами. В первом варианте, если закрутить колесо в одну сторону, то выигрыш получится равным 2, а если закрутить его в противоположную сторону, то – 5. Во втором варианте, если закрутить колесо в одну сторону, то выигрыш будет равным 3, а если в другую сторону, то – 4.

Во втором примере возможна только одна начальная скорость вращения колеса – 15 градусов в секунду. В этом случае при вращении колеса стрелка преодолеет семь границ между секторами. Тогда если его закрутить в одном направлении, то выигрыш составит 4, а если в противоположном направлении, то – 3.

Наконец, в третьем примере оптимальная начальная скорость вращения колеса равна 2 градусам в секунду. В этом случае стрелка вообще не сможет преодолеть границу между секторами, и выигрыш будет равен 5.

Задача C. Форматирование текста

Многие системы форматирования текста, например TEX или Wiki, используют для разбиения текста на абзацы пустые строки. Текст представляет собой последовательность слов, разделенных пробелами, символами перевода строк и следующими знаками препинания: «,», «.», «?», «!», «-», «:» и «’» (ASCII коды 44, 46, 63, 33, 45, 58, 39). Каждое слово в тексте состоит из заглавных и прописных букв английского алфавита и цифр. Текст может состоять из нескольких абзацев. В этом случае соседние абзацы разделяются одной или несколькими пустыми строками. Перед первым абзацем и после последнего абзаца также могут идти одна или несколько пустых строк.

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

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

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

Первая строка входного файла INPUT.TXT содержит два целых числа: w и b (5 ≤ w ≤ 100, 1 ≤ b ≤ 8, b < w). Затем следует одна или более строк, содержащих заданный текст. Длина слова в тексте вместе со следующими за ними знаками препинания не превышает w, а длина первого слова любого абзаца вместе со следующими за ним знаками препинания не превышает (w – b). Текст содержит хотя бы одну букву. Перед первой буквой каждого абзаца знаков препинания нет.

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

Выходной файл OUTPUT.TXT должен содержать заданный текст, отформатированный в соответствии с приведенными в условии задачи правилами. Размер входного файла не превышает 100 Кбайт. Длина каждой строки во входном файле не превышает 250.

Пример

20 4
Yesterday, 
All my troubles seemed so far away, 
Now it looks as though they're here to stay, 
Oh, I believe in yesterday. 

Suddenly, 
I'm not half the man I used to be, 
There's a shadow hanging over me, 
Oh, yesterday  came suddenly...

    Yesterday, All
my troubles seemed
so far away, Now it
looks as though
they' re here to
stay, Oh, I believe
in yesterday. 
    Suddenly, I' m
not half the man I
used to be, There' s
a shadow hanging
over me, Oh,
yesterday came
suddenly...

Задача D. Космические исследования

Отделу космических исследований поступило задание сфотографировать из космоса n объектов в заданной области. Область имеет форму квадрата размером 50×50 километров. Если разделить ее на квадраты размером 1×1 километр, то интересующие отдел объекты окажутся в центрах некоторых единичных квадратов.

Введем систему координат, направив ось OX с запада на восток и ось OY с юга на север. Тогда каждому единичному квадрату будут сопоставлены координаты в диапазоне от 1 до 50, как показано на рисунке ниже.

Для космической съемки используется специальный фотоаппарат высокого разрешения, установленный на космическом спутнике. Фотоаппарат может делать снимки квадратных участков земной поверхности размером k × k километров. Исходно аппарат наведен на юго-западный угол заданной области, то есть, если сделать снимок, на нем будут видны единичные квадраты с координатами x и y от 1 до k километров.

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

Руководство отдела заинтересовалось вопросом: за какое минимальное количество дней можно сделать снимки всех объектов заданной области.

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

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

Первая строка входного файла INPUT.TXT содержит два целых числа: n и k (1 ≤ n ≤ 1000, 1 ≤ k ≤ 5). Следующие n строк содержат по два целых числа: x_i и y_i — координаты объектов в заданной области (1 ≤ x_i, y_i ≤ 50).

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

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

Примеры

Примеры

В первом примере возможна следующая последовательность действий: сделать снимок, 9 раз сместиться на восток, сместиться на север, сделать снимок, 9 раз сместиться на запад, сместиться на север, сделать снимок, 9 раз сместиться на восток, сместиться на север, сделать снимок. Всего требуется 30 перемещений участка съемки.

Во втором примере объекты расположены там же, но размер снимка больше, поэтому можно действовать так: сделать снимок, сместиться на север, сделать снимок, 8 раз сместиться на восток, сделать снимок, сместиться на север, сделать снимок. Всего требуется лишь 10 перемещений участка съемки.

В третьем примере перемещать участок съемки не требуется, можно просто сделать снимок.

Четвертый пример соответствует приведенному выше рисунку.

Задача E. Шахматная доска - 2

Аня разделила доску размера m × n на клетки размера 1×1 и раскрасила их в черный и белый цвет в шахматном порядке. Васю заинтересовал вопрос: клеток какого цвета получилось больше – черного или белого.

Для того чтобы выяснить это, он спросил у Ани, в какой цвет она раскрасила j-ю клетку в i-м ряду доски. По этой информации Вася попытался определить, клеток какого цвета на доске больше.

Требуется написать программу, которая по размерам доски и цвету j-й клетки в i-м ряду определит, клеток какого цвета на доске больше — черного или белого.

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

Входной файл INPUT.TXT содержит пять целых чисел: m, n, i, j и c (1 ≤ m, n ≤ 10⁹, 1 ≤ i ≤ m, 1 ≤ j ≤ n, с = 0 или с = 1). Значение c = 0 означает, что j-я клетка в i-м ряду доски раскрашена в черный цвет, а значение c = 1 – в белый цвет.

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

В выходной файл OUTPUT.TXT выведите одно из трех слов:

• black, если черных клеток на доске больше,
• white, если белых клеток на доске больше,
• equal, если черных и белых клеток на доске поровну.

Примеры

Задача F. Чемпионат по стрельбе

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

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

Будем считать, что участник соревнования занял k-е место, если ровно (k – 1) участников чемпионата набрали строго больше очков, чем он. При этом победителями считались все участники чемпионата, занявшие первое место.

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

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

Первая строка входного файла INPUT.TXT содержит целое число n — количество участников чемпионата страны по стрельбе (3 ≤ n ≤ 10⁵). Вторая строка содержит n положительных целых чисел, каждое из которых не превышает 1000, — очки участников чемпионата, приведенные в том порядке, в котором они выполняли стрельбу.

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

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

Примеры

Задача G. Делители - 2

Натуральное число a называется делителем натурального числа b, если b = ac для некоторого натурального числа c. Например, делителями числа 6 являются числа 1, 2, 3 и 6. Два числа называются взаимно простыми, если у них нет общих делителей кроме 1. Например, 16 и 27 взаимно просты, а 18 и 24 – нет.

Будем называть нормальным набор из k чисел (a₁, a₂, …, a_k), если выполнены следующие условия:

1. каждое из чисел ai является делителем числа n;
2. выполняется неравенство a₁ < a₂ < … < a_k;
3. числа a_i и a_i+1 для всех i от 1 до k – 1 являются взаимно простыми;
4. произведение a₁a₂ … a_k не превышает n.

Например, набор (2, 9, 10) является нормальным набором из 3 делителей числа 360.

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

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

Первая строка входного файла INPUT.TXT содержит два целых числа: n и k (2 ≤ n ≤ 10⁸, 2 ≤ k ≤ 10).

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

В выходном файле OUTPUT.TXT должно содержаться одно число – количество нормальных наборов из k делителей числа n.

Примеры

Задача H. Дом у дороги

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

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

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

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

Первая строка входного файла INPUT.TXT содержит одно целое число n – количество наиболее важных трасс (1 ≤ n ≤ 10⁴).

Последующие n строк описывают трассы. Каждая трасса описывается четырьмя целыми числами x₁, y₁, x₂ и y₂ и представляет собой прямую, проходящую через точки (x₁, y₁) и (x₂, y₂). Координаты заданных точек не превышают по модулю 10⁴. Точки (x₁, y₁) и (x₂, y₂) ни для какой прямой не совпадают.

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

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

Ответ должен иметь абсолютную или относительную погрешность не более 10^-6, что означает следующее. Пусть максимальное расстояние от выведенной точки до некоторой трассы равно x, а в правильном ответе оно равно y. Ответ будет засчитан, если значение выражения |x – y| / max{1, |y| } не превышает 10^-6.

Примеры