Алгоритмы(1657 задач)
Структуры данных(279 задач)
Интерактивные задачи(17 задач)
Другое(54 задач)
Окружная олимпиада(18 задач)
Региональный этап(109 задач)
Заключительный этап(97 задач)
Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось \(n\) дипломов, причём, как оказалось, все они имели одинаковые размеры: \(w\) — в ширину и \(h\) — в высоту. Сейчас Петя учится в одном из лучших российских университетов и живёт в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить её к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещён строго в прямоугольнике размером \(w\) на \(h\). Дипломы запрещается поворачивать на 90 градусов. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек. Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов.
Входной файл содержит три целых числа: \(w\), \(h\), \(n\) (\(1\le w,h,n\le 10^9\)).
В выходной файл необходимо вывести ответ на поставленную задачу.
2 3 10
9
1 1 1
1
Недавно на уроке информатики ученики одного из классов изучили булевы функции. Напомним, что булева функция \(f\) сопоставляет значениям двух булевых аргументов, каждый из которых может быть равен 0 или 1, третье булево значение, называемое результатом. Для учеников, которые выразили желание более подробно изучать эту тему, учительница информатики на дополнительном уроке ввела в рассмотрение понятие цепного вычисления булевой функции \(f\).
Если задана булева функция \(f\) и набор из \(N\) булевых значений \(a_1,a_2,\ldots,a_N\), то результат цепного вычисления этой булевой функции определяется следующим образом:
* если \(N=1\), то он равен \(a_1\);
* если \(N>1\), то он равен результату цепного вычисления булевой функции \(f\) для набора из \((N-1)\) булевого значения \(f(a_1,a_2),a_3,\ldots,a_N\), который получается путём замены первых двух булевых значений в наборе из \(N\) булевых значений на единственное булево значение — результат вычисления функции \(f\) от \(a_1\) и \(a_2\).
Например, если изначально задано три булевых значения: \(a_1=0\), \(a_2=1\), \(a_3=0\), а функция \(f\) — ИЛИ (OR), то после первого шага получается два булевых значения — (0 OR 1) и 0, то есть 1 и 0. После второго (и последнего) шага получается результат цепного вычисления, равный 1, так как 1 OR 0 = 1.
В конце дополнительного урока учительница информатики написала на доске булеву функцию \(f\) и попросила одного из учеников выбрать такие \(N\) булевых значений \(a_i\), чтобы результат цепного вычисления этой функции был равен единице. Более того, она попросила найти такой набор булевых значений, в котором число единиц было бы как можно бо́льшим.
Требуется написать программу, которая решала бы поставленную учительницей задачу.
Первая строка входного файла содержит одно натуральное число \(N\) (\(2\le N\le100\,000\)).
Вторая строка входного файла содержит описание булевой функции в виде четырёх чисел, каждое из которых — ноль или единица. Первое из них есть результат вычисления функции в случае, если оба аргумента — нули, второе — результат в случае, если первый аргумент — ноль, второй — единица, третье — результат в случае, если первый аргумент — единица, второй — ноль, а четвёртый — в случае, если оба аргумента — единицы.
В выходной файл необходимо вывести строку из \(N\) символов, определяющих искомый набор булевых \(a_i\) с максимально возможным числом единиц. Если ответов несколько, требуется вывести любой из них. Если такого набора не существует, выведите в выходной файл фразу «No solution».
В первом примере процесс вычисления цепного значения булевой функции \(f\) происходит следующим образом: \(1011\to111\to01\to1\)
Во втором примере вычисление цепного значения булевой функции \(f\) происходит следующим образом: \(11111\to0111\to111\to01\to1\)
В третьем примере получить цепное значение булевой функции \(f\), равное 1, невозможно.
4 0110
1011
5 0100
11111
6 0000
No solution
К 2110 году город Флэтбург, являясь одним из крупнейших городов мира, не имеет обходной автомагистрали, что является существенным препятствием для его развития как крупнейшего транспортного центра мирового значения. В связи с этим ещё в 2065 году при разработке Генерального плана развития Флэтбурга была определена необходимость строительства кольцевой автомобильной дороги.
В Генеральном плане также были обозначены требования к этой дороге. Она должна соответствовать статусу кольцевой — иметь форму окружности. Кроме этого, четыре крупные достопримечательности Флэтбурга должны быть в одинаковой транспортной доступности от дороги. Это предполагается обеспечить тем, что они будут находиться на равном расстоянии от неё. Расстоянием от точки расположения достопримечательности до дороги называется наименьшее из расстояний от этой точки до некоторой точки, принадлежащей окружности автодороги.
Требуется написать программу, которая вычислит число возможных планов постройки кольцевой автомобильной дороги с соблюдением указанных требований и найдёт такой план, для которого длина дороги будет минимальной. Гарантируется, что хотя бы один план постройки существует.
Входной файл содержит четыре строки. Каждая из них содержит по два целых числа: \(x_i\) и \(y_i\) — координаты места расположения достопримечательности. Первая строка описывает первую достопримечательность, вторая — вторую, третья — третью, четвёртая — четвёртую. Никакие две достопримечательности не находятся в одной точке.
Все числа во входном файле не превосходят 100 по абсолютной величине.
В первой строке выходного файла требуется вывести число возможных планов постройки кольцевой автомобильной дороги. Если таких планов бесконечно много, необходимо вывести в первой строке выходного файла слово Infinity.
На второй строке требуется вывести координаты центра дороги минимальной длины и её радиус. Если существует несколько разных способов построения дороги минимальной длины, необходимо вывести координаты центра и радиус любой из них. Координаты центра и радиус должны быть выведены с точностью не хуже \(10^{-5}\) и не должны превышать \(10^9\). Гарантируется, что существует хотя бы один план с такими параметрами.
0 0 0 1 1 0 2 2
7 1.5 0.5 1.14412281
0 0 0 1 1 0 1 1
Infinity 0.5 0.5 0.0
Миша уже научился хорошо фотографировать и недавно увлекся программированием. Первая программа, которую он написал, позволяет формировать негатив чёрно-белого изображения.
Бинарное чёрно-белое изображение — это прямоугольник, состоящий из пикселей, каждый из которых может быть либо чёрным, либо белым. Негатив такого изображения получается путём замены каждого чёрного пикселя на белый, а каждого белого пикселя — на чёрный.
Миша, как начинающий программист, написал свою программу с ошибкой, поэтому в результате её исполнения мог получаться некорректный негатив. Для того чтобы оценить уровень несоответствия получаемого негатива исходному изображению, Миша начал тестировать свою программу.
В качестве входных данных он использовал исходные изображения. Сформированные программой негативы он начал тщательно анализировать, каждый раз определяя число пикселей негатива, которые получены с ошибкой.
Требуется написать программу, которая в качестве входных данных использует исходное бинарное чёрно-белое изображение и полученный Мишиной программой негатив, и на основе этого определяет количество пикселей, в которых допущена ошибка.
Первая строка входного файла содержит целые числа \(n\) и \(m\) (\(1\le n,m\le100\)) — высоту и ширину исходного изображения (в пикселях).
Последующие \(n\) строк содержат описание исходного изображения. Каждая строка состоит из \(m\) символов «B» и «W». Символ «B» соответствует чёрному пикселю, а символ «W» — белому.
Далее следует пустая строка, а после неё — описание выведенного Мишиной программой изображения в том же формате, что и исходное изображение.
В выходной файл необходимо вывести число пикселей негатива, которые неправильно сформированы Мишиной программой.
3 4 WBBW BBBB WBBW BWWW WWWB BWWB
2
2 2 BW BB WW BW
2
С детства Максим был неплохим музыкантом и мастером на все руки. Недавно он самостоятельно сделал несложный перкуссионный музыкальный инструмент — треугольник. Ему нужно узнать, какова частота звука, издаваемого его инструментом.
У Максима есть профессиональный музыкальный тюнер, с помощью которого можно проигрывать ноту с заданной частотой. Максим действует следующим образом: он включает на тюнере ноты с разными частотами и для каждой ноты на слух определяет, ближе или дальше она к издаваемому треугольником звуку, чем предыдущая нота. Поскольку слух у Максима абсолютный, он определяет это всегда абсолютно верно.
Вам Максим показал запись, в которой приведена последовательность частот, выставляемых им на тюнере, и про каждую ноту, начиная со второй, записано — ближе или дальше она к звуку треугольника, чем предыдущая нота. Заранее известно, что частота звучания треугольника Максима составляет не менее 30 герц и не более 4000 герц.
Требуется написать программу, которая определяет, в каком интервале может находиться частота звучания треугольника.
Первая строка входного файла содержит целое число \(n\) — количество нот, которые воспроизводил Максим с помощью тюнера (\(2\le n\le1000\)). Последующие \(n\) строк содержат записи Максима, причём каждая строка содержит две компоненты: вещественное число \(f_i\) — частоту, выставленную на тюнере, в герцах (\(30\le f_i\le4000\)), и слово «closer» или слово «further» для каждой частоты, кроме первой.
Слово «closer» означает, что частота данной ноты ближе к частоте звучания треугольника, чем частота предыдущей ноты, что формально описывается соотношением: \(|f_i-f_{треуг.}|<|f_{i-1}-f_{треуг.}|\).
Слово «further» означает, что частота данной ноты дальше, чем предыдущая.
Если оказалось, что очередная нота так же близка к звуку треугольника, как и предыдущая нота, то Максим мог записать любое из двух указанных выше слов.
Гарантируется, что результаты, полученные Максимом, непротиворечивы.
В выходной файл необходимо вывести через пробел два вещественных числа — наименьшее и наибольшее возможное значение частоты звучания треугольника, изготовленного Максимом. Числа должны быть выведены с точностью не хуже \(10^{-6}\).
3 440 220 closer 300 further
30.0 260.0
4 554 880 further 440 closer 622 closer
531.0 660.0