Задачи олимпиады "Личное первенство по программированию среди школьников и студентов ИКИТ СФУ"

Задача A. Перевязь

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

Какое минимальное количество луидоров Портос должен заплатить мастеру за работу?

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

Входной файл INPUT.TXT содержит натуральное число N (N ≤ 10⁹) – длина перевязи в миллиметрах.

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

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

Примеры

Задача B. Портрет

У вас есть два портрета, выполненных в виде круга радиуса R. И большой набор круглых рам для таких портретов.

Для этих портретов необходимо найти одинаковые рамы. Рама должна быть того же размера, что и портрет, или чуть меньше (портрет выполнен на холсте, который можно немного подрезать). Но размер рамы должен быть как можно более близок к R.

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

Первая строка входного файла INPUT.TXT содержит два целых числа R – радиус портретов и N – количество найденных рам (1 ≤ N, R ≤ 10⁶). Вторая строка содержит N целых чисел, разделенных пробелами – радиусы рам. Все эти числа не превышают 10⁶.

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

В выходной файл OUTPUT.TXT выведите найденный радиус рам. Если двух подходящих рам с одинаковым радиусом не найдется, следует вывести 0.

Примеры

Задача C. Система счисления

Знаете ли Вы, что такое система счисления с основанием «ДВА НАОБОРОТ»? Эта система счисления отличается от системы счисления с основанием 2 тем, что:

• цифры записываются наоборот: самая старшая цифра стоит справа, а самая младшая - слева;
• справа обязательно приписывается лидирующий ноль.

Например, число 11 в двоичной системе равно 1011, а в системе с основанием «ДВА НАОБОРОТ» это число 11010. Сможете ли вы переводить из десятичной системы счисления в систему с основанием «ДВА НАОБОРОТ» и обратно?

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

Входной файл INPUT.TXT содержит строку, состоящую из буквы «d» или «b» – тип системы счисления (соответственно, десятичная или «ДВА НАОБОРОТ»). Далее следует пробел и натуральное число. Число может иметь один или несколько лидирующих нулей. В записи числа не более 30 символов, и оно не превышает 10⁸ в десятичной системе счисления.

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

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

Примеры

Задача D. Отрезки - 2

Дано N отрезков на плоскости. Найдите количество пар отрезков, пересекающихся в бесконечном количестве точек (число пар перекрывающихся отрезков).

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

Входной файл INPUT.TXT содержит натуральное число N – количество отрезков (N ≤ 1000). Далее идет N строк, каждая из которых содержит четыре числа через пробел - X₁, Y₁, X₂, Y₂ – целочисленные координаты концов отрезка. Все координаты принимают значения 0 до 10⁶. Гарантируется, что все отрезки имеют ненулевую длину.

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

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

Пример

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

Перекрываются три пары отрезков:

1. [(10,0);(20,0)] и [(15,0);(25,0)] перекрываются на [(15,0);(20,0)];
2. [(15,0);(25,0)] и [(20,0);(10,0)] перекрываются на [(20,0).(25,0)];
3. [(50,0);(100,0)] и [(70);(80,0)] перекрываются на [(70,0).(80,0)].

Отрезки, пересекающиеся в одной точке, не перекрываются (например, [(1,1);(2,2)] и [(2,2);(3,3)]).

Задача E. Секрет

Вам в руки попала секретная записка на английском языке. Текст записки может быть любым, главное - код, заложенный в тексте. Чтобы расшифровать записку нужно посчитать количество букв «b» и «g» в записке (на любом регистре).

Если букв «b» больше, чем букв «g», то все плохо. Если букв «b» меньше, чем букв «g», то все хорошо. Ну, а если буквы содержатся в записке в одинаковом количестве, то пока не ясно, как дела пойдут.

Напишите программу для расшифровки таких секретных записок.

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

Входной файл INPUT.TXT содержит натуральное число N – количество строк в записке (N ≤ 100). Далее идет текст записки из N строк, каждая строка не более 100 символов. В тексте записки могут встречаться английские символы, цифры, пробелы, знаки препинания и переводы строки.

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

В выходной файл OUTPUT.TXT выведите все строки записки в неизменном виде. После вывода последней строки записки в той же строке выведите один пробел, слово «is», ещё один пробел и далее слово, определяющее тайный смысл записки:

• «GOOD» – если все хорошо;
• «A BADDY» – если все плохо;
• «NEUTRAL» – если пока не ясно, как пойдут дела.

Примеры

