Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Положение] [Расписание] [Архив] [Содержание] [Задачи] [Рейтинг]

Задачи олимпиады "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.TXTOUTPUT.TXT
14 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.TXTOUTPUT.TXT
12 3 109

Пояснение

Пример расстановки 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.TXTOUTPUT.TXT
14 2 3ad

Пояснение

Все сочетания в порядке их записи: 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.TXTOUTPUT.TXT
12 6 11
210 5 120
318 35 33

Задача E. Веревочный мост

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Однажды N путешественников решили ночью пересечь по веревочному мосту быструю горную речку. Без освещения перейти мост невозможно. К счастью, у одного из них оказался с собой фонарик. Известно, что мост выдерживает только двоих, а скорости людей могут различаться. Если мост пересекают два человека с разной скоростью, то они вынуждены двигаться со скоростью самого медленного из них. Скорость движения каждого из путников известна.

Помогите путешественникам как можно быстрее перебраться через мост. Требуется написать программу, определяющую минимальное время, которое потребуется для такого перехода. Например, если N=4, а время, требуемое для перехода по мосту для каждого, составляет 5, 10, 20 и 25 минут соответственно, то наименьшее время, требуемое для пересечения моста, составит ровно 60 минут.

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

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

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

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

Примеры

INPUT.TXTOUTPUT.TXT
12
10 20
20
24
5 10 20 25
60


Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483