Школа программиста
Резервная копия - VPS Hoster 

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Личное первенство по программированию среди школьников ИКИТ СФУ
(27-28 апреля 2019 г.)


Задача A. Архимед

(Время: 1 сек. Память: 16 Мб)

Недавно Виталька прошел в школе закон Архимеда, в котором говорится, что на тело, погружённое в жидкость, действует выталкивающая или подъёмная сила, равная весу объёма жидкости, вытесненного частью тела, погружённой в жидкость. Так как Виталька любит придумывать различные задачки, то он сразу составил задачу (интересную на его взгляд), в которой по заданным размерам бассейна и начальному объему воды V, нужно определить объем воды, которая выльется через края, если в бассейн положить N предметов, каждый из которых имеет объем Vi.

Можно считать, что предметы укладываются максимально плотно и никакой предмет не выходит за края бассейна, если в бассейне еще есть свободное место (место, занятое либо водой, либо воздухом). Плотность предметов выше плотности воды (предметы не всплывают). Никакие предметы не погружаются в воду вместе с воздухом, то есть нет полых предметов (например, таких как кружка).

Входные данные

В первой строке входного файла INPUT.TXT заданы целые числа W, H, L, V и N (1 ≤ W, H, L ≤ 1000; 0 ≤ V ≤ W×H×L; 1 ≤ N ≤ 100), где W, H, L - ширина, глубина и длина бассейна.

Во второй строке содержатся N целых чисел - Vi (1 ≤ Vi ≤ 1000).

Выходные данные

В выходной файл OUTPUT.TXT выведите ответ на задачу Витальки.

Пример

INPUT.TXTOUTPUT.TXT
10 10 10 900 5
100 10 100 100 250
460

Задача B. Верхняя граница

(Время: 1 сек. Память: 16 Мб)

У Ромы и Саши есть набор карточек с цифрами: для каждой цифры k от 0 до 9 имеется ck карточек с изображением цифры k. Саша хочет составить целое число, которое строго больше X. Рома дополнительно хочет, чтобы это число было как можно меньше. Число составляется из карточек по его десятичной записи.

Определите, какое число им нужно составить или сообщите, что это невозможно.

Входные данные

В первой строке входного файла INPUT.TXT содержится целое неотрицательное число X, записанное в десятичной системе счисления без ведущих нулей. Число состоит не более, чем из 105 цифр. Во второй строке содержатся числа c0, c1, ..., c9 (0 ≤ ci ≤ 106).

Выходные данные

В выходной файл OUTPUT.TXT выведите искомое число без ведущих нулей. Если такое число невозможно составить, выведите «-1».

Примеры

INPUT.TXTOUTPUT.TXT
12019
1 2 0 3 0 0 0 0 0 0
3011
2165
1 1 1 1 1 1 1 1 1 1
167
3165
0 0 0 0 0 0 0 0 0 0
-1

Задача C. Волшебные цветы

(Время: 5 сек. Память: 64 Мб)

Цветочник Стёпик посадил 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 дней.

Примеры

INPUT.TXTOUTPUT.TXT
15 1
3 5 4 1 2
2 3 1 2 1
210 2
9 2 6 7 1 4 5 8 3 10
3 2 1 2 1 4 1 4 3 2
33 3
3 3 3
3 3 3

Задача D. Двоичное упражнение

(Время: 1 сек. Память: 16 Мб)

Маленький Бикарп очень любит степени двойки. Недавно он узнал о двоичной системе счисления и решил поупражняться на задачках по этой теме.

Ему попалась задача о сложении двух чисел, где требовалось определить количество единиц в двоичной записи этой суммы. В этой задаче требовалось сложить числа 2x−1 и 2y−1.

Пока Бикарп решает задачу на бумаге, напишите программу, которая быстро проверит его ответ.

Входные данные

Первая строка входного файла INPUT.TXT содержит число x, вторая − y. Оба числа целые. (0 ≤ x, y ≤ 230).

Выходные данные

