фвфвфв. Контрольная работа Петя и Вася одноклассники и лучшие друзья, поэтому они во всём помогают друг другу. Завтра у них контрольная по математике, и учитель подготовил целых
 Скачать 277.99 Kb.
|
|
Кола Завод по производству колы изготавливает ее не только для магазинов, но и для всемирно известной сети ресторанов быстрого питания. Ежедневно завод отгружает один и тот же объем колы в литрах. Служба доставки сети ресторанов обычно использует для транспортировки колы емкости объемом или только 50 литров, или только 70 литров. Если доставка осуществляется с помощью емкостей в 50 литров, то для перевозки имеющегося объема колы необходимо A емкостей. А если с помощью емкостей в 70 литров, то необходимо B емкостей. При этом в каждом из случаев одна из емкостей может быть заполнена не полностью. Недавно сеть ресторанов решила утвердить новый объем емкостей для доставки колы — 60 литров. Сколько емкостей теперь может понадобиться для доставки того же самого объема колы? Входные данные Входные данные содержат 2 числа A и B , расположенных каждое в отдельной строке ( 1 ≤ A, B ≤ 10 000 000 ). Выходные данные Выведите все возможные значения для количества емкостей по 60 литров, которые окажутся заполненными (в том числе одна возможно частично), в порядке возрастания или число - 1 , если значения A и B противоречат друг другу, то есть они были записаны неверно. Примеры тестов входные данные 3 2 входные данные 1 2 Примечание В первом примере колы могло быть, например, 115 литров, в этом случае понадобится две емкости в 60 литров, а могло быть — 135 литров, в этом случае понадобятся уже три емкости по 60 литров. Четыре емкости не могут понадобиться никогда. Online-группа тестов оценивается в 60 баллов, в этой группе 1 ≤ A, B ≤ 1 000 выходные данные 2 3 выходные данные -1 Offline-группа тестов оценивается в 40 баллов. Контрольная работа Петя и Вася — одноклассники и лучшие друзья, поэтому они во всём помогают друг другу. Завтра у них контрольная по математике, и учитель подготовил целых K вариантов заданий. В классе стоит один ряд парт, за каждой из них (кроме, возможно, последней) на контрольной будут сидеть ровно два ученика. Ученики знают, что варианты будут раздаваться строго по порядку: правый относительно учителя ученик первой парты получит вариант 1, левый — вариант 2, правый ученик второй парты получит вариант 3 (если число вариантов больше двух) и т.д. Так как K может быть меньше чем число учеников N , то после варианта K снова выдаётся вариант 1. На последней парте в случае нечётного числа учеников используется только место 1. Петя самым первым вошёл в класс и сел на своё любимое место. Вася вошёл следом и хочет получить такой же вариант, что и Петя, при этом сидя к нему как можно ближе. То есть между ними должно оказаться как можно меньше парт, а при наличии двух таких мест с равным расстоянием от Пети Вася сядет позади Пети, а не перед ним. Напишите программу, которая подскажет Васе, какой ряд и какое место (справа или слева от учителя) ему следует выбрать. Если же один и тот же вариант Вася с Петей писать не смогут, то выдайте одно число - 1 Входные данные В первой строке входных данных находится количество учеников в классе 2 ≤ N ≤ 10 9 Во второй строке — количество подготовленных для контрольной вариантов заданий 2 ≤ K ≤ N . В третьей строке — номер ряда, на который уже сел Петя, в четвёртой — цифра 1, если он сел на правое место, и 2, если на левое. Выходные данные Если Вася никак не сможет писать тот же вариант, что и Петя, то выведите - 1 . Если решение существует, то выведите два числа — номер ряда, на который следует сесть Васе, и 1, если ему надо сесть на правое место, или 2, если на левое. Разрешается использовать только первые N мест в порядке раздачи вариантов. Примеры тестов входные данные 25 2 1 2 входные данные 25 13 выходные данные 2 2 7 1 Примечание В первом примере вариантов 2, поэтому наилучшее место для Васи находится сразу за Петей. Во втором примере Петя будет единственным, кто получит вариант 13. Система оценки Каждый тест в задаче оценивается отдельно. Программа, выдающая правильный ответ только на тесты из условия и тесты с ответом - 1 , не оценивается. Решение тестируется на основном наборе тестов только при прохождении всех тестов из условия. При этом тесты из условия не оцениваются. Подзадача 1. N ≤ 100 . Оценивается из 52 баллов. Подзадача 2. N ≤ 10 9 . Оценивается из 48 баллов. выходные данные -1 Хорошая строка На день рождения маленький Ипполит получил долгожданный подарок — набор дощечек с написанными на них буквами латинского алфавита. Теперь-то ему будет чем заняться долгими вечерами, тем более что мама обещала подарить ему в следующем году последовательность целых неотрицательных чисел, если он хорошо освоит этот набор. Ради такого богатства Ипполит готов на многое. Прямо сейчас юный исследователь полностью поглощён изучением хорошести строк. Хорошестью строки называется количество позиций от 1 до L - 1 (где L — длина строки), таких, что следующая буква в строке является следующей по алфавиту. Например, хорошесть строки " abcdefghijklmnopqrstuvwxyz " равна 25, а строки " abdc " — только 1. Ипполит размышляет над решением закономерно возникающей задачи: чему равна максимально возможная хорошесть строки, которую можно собрать, используя дощечки из данного набора? Вы-то и поможете ему с ней справиться. Входные данные Первая строка ввода содержит единственное целое число N — количество различных букв в наборе ( 1 ≤ N ≤ 26 ). Обратите внимание: в наборе всегда используются N первых букв латинского алфавита. Следующие N строк содержат целые положительные числа c i — количество букв соответствующего типа ( 1 ≤ c i ≤ 10 9 ). Таким образом, первое число означает количество букв " a ", второе число задаёт количество букв " b " и так далее. Выходные данные Выведите единственное целое число — максимально возможную хорошесть строки, которую можно собрать из имеющихся дощечек. Примеры тестов входные данные 3 1 1 1 входные данные 2 3 4 выходные данные 2 выходные данные Примечание В первом тесте имеется по одной дощечке с каждой из 3 различных букв. Ответ 2 достигается на строке " abc " Система оценки Каждый тест в данной задаче оценивается отдельно. Решение тестируется на основном наборе тестов только при прохождении всех тестов из условия. При этом тесты из условия не оцениваются. Подзадача 1. Во всех тестах данной группы c i ≤ 100 . Данная подзадача оценивается из 40 баллов. Подзадача 2. Во всех тестах данной группы c i ≤ 1 000 000 . Данная подзадача оценивается из 30 баллов. Подзадача 3. Во всех тестах данной группы c i ≤ 10 9 . Данная подзадача оценивается из 30 баллов. 3 Очень Легкая Задача Сегодня утром жюри решило добавить в вариант олимпиады еще одну, Очень Легкую Задачу. Ответственный секретарь Оргкомитета напечатал ее условие в одном экземпляре, и теперь ему нужно до начала олимпиады успеть сделать еще N копий. В его распоряжении имеются два ксерокса, один из которых копирует лист за х секунд, а другой – за y. (Разрешается использовать как один ксерокс, так и оба одновременно. Можно копировать не только с оригинала, но и с копии.) Помогите ему выяснить, какое минимальное время для этого потребуется. Входные данные На вход программы поступают три натуральных числа N, x и y, разделенные пробелом (1 ≤ N ≤ 2∙10 8 , 1 ≤ x, y ≤ 10). Выходные данные Выведите одно число – минимальное время в секундах, необходимое для получения N копий. Примеры входные данные 4 1 1 входные данные 5 1 2 выходные данные 3 выходные данные 4 Изобретательный Петя Петя нашел на чердаке старый телеграфный аппарат и приделал к нему хитроумное устройство, которое может печатать на телеграфной ленте определенное слово (обозначим его X). Петино устройство может напечатать на ленте это слово сколько угодно раз. Петя может заставить аппарат напечатать на ленте и любое другое сообщение, но для этого ему нужно разобрать свое хитроумное устройство, и после этого он уже не сможет печатать сообщение X. А самое главное, что напечатать даже один символ другого сообщения потребует от Пети больше усилий, чем напечатать на ленте слово X с помощью хитроумного устройства. Петя хочет сделать так, чтобы всем казалось, что ему по телеграфу пришло сообщение Z. Для этого он может (строго в этой последовательности): сколько угодно раз напечатать сообщение X разобрать хитроумное устройство и посимвольно напечатать еще что-нибудь (назовем это Y) оторвать и выбросить начало ленты так, чтобы на оставшейся ленте было напечатано в точности сообщение Z Поскольку набирать отдельные символы сообщения Y довольно сложно, Петя хочет, чтобы в сообщении Y было как можно меньше символов. Для лучшего понимания задачи смотрите примеры и пояснения к ним. Входные данные В первой строке вводится слово X, которое Петя может печатать с помощью хитроумного устройства сколько угодно раз. Во второй строке вводится сообщение Z, которое хочет получить Петя. Каждое сообщение состоит только из маленьких латинских букв и имеет длину не более 100 символов. Выходные данные Выведите минимальное по длине сообщение Y, которое Пете придется допечатать вручную. Комментарии к примерам тестов 1. Сначала Петя два раза напечатает слово mama, потом к нему припечатает букву m, а затем отрежет и выбросит три начальных символа (mam). Ответом является допечатываемая отдельно буква m. 2. Казалось бы, Пете стоит сначала напечатать букву m, а затем слово ura, которое он умеет печатать. Однако для того, чтобы напечатать m, ему придется разобрать свое устройство, и печатать ura ему придется также посимвольно. 3. Казалось бы, Петя может напечатать слово computer, а затем отрезать и выбросить его конец — однако он не может так поступить, потому что отрезать и выбросить он может только начало ленты. 4. Пете достаточно один раз напечатать слово ejudge, а затем отрезать и выбросить букву e. Ничего посимвольно выводить ему не придется, поэтому ответом является пустая строка. 5. Достаточно трижды напечатать исходное слово и нужный результат будет получен. Ничего добавлять не надо, поэтому ответ – пустая строка. Примеры входные данные mama amamam входные данные ura mura входные данные computer comp входные данные ejudge judge входные данные m mmm выходные данные m выходные данные mura выходные данные comp выходные данные выходные данные Шляпа Летом Максим съездил в Летнюю Какую-то Школу, где, помимо учёбы, ему очень запомнилась игра «Шляпа», в которую он вместе с друзьями играл всю смену. Опишем правила игры, которых они придерживались. Обратите внимание: эти правила немного отличаются от общепринятых. Изначально в шляпу помещают некоторое количество бумажек с написанными на них словами. После этого команды из двух человек по очереди и в случайном порядке начинают отгадывать слова - один член команды объясняет другому написанное на бумажке слово, не используя однокоренные. Если партнёр отгадывает его, то команде засчитывается одно очко, слово выкидывается, а команда достаёт из шляпы новое, если у неё ещё осталось время в этом раунде. Если команда не успевает отгадать очередное слово, то бумажка на которой оно написано, возвращается в шляпу, и ход передаётся какой-то случайной команде, возможно, той же самой. Игра продолжается, пока все слова из шляпы не будут отгаданы. Теперь Максим провёл турнир для N команд из своей школы и должен определить победителя. Он неаккуратно вёл записи игры и не отмечал, сколько слов отгадала каждая из команд, зато он записывал в хронологическом порядке каждый раз, когда какая-либо команда доставала какую-либо бумажку из шляпы. Всего таких записей M , и они следуют в хронологическом порядке. Помогите Максиму восстановить по сделанным записям, сколько слов отгадала каждая из команд. Входные данные В первой строке дано количество команд N и количество попыток отгадать слова M ( 1 ≤ N ≤ 100 000 , 1 ≤ M ≤ 100 000 ). В следующих M строках сначала указывается номер n i команды, пытавшейся отгадать слово, а через пробел дано слово w i , написанное на бумажке. Номера команд лежат в диапазоне от 1 до N . Все слова w i состоят из строчных латинских букв и имеют ненулевую длину, не превосходящую 10 букв. Выходные данные Выведите в одну строку N чисел, i -ое число должно равняться количеству слов, отгаданному i -ой командой. Примеры тестов входные данные 2 3 1 hat 1 shirt 2 hat входные данные выходные данные 1 1 3 2 1 mom 3 dad Примечание В первом примере первая команда отгадала слово shirt , а вторая слово hat Система оценки Каждый тест в данной задаче оценивается отдельно. Решение тестируется на основном наборе тестов только при прохождении всех тестов из условия. При этом тесты из условия не оцениваются. Подзадача 1. 1 ≤ N ≤ 2000 , 1 ≤ M ≤ 2000 . Каждое слово встречается только один раз. Оценивается из 20 баллов. Подзадача 2. 1 ≤ N ≤ 2000 , 1 ≤ M ≤ 2000 . Оценивается из 30 баллов. Подзадача 3. 1 ≤ N ≤ 100 000 , 1 ≤ M ≤ 100 000 . Оценивается из 50 баллов. выходные данные 1 0 1 Метро Метрополитен состоит из нескольких линий метро. Все станции метро в городе пронумерованы натуральными числами от 1 до N . На каждой линии расположено несколько станций. Если одна и та же станция расположена сразу на нескольких линиях, то она является станцией пересадки и на этой станции можно пересесть с любой линии, которая через нее проходит, на любую другую (опять же проходящую через нее). Напишите программу, которая по данному вам описанию метрополитена определит, с каким минимальным числом пересадок можно добраться со станции A на станцию B Если данный метрополитен не соединяет все линии в одну систему, то может так получиться, что со станции A на станцию B добраться невозможно, в этом случае ваша программа должна это определить. Входные данные Сначала вводится число N — количество станций метро в городе (2≤ N ≤100). Далее следует число M — количество линий метро (1≤ M ≤20). Далее идет описание M линий. Описание каждой линии состоит из числа P — количество станций на этой линии (2≤ P ≤50) и P чисел, задающих номера станций, через которые проходит линия (ни через какую станцию линия не проходит дважды). Затем вводятся два различных числа: A — номер начальной станции, и B — номер станции, на которую нам нужно попасть. При этом если через станцию A проходит несколько линий, то мы можем спуститься на любую из них. Так же если через станцию B проходит несколько линий, то нам не важно, по какой линии мы приедем. Выходные данные Выведите минимальное количество пересадок, которое нам понадобится. Если добраться со станции A на станцию B невозможно, программа должна вывести одно число –1 (минус один). Примеры входные данные 5 2 4 1 2 3 4 2 5 3 3 1 входные данные 5 5 2 1 2 2 1 3 2 2 3 2 3 4 i i i выходные данные 0 2 4 5 1 5 входные данные 10 2 6 1 3 5 7 4 9 6 2 4 6 8 10 7 3 8 входные данные 4 2 2 1 2 2 3 4 1 3 выходные данные 2 выходные данные 1 выходные данные -1 Занимательная экономия В известной сети гипермаркетов Heap-Hop ежегодно проводится следующая акция. В декабре при покупке любого товара стоимостью не меньше 1 000 руб., за каждую целую тысячу рублей в стоимости одного товара выдаётся купон номиналом в 500 руб. Например, если мы покупаем в декабре один товар стоимостью 1 001 руб., а второй — 2 999 руб., то получим купон в 500 руб. за первый и всего два купона за второй. В январе полученные купоны можно использовать для оплаты 20% стоимости уже всей покупки в целом. То есть вне зависимости от стоимости отдельных товаров, если в январе общая сумма покупки в нашем примере будет не меньше 7 500 руб., то 1 500 мы оплатим купонами, а если меньше, то мы не сможем использовать все купоны полностью. Но даже за покупку стоимостью меньше 500 руб. мы сможем получить скидку в 20% , отдав купон номиналом 500 руб. Семья Бережливых давно присмотрела ряд товаров в одном из гипермаркетов этой сети. Зная условия акции, они решили распределить покупки на два месяца так, чтобы в итоге заплатить за все товары вместе как можно меньше. Младший сын Бережливых Иван взялся написать программу, которая и выдаст соответствующие рекомендации, но родители не уверены, что его программа будет находить минимально возможную сумму денег, которой можно обойтись при покупке всех необходимых товаров с учётом акции. Поэтому подобную программу предлагается написать вам. Входные данные В первой строке входных данных находится число N — количество товаров, которые хочет купить семья Бережливых. Во второй строке записаны через пробел целые положительные числа c i — цены товаров. Каждого товара необходимо купить ровно одну единицу, но стоимости различных товаров могут совпадать. Выходные данные Выведите одно вещественное число — минимальное количество рублей, которым можно обойтись при оплате всей покупки с использованием акции. Обратите внимание, ответ всегда выражается целым количеством копеек. Примеры тестов входные данные 2 1000 1000 входные данные 3 1000 2000 500 выходные данные 1800.00 выходные данные входные данные 2 1001 1002 Примечание В первом примере мы покупаем любой из предметов в первый месяц и получаем купон на 500 рублей. Тем не менее при покупке второго предмета можно будет оплатить не более 20% стоимости, что составит 200 рублей. Система оценки Решение тестируется на основном наборе тестов только при прохождении всех тестов из условия. При этом тесты из условия не оцениваются. Подзадача 1. 1 ≤ N ≤ 20 , стоимость любого товара не превосходит 5 000 . Оценивается из 40 баллов. Баллы начисляются только при прохождении всех тестов данной подзадачи. Решения, не прошедшие все тесты в этой подзадаче, дальше не тестируются. Подзадача 2. 1 ≤ N ≤ 100 , стоимость любого товара не превосходит 5 000 Оценивается из 30 баллов. Каждый тест оценивается отдельно. Подзадача 3. 1 ≤ N ≤ 1 000 , стоимость любого товара не превосходит 50 000 Оценивается из 30 баллов. Каждый тест оценивается отдельно. 3000.00 выходные данные 1802.60 K-специальные таблички Чего не сделаешь ради того, чтобы выделиться из серой массы. Кто-то танцует, кто-то учит наизусть правила русского языка, кто-то пытается стать выдающимся спортивным программистом, ну а кто-то коллекционирует забавные математические объекты. Алиса как раз из таких коллекционеров. Сейчас она очень хочет заполучить k - специальную табличку. Напомним, что табличка n называется k -специальной, если выполнены следующие три условия: * каждое число от 1 до n встречается в ней ровно 1 раз; * в каждой строке числа идут в возрастающем порядке; * сумма чисел, расположенных в k -м столбце, максимальна. Помогите Алисе! Отыщите хотя бы одну k -специальную табличку размера n Строки и столбцы нумеруются от 1 до n , при этом строки нумеруются сверху вниз, а столбцы слева направо. Входные данные В первой строке входных данных записаны два числа n и k ( 1 00 ) — размер искомой таблички и номер столбца, сумма в котором должна быть максимальна. Выходные данные В первой строке выведите сумму чисел в k -м столбце искомой таблички. В следующих n строках выведите саму табличку: сначала n элементов первой строки, затем n элементов второй и так далее. Если искомых табличек несколько, то выведите любую из них. Примеры входные данные 4 1 входные данные 5 3 n 2 n n 5 1 k n выходные данные 28 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 выходные данные 85 1 2 11 12 13 3 4 14 15 16 5 6 17 18 19 7 8 20 21 22 9 10 23 24 25 |