|
Забыли пароль? | ||||
| [задачи] [курсы] [олимпиады] [регистрация] | |||||
|
Задача B. Верхняя границаУ Ромы и Саши есть набор карточек с цифрами: для каждой цифры k от 0 до 9 имеется ck карточек с изображением цифры k. Саша хочет составить целое число, которое строго больше X. Рома дополнительно хочет, чтобы это число было как можно меньше. Число составляется из карточек по его десятичной записи. Определите, какое число им нужно составить или сообщите, что это невозможно. Входные данныеВ первой строке входного файла INPUT.TXT содержится целое неотрицательное число X, записанное в десятичной системе счисления без ведущих нулей. Число состоит не более, чем из 105 цифр. Во второй строке содержатся числа c0, c1, ..., c9 (0 ≤ ci ≤ 106). Выходные данныеВ выходной файл OUTPUT.TXT выведите искомое число без ведущих нулей. Если такое число невозможно составить, выведите «-1». Примеры
Задача C. Волшебные цветыЦветочник Стёпик посадил N волшебных цветков в своём саду. Высадил он их по кругу, и пронумеровал от 1 до N так, что первый и N-й соседи, а для 2 ≤ i ≤ N соседями являются цветы с номерами i и i−1. Каждый i-й цветок имеет свою высоту Hi. Почему цветы Стёпика волшебные? Потому что к концу дня они меняют свою высоту, а именно высота i-го цветка становится равна наименьшей из высот его соседей. Изменение высот происходит для всех цветков одновременно. Стёпик собирается уехать на K дней и ему интересно, какими будут высоты цветков к моменту его приезда? Входные данныеПервая строка входного файла INPUT.TXT содержит два целых числа N и K − количество цветков и количество дней соответственно (3 ≤ N ≤ 5×105; 0 ≤ K ≤ 109). Во второй строке содержатся N целых чисел Hi (1 ≤ Hi ≤ 109). Выходные данныеВ выходной файл OUTPUT.TXT выведите в одной строке N целых чисел − высоты цветков по истечении K дней. Примеры
Задача D. Двоичное упражнениеМаленький Бикарп очень любит степени двойки. Недавно он узнал о двоичной системе счисления и решил поупражняться на задачках по этой теме. Ему попалась задача о сложении двух чисел, где требовалось определить количество единиц в двоичной записи этой суммы. В этой задаче требовалось сложить числа 2x−1 и 2y−1. Пока Бикарп решает задачу на бумаге, напишите программу, которая быстро проверит его ответ. Входные данныеПервая строка входного файла INPUT.TXT содержит число x, вторая − y. Оба числа целые. (0 ≤ x, y ≤ 230). Выходные данныеВ выходной файл OUTPUT.TXT выведите количество единиц в двоичной записи требуемой суммы. Пример
Задача E. Stack Unwinding
Давид увлекается изучением своего любимого языка программирования. Для этого он иногда просматривает видео с различных курсов. На одном из них он познакомился с исключениями и теперь везде их Напомним, что в языке Давида, при завершении функции объекты удаляются в обратном порядке, а при срабатывании исключения, программа завершается (т.к. Давид забыл написать соответствующий обработчик), предварительно освобождая созданные ей объекты. Выполнение программы всегда начинается с функции main. Входные данныеВ нескольких строчках входного файла INPUT.TXT содержится псевдокод программы. Он представляет собой описание нескольких функций (не больше 10), каждая из которых задается следующим образом. Вначале записывается сигнатура функции. Для упрощения во всех программах сигнатура функции будет выглядеть как "void funcName() {" (без кавычек), где funcName – имя объявляемой функции. Затем до "}" описывается тело функции, в котором могут быть только следующие команды:
Все имена состоят только из английских букв и цифр. Код программы не превышает 10000 символов. Гарантируется, что в коде нет циклов (рекурсивных вызовов функций) и определение функции main является последним. Выходные данныеВ выходной файл OUTPUT.TXT требуется вывести последовательность создаваемых и удаляемых в программе Давида объектов. При создании объекта типа Type в отдельной строке нужно вывести Type(), при удалении – ∼Type(), возникновение исключения – throw. Пример
Задача F. ПробежкаХомячок Хома наконец-то получил в подарок долгожданный тренажёр – колесо для бега. Колесо представляет из себя два круга, соединённых N спицами. Спицы пронумерованы числами от 1 до N по часовой стрелке. Соседние спицы расположены на равном расстоянии друг от друга. Хома начинает пробежку так, что его передние лапки стоят на первой спице. Далее он делает K шагов таким образом, что на переход к следующей спице он тратит одну секунду. Сделав K шагов, он смотрит на какой спице он остановился: если это первая спица, то он завершает пробежку и слазит с колеса, а иначе отдыхает R секунд и повторяет процедуру снова. Хозяйка Хомы интересуется, сколько времени будет занимать одна такая пробежка? Входные данныеВходной файл INPUT.TXT содержит три целых числа N, K и R по одному в отдельной строке (1 ≤ N, K, R ≤ 2×109). Выходные данныеВ выходной файл OUTPUT.TXT выведите единственное число – сколько секунд потратит Хома на пробежку. Пример
Задача G. Три монетыЭто интерактивная задача. Перед вами стопка из N монет. В стопке есть все монеты номиналов от 1 до N, причём они упорядочены по возрастанию сверху-вниз. То есть, верхняя монета номиналом 1, а нижняя — N. Вес каждой монеты равен её номиналу. Некто заменил ровно три монеты в стопке на фальшивые — вес таких монет равен нулю. Вы можете спрашивать суммарный вес первых K монет сверху для любого 0 ≤ K ≤ N. Определите номиналы фальшивых монет не более чем за 32 вопроса, и тогда Некто подарит вам всю стопку монет. Протокол взаимодействияВначале на ввод подаётся число N — количество монет (3 ≤ N ≤ 109). Далее ваша программа должна выводить запросы вида «? K», где 0 ≤ K ≤ N. В ответ вы получите сумму весов первых K монет вверху стопки. Как только ваша программа будет готова сообщить ответ, выведите «! A B C», где 1 ≤ A, B, C ≤ N — различные номиналы фальшивых монет. После этого программа должна завершить работу. Пример
ПримечаниеДля корректной работы программы после каждой операции вывода данных выводите перевод строки, а также очищайте буфер вывода. Очистка буфера вывода производится следующим образом:
Задача H. КинозалОднажды Вася пришёл в известный кинотеатр «Прямая», чтобы посмотреть новый боевик. Когда он проходил к своему месту в зале, то ему пришлось потревожить некоторых людей, которые заняли свои места раньше него. Он был этим так расстроен, что решил в следующий раз заранее определить минимальное количество людей, которым он должен помешать. Известно, что кинозал имеет форму прямоугольника шириной W (количество мест в ряду) и высотой H (количество рядов). Каждая клетка внутри прямоугольника задаётся координатами (a, b) так, что 1 ≤ a ≤ H и 1 ≤ b ≤ W. Клетка может быть либо местом, на котором можно сидеть зрителю, либо быть часть прохода. Всего существует два типа проходов: вертикальный и горизонтальный, оба проходят от края до края. По проходам можно перемещаться свободно, не мешая зрителям. Дополнительно, по периметру зала тоже можно перемещаться свободно. Вам дано описание зала с указанием проходов и уже занятых мест. Определите минимальное количество человек, которое необходимо потревожить Васе, чтобы добраться до своего места. Помимо прохождения по проходам, Вася может двигаться вдоль любого ряда. Считается, что Вася тревожит зрителя, если он проходит через его место на пути к своему. Аналогичное движение в направлении, перпендикулярном рядам, невозможно. Однако, если номер ряда места Васи на единицу больше координаты горизонтального прохода, то Вася его может занять, не потревожив зрителей. В направлении уменьшения координаты ряда Васи относительно горизонтальных проходов Вася двигаться не может, так как ему мешают спинки кресел. Рассмотрим пример зрительного зала:
Здесь 9 рядов (H = 9) и 21 место в ряду (W =21). В зале помимо Васи 10 зрителей (обозначены кругами) со следующими координатами: (2,3), (9,7), (5,8), (1,9), (5,13), (1,15), (8,15), (5,17), (5,18), и (5,21). Место Васи обозначено смайликом и находится в координате (5,15). Также здесь три вертикальных прохода в координатах 5, 11, 19 и два горизонтальных прохода в координатах 3 и 7. Васе оптимально двигаться через вертикальный проход 11, потревожив всего одного зрителя (5,13). Вертикальные проходы Вася использовать не может. Но, если бы его ряд был на единицу меньше, то он смог бы через горизонтальный проход 3 занять свое место, не мешая другим зрителям. Входные данныеВ первой строке входного файла INPUT.TXT заданы четыре целых числа W, H, C и P (1 ≤ W, H ≤ 109, 0 ≤ C, P ≤ 105), где W и H — размеры кинозала, C — количество уже занятых мест, P — количество проходов. В следующих P строках описаны проходы. Горизонтальный проход описывается как «hor hi» (1 ≤ hi ≤ H), а вертикальный — «vert vi» (1 ≤ vi ≤ W). Затем в C строках записаны координаты (ai, bi) занятых мест (1 ≤ ai ≤ H, 1 ≤ b i ≤ W). Последняя строка содержит координаты места Васи в аналогичном формате. Гарантируется, что ни одно место не указано дважды, а так же то, что места не находятся в проходах. Выходные данныеВ выходной файл OUTPUT.TXT выведите целое число — минимальное количество людей, которое нужно потревожить Васе. Примеры
Задача I. Индикатор загрузкиДля отображения процесса загрузки файла часто используют индикатор в виде полоски, заполняющейся слева направо. Мы имеем дело с индикатором длиной в N пикселей. Если индикатор отображает K пикселей, то это значит, что хотя бы K/N-я часть файла загружена. При этом для уменьшения неопределённости заполняется максимальное возможное количество пикселей. Вам нужно вывести индикатор длиной в N пикселей в момент, когда загружено ровно P% файла. Входные данныеЕдинственная строка входного файла INPUT.TXT содержит два целых числа N и P (1 ≤ N ≤ 1000; 0 ≤ P ≤ 100). Выходные данныеВ выходной файл OUTPUT.TXT выведите индикатор загрузки, окружив его квадратными скобками. Заполненную часть индикатора следует обозначать символом «*» («звёздочка»), а пустую — «.» (точка). Примеры
Задача J. Заверните две!Петя как обычно шёл утром на работу по обычной дороге, как вдруг ему на глаза попалась новая шаурмичная. Он решил зайти в неё и запастись пищей на весь следующий день. Петя хочет купить ровно две шаурмы — на обед и ужин (не беспокойтесь, микроволновка на работе у Пети есть). Всего в шаурмичной существует N ингредиентов, пронумерованных от 1 до N, и M рецептов шаурмы. Каждый рецепт для удобства представляет из себя отрезок [Li, Ri], и означает, что в i-й рецепт входят ингредиенты с номерами от Li до Ri включительно. Петя быстрым взглядом ознакомился со всеми ингредиентами и оценил каждый i-й ингредиент целым числом Ai — насколько ему нравится этот продукт. Естественно, Петя хочет получить максимально возможное суммарное удовольствие от приёма пищи. Удовольствие от одной шаурмы равно сумме всех Ai входящих в неё ингредиентов. Так же, Петя хочет разнообразия — выбранные рецепты не должны иметь общего ингредиента. Помогите Пете с нелёгким выбором, определите, какие две шаурмы нужно заказать, чтобы условия были выполнены, а он в качестве благодарности угостит вас как-нибудь шаурмой. Входные данныеПервая строка входного файла INPUT.TXT содержит целое число N — количество ингредиентов (1 ≤ N ≤ 2×105). Во второй строке содержатся N целых чисел Ai (|Ai| ≤ 109). Третья строка содержит целое число M — количество рецептов (2 ≤ M ≤ 2×105. Следующие M строк содержат пары чисел Li и Ri — границы i-го отрезка (1 ≤ Li ≤ Ri ≤ N). Выходные данныеВ выходной файл OUTPUT.TXT выведите номера рецептов, которые стоит выбрать Пете. Если же выбрать невозможно, выведите «-1 -1». Примеры
Задача K. Сладкая ватаКак все вы знаете, решение олимпиадных задач на алгоритмы и структуры данных – дело весьма энергозатратное. Именно поэтому все участники Открытого личного первенства ИКИТ СФУ по программированию по окончании соревнований получают сладкую вату калорийностью C калорий. На олимпиаде участникам предлагается решить N задач, для решения каждой требуется потратить V калорий. Программист Федя будет участвовать в олимпиаде и собирается решить все задачи! Он хочет посчитать, хватит ли калорий, полученных из сладкой ваты, чтобы компенсировать калории, потраченные на решение всех задач. Помогите ему! Входные данныеПервая строка входного файла INPUT.TXT содержит три целых числа C, N и V (1 ≤ C, V ≤ 10 000, 1 ≤ N ≤ 15). Выходные данныеВ выходной файл OUTPUT.TXT выведите одно целое число – разницу между калорийностью ваты и калориями, необходимыми для решения всех задач олимпиады. Примеры
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