В выходной файл OUTPUT.TXT выведите количество единиц в двоичной записи требуемой суммы.

Пример

INPUT.TXTOUTPUT.TXT
12
2
2

Задача E. Stack Unwinding

(Время: 1 сек. Память: 16 Мб)

Давид увлекается изучением своего любимого языка программирования. Для этого он иногда просматривает видео с различных курсов. На одном из них он познакомился с исключениями и теперь везде их пихаетиспользует. К сожалению, он не совсем понимает в каком порядке удаляются объекты при срабатывании исключения, поэтому просит вас по написанному им коду вывести в каком порядке будут создаваться и удаляться объекты в программе.

Напомним, что в языке Давида, при завершении функции объекты удаляются в обратном порядке, а при срабатывании исключения, программа завершается (т.к. Давид забыл написать соответствующий обработчик), предварительно освобождая созданные ей объекты. Выполнение программы всегда начинается с функции main.

Входные данные

В нескольких строчках входного файла INPUT.TXT содержится псевдокод программы. Он представляет собой описание нескольких функций (не больше 10), каждая из которых задается следующим образом. Вначале записывается сигнатура функции. Для упрощения во всех программах сигнатура функции будет выглядеть как "void funcName() {" (без кавычек), где funcName – имя объявляемой функции. Затем до "}" описывается тело функции, в котором могут быть только следующие команды:

  • Type name – создать объект name типа Type (например, "MyType var");
  • throw – место, где сработает исключение, гарантируется, что исключение может возникнуть только в одном месте;
  • funcName() – вызов функции. Здесь funcName - имя функции, которая описана в программе.

Все имена состоят только из английских букв и цифр. Код программы не превышает 10000 символов. Гарантируется, что в коде нет циклов (рекурсивных вызовов функций) и определение функции main является последним.

Выходные данные

В выходной файл OUTPUT.TXT требуется вывести последовательность создаваемых и удаляемых в программе Давида объектов. При создании объекта типа Type в отдельной строке нужно вывести Type(), при удалении – ∼Type(), возникновение исключения – throw.

Пример

INPUT.TXTOUTPUT.TXT
void foo() {
B b
C c
bar()
throw
bar()
}
void bar() {
T t
}
void main() {
A a
foo()
}
A()
B()
C()
T()
~T()
throw
~C()
~B()
~A()

Задача F. Пробежка

(Время: 1 сек. Память: 16 Мб)

Хомячок Хома наконец-то получил в подарок долгожданный тренажёр – колесо для бега. Колесо представляет из себя два круга, соединённых N спицами. Спицы пронумерованы числами от 1 до N по часовой стрелке. Соседние спицы расположены на равном расстоянии друг от друга.

Хома начинает пробежку так, что его передние лапки стоят на первой спице. Далее он делает K шагов таким образом, что на переход к следующей спице он тратит одну секунду. Сделав K шагов, он смотрит на какой спице он остановился: если это первая спица, то он завершает пробежку и слазит с колеса, а иначе отдыхает R секунд и повторяет процедуру снова.

Хозяйка Хомы интересуется, сколько времени будет занимать одна такая пробежка?

Входные данные

Входной файл INPUT.TXT содержит три целых числа N, K и R по одному в отдельной строке (1 ≤ N, K, R ≤ 2×109).

Выходные данные

В выходной файл OUTPUT.TXT выведите единственное число – сколько секунд потратит Хома на пробежку.

Пример

INPUT.TXTOUTPUT.TXT
6
4
1
14

Задача G. Три монеты

(Время: 1 сек. Память: 16 Мб)

Это интерактивная задача.

Перед вами стопка из 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 — различные номиналы фальшивых монет. После этого программа должна завершить работу.

Пример

стандартный вводстандартный вывод
6
12
6
6
2
2
0
0
? 6
? 5
? 4
? 3
? 2
? 1
? 0
! 1 5 3

Примечание

