Задачи олимпиады "II (районный) этап Всероссийской олимпиады школьников Красноярского края по информатике"
Задача A. Детали
(Время: 1 сек. Память: 16 Мб Баллы: 100)
На клеточном поле N•M расположены две жёсткие детали. Деталь A накрывает в каждой строке несколько (не ноль) первых клеток, деталь B — несколько (не ноль) последних; каждая клетка либо полностью накрыта одной из деталей, либо нет.
Деталь B начинают двигать влево, не поворачивая, пока она не упрётся в A хотя бы одной клеткой. Определите, на сколько клеток будет сдвинута деталь B.
Входные данные
В первой строке входного файла INPUT.TXT записано два числа N и M — число строк и столбцов соответственно (1 ≤ N, M ≤ 100). Далее следуют N строк, задающих расположение деталей. В каждой находится ровно M символов "A" (клетка, накрытая деталью A), "B" (накрытая деталью B) или "." (свободная клетка).
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести одно число — ответ на задачу.
Пример
№
INPUT.TXT
OUTPUT.TXT
1
4 6
AA.BBB
A....B
AAA..B
A..BBB
1
Задача B. Дипломы
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось n дипломов, причем, как оказалось, все они имели одинаковые размеры: w – в ширину и h – в высоту.
Сейчас Петя учится в одном из лучших российских университетов и живет в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить ее к стене, а к ней – дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещен строго в прямоугольнике размером w на h. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек.
Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов.
Входные данные
Входной файл INPUT.TXT содержит три целых числа: w, h, n (1 ≤ w, h, n ≤ 109).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Пример
№
INPUT.TXT
OUTPUT.TXT
1
2 3 10
9
Пояснение
Пример расстановки 10 дипломов 2х3 в квадрате 9х9:
Задача C. Сочетания
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Петя выписал все сочетания из N первых английских букв по K букв. В каждом сочетании он выписывал буквы в лексикографическом порядке. Сочетания он выписывал в лексикографическом порядке по одному в строке. Теперь он хочет узнать: какое слово записано в M-ой строке.
Входные данные
Во входном файле INPUT.TXT записаны целые числа N, K, M (1 ≤ N ≤ 26, 1 ≤ K ≤ N). Гарантируется, что M не превосходит количества всех выписанных сочетаний.
Выходные данные
В выходной файл OUTPUT.TXT выведите M-ое выписанное сочетание.
Пример
№
INPUT.TXT
OUTPUT.TXT
1
4 2 3
ad
Пояснение
Все сочетания в порядке их записи: ab, ac, ad, bc, bd, cd. Здесь 3м по счету сочетанием является ad.
Задача D. Спирт
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Каждому школьнику из курса органической химии известна формула молекулы этилового спирта – C2H5(OH). Откуда видно, что молекула спирта состоит из двух атомов углерода (C), шести атомов водорода (H) и одного атома кислорода (O).
По заданному количеству атомов каждого из описанных выше элементов требуется определить максимально возможное количество молекул спирта, которые могут образоваться в процессе их соединения.
Входные данные
Первая строка входного файла INPUT.TXT содержит 3 натуральных числа: C, Н и O – количество атомов углерода, водорода и кислорода соответственно. Все числа разделены пробелом и не превосходят 1018.
Выходные данные
В выходной файл OUTPUT.TXT выведите максимально возможное число молекул спирта, которые могут получиться из атомов, представленных во входных данных.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
2 6 1
1
2
10 5 12
0
3
18 35 3
3
Задача E. Веревочный мост
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Однажды N путешественников решили ночью пересечь по веревочному мосту быструю горную речку. Без освещения перейти мост невозможно. К счастью, у одного из них оказался с собой фонарик. Известно, что мост выдерживает только двоих, а скорости людей могут различаться. Если мост пересекают два человека с разной скоростью, то они вынуждены двигаться со скоростью самого медленного из них. Скорость движения каждого из путников известна.
Помогите путешественникам как можно быстрее перебраться через мост. Требуется написать программу, определяющую минимальное время, которое потребуется для такого перехода. Например, если N=4, а время, требуемое для перехода по мосту для каждого, составляет 5, 10, 20 и 25 минут соответственно, то наименьшее время, требуемое для пересечения моста, составит ровно 60 минут.
Входные данные
В первой строке входного файла INPUT.TXT содержится натуральное число N – количество путешественников (N ≤ 105). Во второй строке располагаются N натуральных чисел – скорости всех путников, разделенные пробелом и не превосходящие 106. Здесь под скоростью человека понимается время в минутах, необходимое для перехода через мост.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число – минимально возможное время, необходимое путникам для пересечения моста.
