|
Забыли пароль? | ||||
| [задачи] [курсы] [олимпиады] [регистрация] | |||||
|
Задача B. Страшный сон ЕгораЕгор — школьник, совсем скоро ему участвовать в региональном этапе Всероссийской олимпиады школьников по информатике. К олимпиаде он готов, полностью уверен в победе в регионе, но чтобы пройти в следующий, заключительный этап, ему нужно постараться. Накануне перед олимпиадой ему приснился страшный сон: Егор не набрал необходимые 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. Если существует несколько решений, выведите любое. Пример
Задача C. Виталя и кубикУ Витали есть белый кубик с одной красной гранью. Кубик стоит в левом верхнем углу шахматной доски красной гранью вверх. Придумайте последовательность ходов, чтобы переместить кубик в правый верхний угол, перекатывая его по граням от клетки к клетке шахматной доски. При этом кубик не должен касаться поля доски красной гранью, а по завершении своего маршрута он должен остаться стоять красной гранью вверх. В каждой клетке поля кубик должен побывать хотя бы один раз. Количество ходов должно быть не больше 106. Входные данныеВ единственной строке входного файла INPUT.TXT записаны целые числа N и M (1 ≤ N, M ≤ 100) — количество строк и столбцов шахматной доски. Выходные данныеЕсли решения не существует, то в единственной строке выходного файла OUTPUT.TXT выведите «no solution» (без кавычек), в противном случае выведите искомую последовательность ходов, по одному ходу в каждой строке. Для перекатывания кубика влево, вправо, вверх и вниз используйте команды LEFT, RIGHT, UP и DOWN соответственно. Примеры
Задача D. Удаление чиселВасилий в этом году заканчивает 9 класс и мечтает поступить в Физико-математическую школу СФУ (ФМШ). Для подготовки к вступительному экзамену он прорешивает задания прошлых лет. Одно задание показалась Василию особенно сложным, но очень интересным. Василий всё-таки смог решить это задание. А вы сможете? В ряд выписаны все целые числа от 1 до N. За одну операцию можно удалить либо все числа на чётных позициях, либо на нечётных. Оставшиеся числа образуют новый ряд. Позиции пронумерованы с единицы, слева направо. Необходимо вывести последовательность операций, после которых в ряду останется единственное число A. Входные данныеВходной файл INPUT.TXT содержит два целых числа: N — количество чисел и A — число, которое должно остаться после всех операций (1 ≤ A ≤ N ≤ 1018). Выходные данныеВ выходной файл OUTPUT.TXT выведите последовательность операций в одной строке. Для удаления всех чисел на чётных позициях выведите 0, для удаления всех чисел на нечётных позициях выведите 1. Пример
Задача E. Юниты и ресурсыВася играет в стратегическую компьютерную игру. В играх подобного жанра используются два важных понятия: юниты и ресурсы. Ресурсы - это своеобразная валюта внутри игры. В разных играх ресурсами могут выступать золото, лес, минералы, нефть, камни, пища и другое. В одной игре может быть (и чаще всего так и есть) сразу несколько различных ресурсов. Юнит - это боевая или рабочая живая единица в компьютерных играх, покупается за ресурсы. Каждый юнит имеет свою стоимость, выраженную в различных видах ресурсов. За некоторые юниты нужно расплачиваться не одним типом ресурсов, а несколькими. Если какого-либо из ресурсов имеется меньше, чем требуется, то покупка невозможна. Вася накопил определенное количество ресурсов. Теперь Вася хочет на эти ресурсы приобрести какого-нибудь юнита. В игре существует N видов ресурсов и M видов юнитов. Вам известны количество ресурсов, имеющееся у Васи и стоимость каждого из юнитов. Помогите Васе определить, кого из юнитов Вася мог бы купить, а на кого не хватит средств. Входные данныеВ первой строке входного файла INPUT.TXT содержатся два числа: N и M - количество различных ресурсов и количество различных юнитов (1 ≤ N, M ≤ 100). В следующей строке содержится N чисел - имеющееся количество каждого из ресурсов. Далее идет M строк, каждая из которых описывает соответствующего юнита. В каждой из этих строк содержится по N чисел - стоимости юнита в каждом из ресурсов, которые перечислены во второй строке входных данных в том же порядке. Все числа во входном файле целые неотрицательные и не превышают 100. Выходные данныеВ выходной файл OUTPUT.TXT для каждого юнита выведите 1, если на его приобретение хватает средств и 0 в противном случае. Числа следует разделять пробелами. Примеры
ПримечаниеВ первом примере мы можем купить третьего и пятого юнита. Первый и четвертый юнит требуют слишком много второго ресурса, а второй требует слишком много третьего ресурса. Во втором примере мы можем купить только последнего юнита. Задача F. Задача без подвохаПеред вами задача, в которой отсутствует какой-либо подвох. Специальная комиссия изучила задачу на наличие подвохов и... Заверила, что количество подвохов в ней идеально — ровно ноль. Если вы жаждите подвохов — эта задача не для вас. Ну же, убедитесь в этом! Ах да, сама задача... Вам дано множество цифр. Десятичных, никакого подвоха. Вам нужно найти минимальное целое K такое, что 0 ≤ K и что число 2K содержит в своей десятичной записи все эти цифры. Как видите, здесь нет подвоха. Просто напишите решение и получите свой Accepted! Входные данныеВ первой строке входного файла INPUT.TXT содержится целое число T (1 ≤ T ≤ 32). Подвох? Нет, это просто количество подтестов. В каждой из следующих T строк содержится непустая строка, состоящая из различных десятичных цифр. Выходные данныеДля каждого множества цифр в выходной файл OUTPUT.TXT выведите ответ в отдельной строке, спокойно и уверенно. Вы же не хотите, чтобы тестирующая система почувствовала подвох? Пример
Задача G. Раздел ИмперииВеликий император Виталиус Демидович вскоре уйдёт на покой. Во владениях он имеет империю, которая представляет из себя 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 целых чисел — для каждого множества стран в отдельной строке выведите максимальный размер новой империи. Пример
Задача H. Великая таблица умноженияПоликарп приобрёл на барахолке кусок каменной плиты. Старик, показавший ему этот камень, утверждал, что это кусок Великой Таблицы Умножения — монумента, которому поклонялось племя коммутативных инков. Таблицу не зря называли великой — она была таблицей умножения размера 1018 строк на 1018 столбцов. На куске камня, который попал к Поликарпу, вычерчено N строк по M целых чисел в каждой и, как утверждал старец, этот прямоугольник был вырезан из Великой Таблицы Умножения, то есть является его подпрямоугольником. Поликарп переслал вам фотографию, на которой видно все числа и попросил проверить, может ли камень быть частью давно утерянного артефакта. Входные данныеВ первой строке входного файла INPUT.TXT содержатся два целых числа N и M — размеры таблицы (1 ≤ N, M ≤ 500). В следующих N строках содержится по M чисел ai, j, записанных через пробел — элементы таблицы (1 ≤ ai, j ≤ 1018). Выходные данныеВ выходной файл OUTPUT.TXT выведите «true», если Поликарпу достался кусок настоящего сокровища, и «false» иначе. Примеры
Задача I. Индекс.КонтестДаны два длинных целых числа A и B, выложенные спичками, и кучка с неограниченным количеством спичек. Числа одинаковой длины. Все цифры в числах выложены как индекс на почтовом конверте: Найдите минимальное количество перекладываний спичек, за которое все цифры числа A можно превратить в соответствующие цифры числа B. Таким образом первая цифра числа A должна превратиться в первую цифру числа B, вторая - во вторую и т.д. За одно перекладывание можно переложить спичку с одного места в числе на другое (можно перекладывать спички между разными цифрами), убрать спичку из числа в кучку или взять спичку из кучки. Входные данныеВ первой строке входного файла INPUT.TXT записано число A, во второй строке - число B. Числа могут содержать ведущие нули. Каждое число содержит от 1 до 105 цифр. Выходные данныеВ выходной файл OUTPUT.TXT выведите одно целое число - ответ на задачу. Примеры
Задача J. ЮбилейРомка недавно вернулся с юбилея своего друга Сашки. Праздник отмечался с размахом и Ромка подумал, а что если бы юбилеи были чаще? Можно же не ограничиваться десятичной системой счисления. Ромка ввёл понятие юбилейности числа, равное максимальному количеству нулей в конце записи этого числа в какой-то системе счисления с основанием B, где B — целое число, большее единицы. Например, юбилейность числа 256 равна 8, так как в двоичной системе счисления оно оканчивается на 8 нулей. Ромка хочет узнать, когда его ближайший значимый юбилей, если в прошлом месяце ему исполнилось X лет? Значимым юбилеем он считает количество лет, которое обладает юбилейностью хотя бы L.
Входные данныеЕдинственная строка входного файла INPUT.TXT содержит два целых числа X и L (1 ≤ X ≤ 1012; 1 ≤ L ≤ 50). Выходные данныеВ выходной файл OUTPUT.TXT выведите единственное число — ответ на задачу. Примеры
Задача K. Простая задачаЭта задача проще, чем может показаться на первый взгляд.
Входные данные
Во входном файле INPUT.TXT записаны результаты выражений Выходные данныеМы не просим вас найти значения a и b. Нам будет достаточно, если в выходной файл OUTPUT.TXT вы выведите произведение этих чисел (a×b). Примеры
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
