Школа программиста

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

HotLog


 

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


Задача A. Обед

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

Организаторы чемпионата мира по программированию ACM ICPC приготовили для всех участников финала вкусный и питательный перекус, который они получат прямо во время соревнований. Каждый участник получит сладкий банан, так как сладкое помогает работе мозга и решению задач, и бутылочку минеральной воды, которая способствует быстрому усвоению этого банана.

Ваша задача - помочь организаторам финала рассчитать, сколько будет стоить перекус для всех участников.

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

В единственной строке входного файла INPUT.TXT записаны три целых числа: N — количество участников, X — стоимость одного банана и Y — стоимость одной бутылочки с минералкой (1 ≤ N, X, Y ≤ 1000).

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

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

Пример

INPUT.TXTOUTPUT.TXT
1100 20 355500

Задача B. Страшный сон Егора

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

Егор — школьник, совсем скоро ему участвовать в региональном этапе Всероссийской олимпиады школьников по информатике. К олимпиаде он готов, полностью уверен в победе в регионе, но чтобы пройти в следующий, заключительный этап, ему нужно постараться.

Накануне перед олимпиадой ему приснился страшный сон: Егор не набрал необходимые T проходных баллов по итогу олимпиады, а значит на заключительный этап он поедет только по квоте! Об отношении с квотниками на заключительном этапе Егор знает не понаслышке, поэтому он просит вас о помощи.

Помимо проходного балла T — минимального количества баллов, которое нужно набрать, ему приснилось, что на олимпиаде будет N задач, по каждой можно набрать целый балл от 0 до 100, при этом в i-й задаче можно будет набрать только балл, кратный ki.

Егору не приснились сами задачи, но приснились затраты энергии si — сколько требуется энергии на прочтение задачи, и ci — сколько потребуется энергии чтобы набрать по задаче один балл. Естественно, нельзя набирать баллы по задаче, не прочитав её.

Егор хочет набрать как минимум T баллов, но при этом хочет потратить суммарно как можно меньше энергии, чтобы потом смело можно было заявлять, что он писал олимпиаду на расслабоне.

Определите минимальное количество энергии, необходимое Егору, а также для каждой задачи, какой балл по ней нужно набрать, чтобы достичь этого результата.

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

В первой строке входного файла INPUT.TXT содержатся два целых числа N и T (1 ≤ N ≤ 100; 1 ≤ T ≤ 100×N).

В следующих N строках содержится по три числа si, ci и ki для каждой задачи (1 ≤ si, ci ≤ 105; 1 ≤ ki ≤ 100; ki — делитель числа 100).

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

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

Во второй строке выведите N чисел bi через пробел — баллы, которые нужно набирать по каждой задаче. Каждое bi должно делиться на ki, а также быть 0 ≤ bi ≤ 100.

Если существует несколько решений, выведите любое.

Пример

INPUT.TXTOUTPUT.TXT
13 166
10 5 1
1 1 10
15 4 25
406
16 100 50

Задача C. Виталя и кубик

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

У Витали есть белый кубик с одной красной гранью. Кубик стоит в левом верхнем углу шахматной доски красной гранью вверх.

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

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

В единственной строке входного файла INPUT.TXT записаны целые числа N и M (1 ≤ N, M ≤ 100) — количество строк и столбцов шахматной доски.

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

Если решения не существует, то в единственной строке выходного файла OUTPUT.TXT выведите «no solution» (без кавычек), в противном случае выведите искомую последовательность ходов, по одному ходу в каждой строке. Для перекатывания кубика влево, вправо, вверх и вниз используйте команды LEFT, RIGHT, UP и DOWN соответственно.

Примеры

INPUT.TXTOUTPUT.TXT
12 2DOWN
RIGHT
UP
22 3DOWN
RIGHT
RIGHT
UP
LEFT
RIGHT

Задача D. Удаление чисел

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

Василий в этом году заканчивает 9 класс и мечтает поступить в Физико-математическую школу СФУ (ФМШ). Для подготовки к вступительному экзамену он прорешивает задания прошлых лет. Одно задание показалась Василию особенно сложным, но очень интересным. Василий всё-таки смог решить это задание. А вы сможете?

В ряд выписаны все целые числа от 1 до N. За одну операцию можно удалить либо все числа на чётных позициях, либо на нечётных. Оставшиеся числа образуют новый ряд. Позиции пронумерованы с единицы, слева направо. Необходимо вывести последовательность операций, после которых в ряду останется единственное число A.

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

Входной файл INPUT.TXT содержит два целых числа: N — количество чисел и A — число, которое должно остаться после всех операций (1 ≤ A ≤ N ≤ 1018).

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

