Автор: | Кировская командная олимпиада 2001 года | Ограничение времени: | 5 сек | |
Входной файл: | c.in | Ограничение памяти: | 64 Мб | |
Выходной файл: | c.out |
Из правил проведения студенческого командного чемпионата мира по программированию ACM:
Когда команда считает, что она решила задачу, она может послать свое решение на проверку. Решение проверяется на наборе секретных тестов. Если хотя бы один из тестов не проходит, команде сообщается причина (неверный ответ, превышение предела времени и т.д.). Такое решение считается неверным и на результат команды никак не влияет.
Если же решение проходит все тесты, то данная задача считается решенной, и команде начисляется некоторое количество штрафного времени. Штрафное время — это время в минутах от начала тура до момента посылки правильного решения этой задачи на проверку плюс по 20 штрафных минут за каждую неверную попытку по этой задаче (до тех пор, пока решение не прошло все тесты, никакого штрафного времени за задачу не начисляется).
Команды ранжируются по числу решенных задач, а при одинаковом их числе — по штрафному времени (чем штрафное время меньше, тем лучше).
Задача:
Жюри точно уверено, что команда "Super solvers", известная своей непобедимостью, все равно за тур успеет решить все задачи, и, скорее всего, каждую из задач — с первой же попытки (то есть штрафное время за каждую задачу будет равно времени от начала тура до момента ее посылки на проверку). Конечно, жюри может попытаться усложнить задачи, однако оно не хочет этого делать, так как опасается, что в этом случае из остальных команд вообще никто ничего не решит.
Сама команда тоже прекрасно понимает, что ей по силам решить все задачи, поэтому ей все равно, в каком порядке решать задачи - и команда решила, что будет решать задачи по порядку, начиная с первой.
Среди членов жюри есть тренер этой команды. Он прознал про тактику, которой решила придерживаться команда, а также может примерно оценить время, которое потребуется команде для решения каждой задачи. Жюри прекрасно понимает, что уже никак не может повлиять на число решенных командой задач, но зато, учитывая тактику команды, жюри может влиять на штрафное время, которое получит команда, располагая задачи в разном порядке. В самом деле, если на тур предлагается две задачи, и на решение одной из них команда тратит 10 минут, а на решение второй - 20, то штрафное время команды, если задачи расположить именно в таком порядке, будет равно 40 минутам (первую задачу команда сдает на 10-й минуте тура, вторую - на 30, 10+30=40). Если же задачи расположить в обратном порядке, то штрафное время будет равно 50 (сначала команда потратит 20 минут, потом еще 10, то есть пошлет задачи на 20-й и 30-й минутах, и штрафное время будет равно 20+30=50).
Жюри хочет, чтобы штрафное время команды "Super solvers" было как можно больше (быть может, это даст хоть какой-то шанс другим командам). Помогите членам жюри расположить задачи в таком порядке.
Во входном файле записано сначала число N — количество задач на тур. Затем идет N натуральных чисел, каждое из которых не превышает 300. i-ое из этих чисел задает количество минут, которое (по прогнозу тренера) команда "Super solvers" потратит на решение задач номер i.
В выходной файл выведите N чисел, задающих номера задач в той нумерации, которая есть у жюри в данный момент, в том порядке, в каком задачи должны быть расположены на олимпиаде.
№ | Входной файл (c.in ) |
Выходной файл (c.out ) |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|
Автор: | А. Жуплев | Ограничение времени: | 1 сек | |
Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
Выходной файл: | output.txt |
Прожив 1000 лет, Гассан Абдуррахман ибн Хоттаб узнал, что из интернета можно скачивать файлы. Решив помочь другим пользователям, он сотворил собственный сервер с файлами. Поскольку сервер Хоттаба волшебный, любой файл скачивается с него мгновенно. Однако, после скачивания файла размером S мегабайт скачавший его компьютер отключается от сервера на S секунд.
В распоряжении шушанчиков имеется один компьютер, подключённый к интернету. Им требуется скачать N файлов, i-й файл размером si мегабайт. Шушанчики просят Вас рассчитать минимальное время, за которое можно скачать эти файлы с сервера Хоттабыча.
Во входном файле содержится число N — количество файлов, за которым следуют N чисел si — размеры файлов в мегабайтах.
В выходном файле должно содержаться единственное число — минимальное время скачивания всех файлов в секундах.
1 ≤ N ≤ 1000
1 ≤ si ≤ 1000
Все числа во входном файле целые
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|
Автор: | А. Жуплев | Ограничение времени: | 2 сек | |
Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
Выходной файл: | output.txt |
Одной из главных особенностей мультимедиа-проигрывателя, разрабатываемого юным программистом Васей, будет функция автоматического добавления файлов в список воспроизведения.
Изучив некоторые аналогичные программы, Вася решил реализовать следующий алгоритм: когда пользователь выбирает файл для воспроизведения, то вместе с этим файлом добавляются также все "похожие" на него файлы в алфавитном порядке. Файлы добавляются даже в случае, если они уже есть в списке воспроизведения. Файлы считаются "похожими", если их имена имеют (непустое) одинаковое начало, после которого идёт символ разделителя либо конец строки. Разделителями считаются символы ' ' (пробел, ASCII 32), '_' (подчёркивание, ASCII 95) и '-' (минус, ASCII 45).
Помогите Васе написать программу, которая принимает на входе список всех имеющихся файлов, а также список файлов, выбранных пользователем для воспроизведения, и выдаёт список воспроизведения, получающийся в результате работы описанного алгоритма.
Выходной файл должен содержать итоговый список имён файлов (по одному в строке).
1 ≤ N ≤ 100; 0 ≤ M ≤ 100. Все имена файлов различны, состоят из маленьких латинских букв, цифр и разделителей и имеют длину от 1 до 100 символов.
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
Входной файл: | input.txt | Ограничение времени: | 5 сек | |
Выходной файл: | output.txt | Ограничение памяти: | 64 Мб |
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
Входной файл: | input.txt | Ограничение времени: | 2 сек | |
Выходной файл: | output.txt | Ограничение памяти: | 8 Мб |
K-й порядковой статистикой N-элементного массива называется число Аk, которое будет стоять на K-м месте после сортировки этого массива по возрастанию.
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
Входной файл: | input.txt | Ограничение времени: | 5 сек | |
Выходной файл: | output.txt | Ограничение памяти: | 64 Мб |
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
Автор: | VI Всероссийская командная олимпиада школьников по программированию | Ограничение времени: | 2 сек | |
Входной файл: | numbers.in | Ограничение памяти: | 64 Мб | |
Выходной файл: | numbers.out |
При расследовании дорожно-транспортных происшествий часто возникают проблемы с розыском автомобилей, водители которых покинули место происшествия.
Получение свидетельских показаний — непростая работа. Ситуация осложняется тем, что очень часто свидетели могут только приблизительно вспомнить номер автомобиля. При этом с большой вероятностью опрашиваемый может перепутать порядок цифр или букв в номере.
По полученному от свидетеля происшествия номеру, подсчитайте, сколько различных номеров может получиться из него перестановкой букв и/или цифр, а также выведите все такие номера.
Напомним, что автомобильные номера в России состоят из трех букв и трех цифр, упорядоченных следующим образом: буква, три цифры, затем две буквы. Фрагмент номера, который идентифицирует регион, в котором зарегистрирован автомобиль, мы будем игнорировать.
В номере могут использоваться следующие буквы: "A", "B", "C", "E", "H", "K", "M", "O", "P", "T", "X", "Y" (эти буквы имеют схожие по написанию аналоги как в русском, так и в латинском алфавите). В этой задаче во входном файле будут использоваться буквы латинского алфавита.
Входной файл содержит одну строку, которая представляет собой корректный автомобильный номер.
№ | Входной файл (numbers.in ) |
Выходной файл (numbers.out ) |
---|---|---|
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 |
|
|
Входной файл: | sum.in | Ограничение времени: | 2 сек | |
Выходной файл: | sum.out | Ограничение памяти: | 256 Мб |
Первая строка входного файла содержит два целых числа N и K — число чисел в массиве и количество запросов. (1 ≤ N ≤ 100 000), (0 ≤ K ≤ 100 000). Следующие K строк содержат запросы:
A l r x— присвоить элементам массива с позициями от l до r значение x (1 ≤ l ≤ r ≤ N, 0 ≤ x ≤ 109)
Q l r— найти сумму чисел в массиве на позициях от l до r. (1 ≤ l ≤ r ≤ N)
Изначально массив заполнен нулями.
На каждый запрос вида
Q l rнужно вывести единственное число — сумму на отрезке.
№ | Входной файл (sum.in ) |
Выходной файл (sum.out ) |
---|---|---|
1 |
|
|
Author: | - | Time limit: | 1 sec | |
Input file: | input.txt | Memory limit: | 256 Mb | |
Output file: | output.txt |
Имеется трёхмерный массив чисел. Поступают запросы двух видов. Запрос первого вида заменяет значение в заданной ячейке на заданную величину. Запрос второго вида требует вычисления суммы значений в ячеках заданного параллелепиппеда.
Требуется написать программу, обрабатывающую запросы в порядке их перечисления, и выводящую на печать ответы на запросы второго вида.
В первой строке входного файла находится целое число n — общее количество запросов.
Далее следует n строк, содержащих запросы. В начале каждой строки находится число 1 или 2 — тип запроса.
Для запросов первого типа далее в строке содержатся целые числа x, y, z, value — координаты ячейки и новое значение в ней.
Для запросов второго типа далее в строке содержатся целые числа x1, y1, z1, x1, y1, z1 — координаты параллелепиппеда, для которого следет предоставить ответ на запрос.
Для каждого запроса второго типа следует вывести единственное число — ответ на запрос.
1 ≤ n ≤ 100000;
1 ≤ x, y, z, x1, y1, z1, x2, y2, z2 ≤ 100;
0 ≤ 232 − 1;
No. | Input file (input.txt ) |
Output file (output.txt ) |
---|---|---|
1 |
|
|
Автор: | Виртуальная реальность | Ограничение времени: | 2 сек | |
Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
Выходной файл: | output.txt |
Виртуальный студсовет принял решение провести митинг против свободы слова. В связи с этим встал вопрос о выборе председателя. В студсовете полно народу, и не из кого выбрать. Посовещавшись, виртуальные персонажи занумеровали себя и для персонажа с номером i определили следующие числа:
Считается, что, i-й персонаж является кандидатом на должность председателя в том и только том случае, когда для него не найдётся такого j-того персонажа, что одновременно mj > mi, pj > pi, tj > ti.
Напишите программу, составляющую список кандидатов на роль председателя.
Входной файл содержит натуральное число n — количество персонажей. Далее следует n троек натуральных чисел mi pi ti.
Требуется вывести в выходной файл номера отобранных персонажей в порядке возрастания.
1 ≤ n ≤ 105
1 ≤ mi, pi, ti ≤ 109
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
Входной файл: | input.txt | Ограничение времени: | 1 сек | |
Выходной файл: | output.txt | Ограничение памяти: | 64 Мб |
Дан квадратный лабиринт, размером N × N, координаты точки входа и точки выхода. Определите минимальное расстояние от входа до выхода.
В выходном файле должно содержаться единственное число — минимальное расстояние. Лабиринт проходим.
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
Автор: | А. Жуплев | Ограничение времени: | 1 сек | |
Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
Выходной файл: | output.txt |
Одной из номинаций марсианского весеннего турнира юных программистов является "исследование лабиринта". Каждый участник этой номинации помещается в настоящий лабиринт и получает определённое задание — например, как можно быстрее попасть в указанную точку лабиринта.
Для строительства лабиринта жюри турнира использует кубические блоки из марсианского пластика. Лабиринт строится по заранее разработанной схеме, изображающей пустые клетки и клетки с блоками. Участник может перемещаться из клетки в пустую соседнюю клетку, имеющую с текущей клеткой общую сторону.
Взглянув на схему лабиринта, один из членов жюри обнаружил, что, если убрать некоторые блоки, то участники этого не заметят, поскольку, из какой бы изначально пустой клетки они не начинали свой путь, они не смогут попасть в клетки, занятые этими блоками. На основе сделанного наблюдения жюри желает сократить затраты на строительство лабиринта.
Напишите программу, получающую на входе описание лабиринта, и генерирующую новый лабиринт, состоящий из минимального количества блоков. При этом для каждой клетки нового лабиринта, которая была пустой в старом лабиринте, множество достижимых из неё клеток должно совпадать для обоих лабиринтов.
Первая строка входного файла содержит два целых числа — N M.
Далее идут N строк по M символов, описывающие лабиринт:
Выходной файл должен содержать N строк по M символов — описание нового оптимизированного лабиринта в формате, идентичном входному.
1 ≤ N, M ≤ 100
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|
Автор: | А. Кленин, М. Рожков | Ограничение времени: | 2 сек | |
Входной файл: | input.txt | Ограничение памяти: | 4 Мб | |
Выходной файл: | output.txt |
Лабиринт размером N x N клеток состоит из стенок, обозначенных символом '#' (ASCII 35), и проходов, обозначенных символом '.' (ASCII 46). В различных клетках лабиринта находятся два путешественника, потерявшие друг друга. Каждый из них полагает, что сможет найти товарища, если будет двигаться по лабиринту в соответствии со своим планом. Первый путешественник на каждую секунду делает шаг вперёд на одну клетку, если это возможно, либо поворачивает направо, если впереди стена. Второй путешественник действует аналогично, но поворачивает налево.
Требуется определить, встретятся ли когда-нибудь путешественники, и, если да, то после скольки шагов. Первоначальные позиции путешественников заданы координатами (x, y) и направлением d — числом 1, 2, 3, 4 для севера, востока, юга и запада соответственно. Позиция (1, 1) находится в северо-западном углу лабиринта.
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|
Входной файл: | input.txt | Ограничение времени: | 2 сек | |
Выходной файл: | output.txt | Ограничение памяти: | 256 Мб |
В первой строке входного файла записано число N — количество гвоздиков (2 ≤ N ≤ 100). В следующей строке записано N чисел — координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10 000).
В выходной файл нужно вывести единственное число — минимальную суммарную длину всех ниточек.
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
Входной файл: | input.txt | Ограничение времени: | 2 сек | |
Выходной файл: | output.txt | Ограничение памяти: | 256 Мб |
У лестницы n ступенек, пронумерованных числами 1, 2, ... , n снизу вверх. На каждой ступеньке написано число. Начиная с подножия лестницы (его можно считать ступенькой с номером 0), требуется взобраться на самый верх (ступеньку с номером n). За один шаг можно подниматься на одну или на две ступеньки. После подъёма числа, записанные на посещённых ступеньках, складываются. Нужно подняться по лестнице так, чтобы сумма этих чисел была как можно больше.
В первой строке входного файла записано целое число n (1 ⩽ n ⩽ 100). Во второй строке заданы целые числа a1, a2, ... , an через пробел ( − 10 000 ⩽ ai ⩽ 10 000) "--- это числа, записанные на ступеньках.
В первой строке выходного файла выведите одно число "--- максимальную сумму, которую можно получить, поднявшись по данной лестнице.
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|
Author: | StdAlg | Time limit: | 1 sec | |
Input file: | input.txt | Memory limit: | 256 Mb | |
Output file: | output.txt |
a
'
to 'z
' and spaces.
No. | Input file (input.txt ) |
Output file (output.txt ) |
---|---|---|
1 |
|
|
Автор: | A. Klenin | Ограничение времени: | 5 сек | |
Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
Выходной файл: | output.txt |
Дана последовательность целых чисел. Каждое прочитанное число обрабатывается следующим образом:
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|