Седьмая Всероссийская Командная олимпиада школьников по программированию
Ограничение времени:
2 сек
Входной файл:
cinema.in
Ограничение памяти:
64 Мб
Выходной файл:
cinema.out
Условие
Марья Ивановна с Марьей Михайловной привели школьников в кинотеатр. Чтобы не было никаких обид,
Марья Ивановна построила всех школьников по алфавиту и рассадила их: сначала в первый ряд слева направо,
затем во второй слева направо и т.д., заполнив весь зал из n рядов по m кресел. Тут пришла Марья Михайловна
и сказала, что ребята сели неправильно - надо пересесть. Она предложила сначала заполнить все первые
места от первого ряда к последнему, затем все вторые места и т. д.
Определите, сколько школьников после такой пересадки останется на своем месте.
Например, если n = 3 и m = 3, то в первом случае дети сядут так:
1
2
3
4
5
6
7
8
9
а во втором - так:
1
4
7
2
5
8
3
6
9
Таким образом, три школьника: 1, 5 и 9 останутся на своих местах.
Формат входного файла
Входной файл содержит два целых числа n и m.
Формат выходного файла
Выведите количество школьников, которые останутся на своих местах.
Седьмая Всероссийская Командная олимпиада школьников по программированию
Ограничение времени:
2 сек
Входной файл:
windows.in
Ограничение памяти:
64 Мб
Выходной файл:
windows.out
Условие
Когда пользователь работает в операционной системе Windows, у него часто запущено несколько приложений.
Каждое из приложений работает в отдельном окне. Для переключения между окнами используется комбинация клавиш "Alt+Tab".
Эта комбинация делает активным окно, в котором пользователь работал перед тем, как перейти в текущее активное окно.
Чтобы переключиться в другое окно, можно нажать клавишу "Alt" и затем, не отпуская ее, несколько раз нажать клавишу "Tab".
Чтобы понять, какое окно станет активным после этого, воспользуемся следующей моделью. Пусть запущено п приложений.
Приложения в операционной системе организованы в виде списка и упорядочены по убыванию времени последней активности.
То есть приложение, окно которого является активным в настоящий момент - первое в списке, приложение, окно которого было
активно перед этим - второе, и т. д.
Если нажать клавишу "Alt" и затем, не отпуская ее, нажать клавишу "Tab" k раз, то активным станет окно приложения,
которое находится на (kmodn) + 1-м месте в списке. Здесь amodb означает остаток от деления a на b. Иными словами,
операционная система рассматривает список как циклический, переходя после последнего элемента списка к первому.
При запуске нового приложения оно добавляется в начало списка.
Задана последовательность действий пользователя, где каждое действие - либо запуск приложения, либо переключение
между окнами. Выведите в выходной файл, в каком порядке пользователь работал с приложениями.
Формат входного файла
Первая строка входного файла содержит целое число n - количество действий пользователя.
Следующие n строк содержат описание действий пользователя.
Запуск приложения описывается строкой "Run < имя приложения >".
Здесь "Run < имя приложения >" - строка из не более чем 100 латинских букв, цифр и пробелов.
Она отделена от слова "Run" ровно одним пробелом. Все имена приложений различны. Большие и маленькие буквы считаются различными.
Переключение между приложениями описывается строкой "Alt+Tab-. . . +Tab", здесь подстрока "+Tab" повторена в точности столько раз,
сколько раз пользователь нажал клавишу "Tab", не отпуская клавишу "Alt". Это количество не превышает 100.
Первая команда во входном файле - всегда команда "Run".
Формат выходного файла
Выведите в выходной файл n строк - последовательность имен приложений, с которыми работал пользователь в порядке, в котором их окна становились активными.
Ограничения
1 ≤ n ≤ 1000
Примеры тестов
№
Входной файл (windows.in)
Выходной файл (windows.out)
1
6
Run Mozilla Firefox
Run Free Pascal
Alt+Tab
Run Miranda IM
Alt+Tab+Tab
Alt+Tab+Tab+Tab
Mozilla Firefox
Free Pascal
Mozilla Firefox
Miranda IM
Free Pascal
Free Pascal
Седьмая Всероссийская Командная олимпиада школьников по программированию
Ограничение времени:
2 сек
Входной файл:
frame.in
Ограничение памяти:
64 Мб
Выходной файл:
frame.out
Условие
Картины художников-абстракционистов весьма необычны. На них часто изображены абсолютно непонятные предметы.
Один известный художник-абстракционист решил добавить своим картинам оригинальности следующим способом. Вместо
прямоугольных рамок, в которые обычно вставляются картины, он решил на ближайшей выставке использовать треугольные.
Однако все оказалось совсем не так просто. Художник изготовил рамку, поместил в нее картину и понял, что что-то не так.
Рамка получилась слишком широкой, и картина выглядела совсем не так ярко, как он ожидал.
Немного поразмыслив, художник понял, что то, насколько рамка "подходит" для картины, определяется площадью рамки.
Кроме этого он понял, что рамки надо не изготавливать самостоятельно, а покупать в специальном магазине. Заглянув в
прайс-лист магазина, он увидел, что для каждой рамки в нем указаны длины внешних сторон и ширина.
Поясним подробнее то, как выглядит треугольная рамка. Ее изготовление происходит следующим образом: берется доска
из красного дерева, имеющая форму треугольника со сторонами a, b и c. После этого стороны этого треугольника мысленно
сдвигаются внутрь него на расстояние d (измеряемое по перпендикуляру к соответствующей стороне). На точках пересечения
"сдвинутых" сторон строится маленький треугольник, который затем вырезается из исходного.
Пример рамки со сторонами a = 6, b = 8, c = 10 и шириной d = 1 показан на рисунке.
Помогите художнику по имеющимся в прайс-листе данным вычислить площадь рамки.
Формат входного файла
Входной файл содержит четыре целых числа a, b, c, d - длины внешних сторон рамки и ее ширину, соответственно.
Гарантируется, что треугольник со сторонами a, b и c. существует, и что в треугольнике есть точка, расстояние от которой
до ближайшей стороны строго больше d.
Формат выходного файла
В выходной файл выведите площадь рамки с точностью не меньше 10 − 5.
Седьмая Всероссийская Командная олимпиада школьников по программированию
Ограничение времени:
2 сек
Входной файл:
number.in
Ограничение памяти:
64 Мб
Выходной файл:
number.out
Условие
Вася написал на длинной полоске бумаги большое число и решил похвастаться своему старшему брату Пете этим достижением.
Но только он вышел из комнаты, чтобы позвать брата, как его сестра Катя вбежала в комнату и разрезала полоску бумаги на несколько частей.
В результате на каждой части оказалось одна или несколько идущих подряд цифр.
Теперь Вася не может вспомнить, какое именно число он написал. Только помнит, что оно было очень большое.
Чтобы утешить младшего брата, Петя решил выяснить, какое максимальное число могло быть написано на полоске бумаги перед разрезанием.
Помогите ему!
Формат входного файла
Входной файл содержит одну или более строк, каждая из которых содержит последовательность цифр.
Гарантируется, что хотя бы в одной строке первая цифра отлична от нуля.
Формат выходного файла
Выведите в выходной файл одну строку - максимальное число, которое могло быть написано на полоске перед разрезанием.
Ограничения
Количество строк во входном файле не превышает 100, каждая строка содержит от 1 до 100 цифр.
Седьмая Всероссийская Командная олимпиада школьников по программированию
Ограничение времени:
2 сек
Входной файл:
chess.in
Ограничение памяти:
64 Мб
Выходной файл:
chess.out
Условие
Известный частный сыщик поставил чашку с чаем на специальную подогревающую подставку, питающуюся от USB-порта
его компьютера, и приступил к обдумыванию очередного запутанного преступления. Через пару часов раздумий он понял,
что для разгадки этого дела достаточно определить, была ли на месте преступления шахматная доска.
Недавно он получил по электронной почте фотографию места преступления. Подозрительный фрагмент (тот, на котором
изображен предмет, похожий на шахматную доску) уже был скопирован в отдельный файл, но вдруг выяснилось, что,
поскольку фотография была сжата с потерей качества, некоторые пиксели на ней из белых или черных стали серыми.
Таким образом, определение того, является ли сфотографированный предмет шахматной доской, стало намного более сложным.
Все усложняется тем, что на фотографию могла попасть не вся шахматная доска, а лишь ее часть. Например, на
приведенном рисунке на фотографию попала часть доски, у которой каждое поле имеет длину стороны, равную трем пикселям.
Помогите частному сыщику в расследовании преступления. Напишите программу, которая определит, может ли
заданный фрагмент фотографии быть изображением части шахматной доски, и, если может, восстановит изображение шахматной
доски до сжатия.
Шахматная доска — это квадрат, разбитый на х2 (для некоторого х) равных квадратов — полей. Стороны полей параллельны
сторонам изображения. Длина стороны каждого поля шахматной доски выражается целым числом пикселей. Все пиксели,
принадлежащие одному полю, покрашены в один и тот же цвет — черный или белый. При этом соседние поля (поля, имеющие
общую сторону) покрашены в различные цвета.
Формат входного файла
Первая строка входного файла содержит два целых числа: m и n — размеры фрагмента фотографии в пикселях.
Следующие m строк содержат по n символов каждая, j-й символ i-й строки соответствует пикселю с координатами (i,j).
Символ "." (точка) означает белый пиксель, символ "*" - черный, символ "?" — серый.
Формат выходного файла
Если заданный фрагмент фотографии может быть изображением части шахматной доски, выведите в выходной файл слово "YES".
После этого выведите m строк по n символов в каждой. Они должны содержать изображение соответствующей части шахматной доски
в том же формате, что и во входном файле, только серые пиксели должны быть заменены на белые или черные.
Если решений несколько, выведите любое.
В противном случае выведите в выходной файл слово "NO".