В выходной файл OUTPUT.TXT выведите последовательность операций в одной строке. Для удаления всех чисел на чётных позициях выведите 0, для удаления всех чисел на нечётных позициях выведите 1.

Пример

INPUT.TXTOUTPUT.TXT
110 50 0 1

Задача E. Юниты и ресурсы

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

Вася играет в стратегическую компьютерную игру. В играх подобного жанра используются два важных понятия: юниты и ресурсы.

Ресурсы - это своеобразная валюта внутри игры. В разных играх ресурсами могут выступать золото, лес, минералы, нефть, камни, пища и другое. В одной игре может быть (и чаще всего так и есть) сразу несколько различных ресурсов.

Юнит - это боевая или рабочая живая единица в компьютерных играх, покупается за ресурсы. Каждый юнит имеет свою стоимость, выраженную в различных видах ресурсов. За некоторые юниты нужно расплачиваться не одним типом ресурсов, а несколькими. Если какого-либо из ресурсов имеется меньше, чем требуется, то покупка невозможна.

Вася накопил определенное количество ресурсов. Теперь Вася хочет на эти ресурсы приобрести какого-нибудь юнита.

В игре существует N видов ресурсов и M видов юнитов. Вам известны количество ресурсов, имеющееся у Васи и стоимость каждого из юнитов. Помогите Васе определить, кого из юнитов Вася мог бы купить, а на кого не хватит средств.

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

В первой строке входного файла INPUT.TXT содержатся два числа: N и M - количество различных ресурсов и количество различных юнитов (1 ≤ N, M ≤ 100).

В следующей строке содержится N чисел - имеющееся количество каждого из ресурсов.

Далее идет M строк, каждая из которых описывает соответствующего юнита. В каждой из этих строк содержится по N чисел - стоимости юнита в каждом из ресурсов, которые перечислены во второй строке входных данных в том же порядке.

Все числа во входном файле целые неотрицательные и не превышают 100.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
13 5
10 6 9
5 9 3
4 6 10
9 3 6
2 8 7
4 5 6
0 0 1 0 1
23 5
10 6 5
7 9 7
1 9 2
6 9 3
9 7 5
4 4 5
0 0 0 0 1

Примечание

В первом примере мы можем купить третьего и пятого юнита. Первый и четвертый юнит требуют слишком много второго ресурса, а второй требует слишком много третьего ресурса.

Во втором примере мы можем купить только последнего юнита.


Задача F. Задача без подвоха

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

Перед вами задача, в которой отсутствует какой-либо подвох. Специальная комиссия изучила задачу на наличие подвохов и... Заверила, что количество подвохов в ней идеально — ровно ноль.

Если вы жаждите подвохов — эта задача не для вас.

Ну же, убедитесь в этом! Ах да, сама задача...

Вам дано множество цифр. Десятичных, никакого подвоха.

Вам нужно найти минимальное целое K такое, что 0 ≤ K и что число 2K содержит в своей десятичной записи все эти цифры.

Как видите, здесь нет подвоха. Просто напишите решение и получите свой Accepted!

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

В первой строке входного файла INPUT.TXT содержится целое число T (1 ≤ T ≤ 32). Подвох? Нет, это просто количество подтестов.

В каждой из следующих T строк содержится непустая строка, состоящая из различных десятичных цифр.

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

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

Пример

INPUT.TXTOUTPUT.TXT
15
2
8
3
69
17
1
3
5
12
17

Задача G. Раздел Империи

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

Великий император Виталиус Демидович вскоре уйдёт на покой. Во владениях он имеет империю, которая представляет из себя N стран, соединённых N - 1 дорогой так, что из каждой страны есть путь в любую другую.

Придворный оракул императора рассказал, что некоторые страны могут ослабеть и исчезнуть с лица Земли. Теперь Виталиус не находит покоя. Ведь если некоторые страны исчезнут, то империя может распасться на несколько новых. А именно, после исчезновения страны вслед за ней исчезают и все дороги, которые к ней примыкали. Все оставшиеся страны объединяются по новым империям по следующему правилу: если две страны всё ещё достижимы друг от друга по оставшимся дорогам, то они будут находиться в одной империи.

Император беспокоится о величии новых империй, а именно его интересует размер наибольшей из образовавшихся империй после удаления некоторых стран. Придворный картограф Виталиуса, то есть Вы, теперь завален запросами для некоторых множеств стран. Для каждого такого множества вычислите наибольший размер новой империи, если заданные страны исчезнут.

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

В первой строке входного файла INPUT.TXT содержится целое число N — размер империи (1 ≤ N ≤ 200 000).

В следующих N - 1 строках содержится по паре чисел ai и bi означающих, что соответствующие страны соединены дорогой (1 ≤ ai, bi ≤ N; ai ≠ bi).