Для корректной работы программы после каждой операции вывода данных выводите перевод строки, а также очищайте буфер вывода. Очистка буфера вывода производится следующим образом:

  • В языке Pascal: flush(output)
  • В С/С++: fflush(stdout) или cout.flush()
  • В Java: System.out.flush()
  • В Python: sys.stdout.flush() из библиотеки sys
  • В C# и Basic: Console.Out.Flush()

Задача H. Кинозал

(Время: 2 сек. Память: 32 Мб)

Однажды Вася пришёл в известный кинотеатр «Прямая», чтобы посмотреть новый боевик. Когда он проходил к своему месту в зале, то ему пришлось потревожить некоторых людей, которые заняли свои места раньше него. Он был этим так расстроен, что решил в следующий раз заранее определить минимальное количество людей, которым он должен помешать.

Известно, что кинозал имеет форму прямоугольника шириной 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 выведите целое число — минимальное количество людей, которое нужно потревожить Васе.

Примеры

INPUT.TXTOUTPUT.TXTПояснение
110 5 8 2
vert 3
vert 8
2 2
5 6
1 7
3 4
3 6
3 7
4 10
1 4
3 5
1
25 5 2 2
hor 3
vert 4
4 1
4 3
4 2
0

Задача I. Индикатор загрузки

(Время: 1 сек. Память: 16 Мб)

Для отображения процесса загрузки файла часто используют индикатор в виде полоски, заполняющейся слева направо. Мы имеем дело с индикатором длиной в N пикселей. Если индикатор отображает K пикселей, то это значит, что хотя бы K/N-я часть файла загружена. При этом для уменьшения неопределённости заполняется максимальное возможное количество пикселей.

Вам нужно вывести индикатор длиной в N пикселей в момент, когда загружено ровно P% файла.

Входные данные

Единственная строка входного файла INPUT.TXT содержит два целых числа N и P (1 ≤ N ≤ 1000; 0 ≤ P ≤ 100).

Выходные данные

В выходной файл OUTPUT.TXT выведите индикатор загрузки, окружив его квадратными скобками. Заполненную часть индикатора следует обозначать символом «*» («звёздочка»), а пустую — «.» (точка).

Примеры

INPUT.TXTOUTPUT.TXT
110 40[****......]
210 99[*********.]

Задача J. Заверните две!

(Время: 5 сек. Память: 64 Мб)

Петя как обычно шёл утром на работу по обычной дороге, как вдруг ему на глаза попалась новая шаурмичная. Он решил зайти в неё и запастись пищей на весь следующий день. Петя хочет купить ровно две шаурмы — на обед и ужин (не беспокойтесь, микроволновка на работе у Пети есть).

Всего в шаурмичной существует 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».

Примеры

INPUT.TXTOUTPUT.TXT
15
5 1 2 -3 1
3
1 4
2 3
4 5
2 3
23
1 2 3
2
1 2
2 3
-1 -1

Задача K. Сладкая вата

(Время: 1 сек. Память: 16 Мб)

Как все вы знаете, решение олимпиадных задач на алгоритмы и структуры данных – дело весьма энергозатратное. Именно поэтому все участники Открытого личного первенства ИКИТ СФУ по программированию по окончании соревнований получают сладкую вату калорийностью C калорий. На олимпиаде участникам предлагается решить N задач, для решения каждой требуется потратить V калорий.

Программист Федя будет участвовать в олимпиаде и собирается решить все задачи! Он хочет посчитать, хватит ли калорий, полученных из сладкой ваты, чтобы компенсировать калории, потраченные на решение всех задач. Помогите ему!

Входные данные

Первая строка входного файла INPUT.TXT содержит три целых числа C, N и V (1 ≤ C, V ≤ 10 000, 1 ≤ N ≤ 15).

Выходные данные

В выходной файл OUTPUT.TXT выведите одно целое число – разницу между калорийностью ваты и калориями, необходимыми для решения всех задач олимпиады.

Примеры

INPUT.TXTOUTPUT.TXT
1100 10 550
215 3 6-3



Красноярский краевой Дворец пионеров, (c)2006 - 2019, ICQ: 151483, E-mail: admin@acmp.ru