1
It is rainy and I  have bought umbrella

It is rainy and I  have bought umbrella is A BADDY

3
It is 
rainy                and I have 
bought umbrella

It is 
rainy                and I have 
bought umbrella is A BADDY

1
It is rainy and I  have bought tea

It is rainy and I  have bought tea is NEUTRAL

1
My aunt Ann is greedy!

My aunt Ann is greedy! is GOOD

Задача F. Звезда

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

• Точка - означает отсутствие звезды.
• Знак "звездочка" - означает звезду.

Созвездие - это соединенные вместе несколько звезд. Звезды считаются соединенными, если они являются соседями сверху, снизу, справа или слева. Одна изолированная звезда также считается созвездием.

Напишите программу для подсчета количества созвездий на карте.

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

Первая строка входного файла INPUT.TXT содержит два натуральных числа N и M – количество строк и столбцов на карте звездного неба (N, M ≤ 300). Далее следуют N строк, каждая из которых содержит M символов «.» (точка) или «*» (звездочка).

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

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

Пример

Задача G. Ковер

Драгоценности короля Людовика XIII хранятся в специальных ларцах. Все ларцы имеют одинаковые размеры 40 дюймов длины и 8 дюймов ширины.

Король приказал изготовить ковер и составить на него все драгоценности. При этом придворные должны соблюдать следующие условия:

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

Людовик XIII хочет, чтобы ковер был оптимальных размеров:

1. Площадь ковра должна быть минимальной;
2. Если есть несколько ковров оптимальной площади, выбрать среди них тот, который больше похож на квадрат (т.е. имеет минимальную разницу длины и ширины).

Ваша задача - вычислить размеры такого ковра.

На рисунке показан пример оптимального размещения на ковре 29 ларцов. Размеры такого ковра: 92 дюйма длины и 32 ширины.

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

Входной файл INPUT.TXT содержит натуральное число N (N ≤ 10¹²) – количество ларцов.

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

В выходной файл OUTPUT.TXT выведите ответ в формате W X H = S, где W - длина ковра, H – ширина ковра, S – площадь ковра.

Примеры

Задача H. Единички

В арифметическом выражении разрешается использовать число 1, операции сложения, умножения и скобки. Какое наименьшее количество единиц нужно использовать, чтобы получить заданное натуральное число N?

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

Входной файл INPUT.TXT содержит натуральное число N (N ≤ 5000).

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

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

Пример

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

(1 + 1 + 1) * (1 + 1) + 1 = 7

Задача I. Дерево - 2

Катя решила разместить на стене комнаты свое родословное дерево из фотографий. В корне дерева она повесила свою фотографию. Фотографии мамы и папы – это левое и правое поддеревья. И так далее… Катя повесила на стену фотографии всех родственников, которых она знала, полюбовалась на свою работу, и ушла гулять.

Пока Кати не было, её брат Антон решил вставить фотографии в рамочки. Для этого он решил снять фотографии. Сначала он слева-направо снял все фотографии, которые являются листьями дерева (лист - это вершина, у которой нет поддеревьев.) Снятые портреты Антон сложил в стопку и перенес к себе в комнату. Затем вернулся в комнату Кати и повторил процедуру. В конце концов на стене остался только портрет Кати. Антон перенес и этот портрет к себе.

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

• буквы всех узлов левого поддерева в алфавитном порядке идут перед буквенным обозначением текущего узла,
• буквы всех узлов правого поддерева в алфавитном порядке идут после буквенного обозначения текущего узла.

На рисунке показан пример дерева, а также последовательность действий Антона.

Удаление узлов с данными:

BDHPY
CM
GQ
K

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

Входной файл INPUT.TXT содержит нескольких строк, где каждая строка содержит буквенные обозначения удаленных узлов. Последняя строка теста содержит знак «*». Гарантируется, что в дереве есть хотя бы один узел. Число узлов дерева не превосходит число символов английского алфавита. Каждая буква в тесте встречается только один раз.

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

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

Пример

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

Найдите n-й элемент строго возрастающей последовательности, которая описывается следующими правилами:

1. число 1 является элементом последовательности;
2. если a – элемент последовательности, то 2a, 3a, 5a тоже являются элементами последовательности;
3. последовательности принадлежат только элементы, заданные правилами 1 и 2.

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

Входной файл INPUT.TXT содержит одно натуральное число n (n ≤ 10000).

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

В выходной файл OUTPUT.TXT выведите одно число – n-й элемент последовательности.

Примеры