Далее записано целое число M — количество запросов (1 ≤ M ≤ 500 000).

В следующих M строках идёт описание запросов. Каждый запрос содержится в отдельной строке и начинается с целого числа k, следом за которым идут k целых различных чисел vi — номера стран для удаления (1 ≤ k, vi ≤ N).

Гарантируется, что сумма всех k в одном тесте не превосходит 500 000.

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

В выходной файл OUTPUT.TXT выведите M целых чисел — для каждого множества стран в отдельной строке выведите максимальный размер новой империи.

Пример

INPUT.TXTOUTPUT.TXT
114
1 2
1 3
2 6
2 7
3 4
3 5
6 8
8 9
8 10
7 11
7 12
7 13
12 14
4
1 2
3 1 7 8
4 2 3 8 12
4 9 10 14 5
5
3
3
10

Задача H. Великая таблица умножения

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

Поликарп приобрёл на барахолке кусок каменной плиты. Старик, показавший ему этот камень, утверждал, что это кусок Великой Таблицы Умножения — монумента, которому поклонялось племя коммутативных инков. Таблицу не зря называли великой — она была таблицей умножения размера 1018 строк на 1018 столбцов.

На куске камня, который попал к Поликарпу, вычерчено N строк по M целых чисел в каждой и, как утверждал старец, этот прямоугольник был вырезан из Великой Таблицы Умножения, то есть является его подпрямоугольником.

Поликарп переслал вам фотографию, на которой видно все числа и попросил проверить, может ли камень быть частью давно утерянного артефакта.

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

В первой строке входного файла INPUT.TXT содержатся два целых числа N и M — размеры таблицы (1 ≤ N, M ≤ 500).

В следующих N строках содержится по M чисел ai, j, записанных через пробел — элементы таблицы (1 ≤ ai, j ≤ 1018).

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

В выходной файл OUTPUT.TXT выведите «true», если Поликарпу достался кусок настоящего сокровища, и «false» иначе.

Примеры

INPUT.TXTOUTPUT.TXT
12 2
1 2
2 4
true
23 3
3 4 5
4 5 6
5 6 7
false

Задача I. Индекс.Контест

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

Даны два длинных целых числа A и B, выложенные спичками, и кучка с неограниченным количеством спичек. Числа одинаковой длины. Все цифры в числах выложены как индекс на почтовом конверте:

Найдите минимальное количество перекладываний спичек, за которое все цифры числа A можно превратить в соответствующие цифры числа B. Таким образом первая цифра числа A должна превратиться в первую цифру числа B, вторая - во вторую и т.д. За одно перекладывание можно переложить спичку с одного места в числе на другое (можно перекладывать спички между разными цифрами), убрать спичку из числа в кучку или взять спичку из кучки.

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

В первой строке входного файла INPUT.TXT записано число A, во второй строке - число B. Числа могут содержать ведущие нули. Каждое число содержит от 1 до 105 цифр.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
1010
112
7
212345
67890
14

Задача J. Юбилей

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

Ромка недавно вернулся с юбилея своего друга Сашки. Праздник отмечался с размахом и Ромка подумал, а что если бы юбилеи были чаще? Можно же не ограничиваться десятичной системой счисления. Ромка ввёл понятие юбилейности числа, равное максимальному количеству нулей в конце записи этого числа в какой-то системе счисления с основанием B, где B — целое число, большее единицы. Например, юбилейность числа 256 равна 8, так как в двоичной системе счисления оно оканчивается на 8 нулей. Ромка хочет узнать, когда его ближайший значимый юбилей, если в прошлом месяце ему исполнилось X лет? Значимым юбилеем он считает количество лет, которое обладает юбилейностью хотя бы L.

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

Единственная строка входного файла INPUT.TXT содержит два целых числа X и L (1 ≤ X ≤ 1012; 1 ≤ L ≤ 50).

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

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

Примеры

INPUT.TXTOUTPUT.TXT
19990 410000
2100 8256
3100 2104

Задача K. Простая задача

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

Эта задача проще, чем может показаться на первый взгляд.

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

Во входном файле INPUT.TXT записаны результаты выражений и . Оба этих числа (а также сами числа a и b) целые, неотрицательные и не превышают 10000.

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

Мы не просим вас найти значения a и b. Нам будет достаточно, если в выходной файл OUTPUT.TXT вы выведите произведение этих чисел (a×b).

Примеры

INPUT.TXTOUTPUT.TXTПояснение
181 2556a=14, b=4
281 4932a=16, b=2
3100 6436a=18, b=2



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



Купить модуль Bluetooth HC-05 для Arduino.