Author: | StdAlg | Time limit: | 3 sec | |
Input file: | input.txt | Memory limit: | 512 Mb | |
Output file: | output.txt |
No. | Input file (input.txt ) |
Output file (output.txt ) |
---|---|---|
1 |
|
|
Author: | StdAlg | Time limit: | 1 sec | |
Input file: | input.txt | Memory limit: | 512 Mb | |
Output file: | output.txt |
No. | Input file (input.txt ) |
Output file (output.txt ) |
---|---|---|
1 |
|
|
Автор: | StdAlg | Ограничение времени: | 3 сек | |
Входной файл: | input.txt | Ограничение памяти: | 512 Мб | |
Выходной файл: | output.txt |
K-ой порядковой статистикой N-элементной последовательности AN называется число AK, которое будет стоять на K-ом месте после упорядочивания элементов этой последовательности по возрастанию.
Последовательность AN задаётся следующим образом. A1 = P, Ai = (Ai − 1 ⋅ Q) mod V.
Во входном файле содержатся целые числа Q V P N K
В выходном файле должно содержаться единственное число — K-ая порядковая статистика исходной последовательности.
V, Q ≠ 0
0 ≤ Q ⋅ V, Q ⋅ P ≤ 231 − 1
1 ≤ K ≤ N ≤ 4 ⋅ 107
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
Автор: | А. Кленин, И. Бураго | Ограничение времени: | 2 сек | |
Входной файл: | input.txt | Ограничение памяти: | 512 Мб | |
Выходной файл: | output.txt |
На улице длиной в 100 метров установлено N фонарей высотой y1, y2, …, yN метров на расстоянии x1, x2, … xN метров от начала улицы. Форма отражателей такова, что свет каждого фонаря распространяется в пределах конуса с углом при вершине 90°.
Требуется определить яркость самого освещённого участка улицы, т.е. максимальное количество фонарей, освещающих один и тот же участок.№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
Автор: | Известная | Ограничение времени: | 2 сек | |
Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
Выходной файл: | output.txt |
Дана последовательность из N целых чисел. Для каждого числа вывести ближайшее к нему справа в этой последовательности, которое будет больше него. Для чисел, которым найти ближайшее большее не удалось, вывести сами эти числа.
Входной файл содержит целое число N за которым следует N целых чисел ai - исходная последовательность.
В выходной файл необходимо вывести N целых чисел bi, таких что bi является ответом на задачу для числа ai.
1 ≤ N ≤ 106
|ai| ≤ 109
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|
Автор: | И. Олейников | Ограничение времени: | 2 сек | |
Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
Выходной файл: | output.txt |
По мотивам романа А. и Б. Стругацких “Понедельник начинается в субботу”.
Очередной понедельник выдался в НИИЧАВО (Научно-Исследовательский Институт ЧАродейства и ВОлшебства) на удивление беспокойным. Началось все с проблем в отделе исследования живой, мёртвой и водопроводной воды, куда на прошлой неделе завезли новый аквариум. Туда и вошел Привалов в самый интересный момент беседы между Амвросием Амбруазовичем Выбегалло и заведующим отделом смысла жизни Кристобалем Хозевичем Хунтой. Сейчас Кристобаль Хозевич в красках описывал, какие могут возникнуть повреждения всей новейшей системы безопасности, недавно установленной в институте, от всего того количества воды, которым сейчас затапливался его отдел.
— Подождите, остановил его речь Выбегалло, вот закончим проверку и выключим воду.
— Да какая же это проверка, это же чистой воды саботаж! — возмущался Хунта, вот сейчас заделаю все дырки в вашем аквариуме, и тогда будем разговаривать.
— Нет, это категорически невозможно! — Возражал Выбегалло, — как вы себе это представляете? Мы проводим важнейший эксперимент!
— Может быть, объясните, что здесь все-таки происходит? - вмешался в разговор Привалов
— Позвольте, я объясню, начал было Выбегалло, но Кристобаль Хозевич не дал ему закончить, и, сделав руками несколько пассов, произнес, — вот теперь порядок, ничего не вливается и не выливается, можете объяснять.
— Ну, раз вы все-таки запечатали отверстия, то спешки особой нет, — продолжил Амвросий Амбруазович, — на прошлой неделе мне, доставили новый большой аквариум, необычной конструкции, а если быть точным, с несколькими прямоугольными отверстиями на лицевой стороне, вот посмотрите.
Привалов, наконец, осмотрел новый аквариум. Он представлял собой прямоугольный параллелепипед размерами W × H × L метров без верхней крышки, на лицевой стороне которого было вырезано N квадратных отверстий c длиной стороны ai метров. Сверху над аквариумом висела большая труба, через которую в него поступало M кубических метров воды в секунду.
— Так вот, — продолжил Выбегалло, — до появления здесь Кристобаля Хозевича мы проводили эксперимент, целью которого было определить уровень воды в этом аквариуме при заданной конфигурации отверстий.
— А более сухого способа вы не нашли, — вставил свою реплику Хунта
Привалов, как программист, прекрасно понимал, что для таких экспериментов вовсе не обязательно затапливать пол-института. Нужно лишь определить скорость вытекания воды из отверстий и описать весь эксперимент очень простой компьютерной моделью. Свои соображения он и изложил собравшимся.
— Замечательная идея, молодой человек, — произнес Выбегалло, — это ж сколько средств то можно сэкономить, да и воду тратить не придется.
Через несколько минут он передал Привалову формулу расчета потока воды из отверстий в аквариуме. Поскольку аквариум до эксперимента был специально заколдован, формула была оказалась простой: через отверстие площадью b квадратных метров в одну секунду будет вытекать V × b кубических метров воды.
В начале эксперимента аквариум пуст. Через некоторое время после того, как
из трубы начнёт поступать вода, уровень в воды в аквариуме стабилизируется
(либо аквариум переполнится).
Теперь осталось только написать программу, определяющую высоту стабильного уровня воды.
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
Автор: | Центральная предметно-методическая комиссия по информатике | Ограничение времени: | 2 сек | |
Входной файл: | diploma.in | Ограничение памяти: | 64 Мб | |
Выходной файл: | diploma.out |
Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось N дипломов, причем, как оказалось, все они имели одинаковые размеры: W — в ширину и H — в высоту.
Сейчас Петя учится в одном из лучших российских университетов и живет в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить ее к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещен строго в прямоугольнике размером W на H. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек.
Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов.
Решения, правильно работающие только при W, H, N ≤ 1000, будут оцениваться в 40 баллов.
Входной файл содержит три целых числа: W, H, N
В выходной файл необходимо вывести ответ на поставленную задачу.
1 ≤ W, H, N ≤ 109
№ | Входной файл (diploma.in ) |
Выходной файл (diploma.out ) |
---|---|---|
1 |
|
|
Автор: | A. Klenin | Ограничение времени: | 8 сек | |
Входной файл: | input.txt | Ограничение памяти: | 4 Мб | |
Выходной файл: | output.txt |
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
Автор: | А. Жуплев, А. Кленин | Ограничение времени: | 1 сек | |
Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
Выходной файл: | output.txt |
Крокодил Гена решил поступить в университет. Для поступления ему нужно пройти тест, состоящий из Q вопросов. На каждый из них можно ответить либо "Да", либо "Нет". Количество баллов, получаемых абитуриентом за тест, равно количеству данных им правильных ответов. Все абитуриенты проходят тест с одними и теми же вопросами.
Поскольку Гена не подготовился к тесту, он решил схитрить. Для этого он подговорил P шушанчиков, чтобы они прошли тест до него. Каждый шушанчик запомнил, как он отвечал на каждый из вопросов, и сколько баллов получил.
По этим данным Гена должен определить правильные ответы.
В первой строке входного файла содержатся числа P Q. Далее следует P описаний шушанчиков, по две строки на описание:
В выходном файле должна содержаться единственная строка, состоящая из Q символов + (ASCII 43) или - (ASCII 45) — правильные ответы к тесту. Если существует несколько вариантов правильных ответов, вывести любой из них. Так, во втором примере допустим также ответ -+++.
1 ≤ P ≤ 1000, 1 ≤ Q ≤ 15
Исходные данные таковы, что существует хотя бы один вариант решения.№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|
Автор: | А. Кленин | Ограничение времени: | 1 сек | |
Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
Выходной файл: | output.txt |
Имеется два компьютера с одинаковой производительностью и N программ, которые необходимо выполнить. Известно, что i-я программа требует для выполнения на любом из компьютеров Ti секунд. Программы можно выполнять в любом порядке, но прерывать однажды запущенную программу нельзя. Сразу после окончания одной программы можно запускать следующую.
Требуется распределить программы между компьютерами таким образом, чтобы время на их выполнение оказалось наименьшим. Например, программы длительностью 7, 10, 3, 5, 6 можно выполнить за 16 секунд, если на первом компьютере выполнять вторую и четвертую программу, а на втором — остальные три.
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
Автор: | - | Ограничение времени: | 1 сек | |
Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
Выходной файл: | output.txt |
Найдите наибольшую общую подпоследовательность двух строк.
В первой строке находится первая строка, во второй строке находится вторая строка. Строки состоят только из маленьких латинских букв.
Вывести наибольшую общую подпоследовательность. Если решений несколько, вывести любое.
Длина каждой строки не менее 1 и не превосходят 1000.
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
Автор: | А. Кленин, краевая олимпиада 2001 г. | Ограничение времени: | 2 сек | |
Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
Выходной файл: | output.txt |
Начинающий бизнесмен Вася копит в свинье-копилке деньги на открытие собственного дела.
Как известно, количество денег в копилке можно определить, только разбив ее.
Однако Вася не хочет разбивать копилку раньше, чем будет накоплена требуемая сумма.
Друг подсказал Васе, что можно оценить минимальное количество денег в копилке, зная вес пустой копилки и вес копилки с монетами.
Дано E — вес пустой копилки, F — вес копилки с монетами, N — количество достоинств монет, Ci и Wi — достоинство и вес каждого вида монет (1 ≤ i ≤ N). Требуется определить минимальную сумму, которая может содержаться в копилке.
В первой строке входного файла содержатся числа E F N. В следующих N строках находятся по два числа — Ci Wi. Все числа во входном файле — целые.
В выходном файле должно содержаться одно число — минимальная сумма, накопленная в копилке. Если заданный вес копилки F не может быть достигнут с монетами заданного типа, то в выходной файл следует записать число − 1.
1 ≤ E ≤ F ≤ 10000; 1 ≤ N ≤ 100
1 ≤ Ci ≤ 10000; 1 ≤ Wi ≤ 10000
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|
Автор: | И. Олейников | Ограничение времени: | 1 сек | |
Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
Выходной файл: | output.txt |
Отдел инновационных технологий фирмы "Division Computers" решил, что повысить производительность в написании программ можно, если использовать модульное программирование, т.е. когда когда каждый программист пишет свою часть отдельно.
Когда все программисты сдали в отдел свою работу, выяснилось, что некоторым модулям для правильного функционирования требуются другие модули, при этом если i-тому модулю нужен j-тый, то и наоборот j-тому модулю нужен i-тый. Вам, как одному из программистов отдела, поручено написать программу, которая по сведениям о связях между модулями определила бы, сколько минимальных программ можно из них собрать. Минимальной считается программа, которую нельзя разделить на более мелкие части.
Входной файл содержит числа N и M — соответственно число модулей и связей между ними, за которыми следуют M пар чисел ai aj, означающие, что i-тый и j-тый модули не могут функционировать друг без друга.
Выходной файл должен содержать число получившихся после сборки программ.
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
Входной файл: | input.txt | Ограничение времени: | 1 сек | |
Выходной файл: | output.txt | Ограничение памяти: | 256 Мб |
Дан неориентированный граф. Проверьте, является ли он деревом.
В первой строке входного файла заданы через пробел два целых числа n и m — количество вершин и рёбер в графе, соответственно. В следующих m строках заданы рёбра; i-я из этих строк содержит два целых числа ui и vi через пробел — номера концов i-го ребра. Граф не содержит петель и кратных рёбер.
В первой строке выходного файла выведите YES
, если граф является
деревом, и NO
в противном случае.
1 ≤ n ≤ 105
0 ≤ m ≤ 105
1 ≤ ui, vi ≤ n
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|
Входной файл: | input.txt | Ограничение времени: | 1 сек | |
Выходной файл: | output.txt | Ограничение памяти: | 64 Мб |
Дан квадратный лабиринт, размером N × N, координаты точки входа и точки выхода. Определите минимальное расстояние от входа до выхода.
В выходном файле должно содержаться единственное число — минимальное расстояние. Лабиринт проходим.
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|