|
|
Пример входных и выходных данных
Покупка билетов За билетами на премьеру нового мюзикла выстроилась очередь из N человек, каждый из которых хочет купить 1 билет. На всю очередь работала только одна касса, поэтому продажа билетов шла очень медленно, приводя «постояльцев» очереди в отчаяние. Самые сообразительные быстро заметили, что, как правило, несколько билетов в одни руки кассир продаёт быстрее, чем когда эти же билеты продаются по одному. Поэтому они предложили нескольким подряд стоящим людям отдавать деньги первому из них, чтобы он купил билеты на всех. Однако для борьбы со спекулянтами кассир продавала не более 3-х билетов в одни руки, поэтому договориться таким образом между собой могли лишь 2 или 3 подряд стоящих человека. Известно, что на продажу i-му человеку из очереди одного билета кассир тратит Ai секунд, на продажу двух билетов — Bi секунд, трех билетов — Ci секунд. Напишите программу, которая подсчитает минимальное время, за которое могли быть обслужены все покупатели. Обратите внимание, что билеты на группу объединившихся людей всегда покупает первый из них. Также никто в целях ускорения не покупает лишних билетов (то есть билетов, которые никому не нужны). Входные данные На вход программы поступает сначала число N — количество покупателей в очереди (1≤N≤5000). Далее идет N троек натуральных чисел Ai, Bi, Ci. Каждое из этих чисел не превышает 3600. Люди в очереди нумеруются, начиная от кассы. Выходные данные Требуется вывести одно число — минимальное время в секундах, за которое могли быть обслужены все покупатели. Примеры Входные данные 23 4 51 1 1Выходные данные 4Выражение Петя - большой любитель математических головоломок. Недавно он прочитал в одном популярном журнале о новой головоломке. Он пытался ее решить несколько дней, но это ему так и не удалось. Помогите Пете справиться с неподдающейся задачей. В ряд выписаны n чисел. Требуется поставить между каждой парой соседних чисел один из знаков "+" или "×" таким образом, чтобы значение получившегося выражения было как можно больше. Использовать скобки не разрешается. Например, для последовательности чисел 1, 2, 3, 1, 2, 3 оптимально расставить знаки следующим образом: 1 + 2 × 3 × 1 × 2 × 3. Значение выражения в этом случае равно 37. Входные данные В первой строке вводится число n (2 <= n <= 200000). Вторая строка содержит n целых чисел - числа, между которыми следует расставить знаки. Все числа находятся в диапазоне от 0 до 109. Выходные данные Выведите оптимальное выражение. В качестве знака "×" выводите символ "*" (звездочку). Если оптимальных решений несколько, выведите любое из них. Примеры Входные данные 61 2 3 1 2 3Выходные данные 1+2*3*1*2*3Шкафы Региональное отделение одного крупного банка заказало два несгораемых шкафа для хранения личных дел своих клиентов. Каждый шкаф имеет несколько ящиков различной высоты, при просмотре снизу вверх ящики в первом шкафу имеют высоту a1, a2, ..., am, а ящики во втором шкафу высоту b1, b2, ..., bn. Шкафы были установлены в узкой нише в стене лицевой стороной друг к другу, поэтому оказалось, что выдвинуть одновременно два ящика, находящиеся напротив друг друга, невозможно. Сотрудники банка постоянно обращаются к личным делам клиентов, поэтому им удобнее держать ящики открытыми в течение рабочего дня. Поскольку пока клиентов у банка немного, использовать все ящики не обязательно. Решено было использовать такое множество ящиков, чтобы их все можно было выдвинуть одновременно и они не мешали друг другу. Чтобы максимально систематизировать работу, необходимо использовать как можно больше ящиков. Помогите сотрудникам банка выбрать, какие ящики следует использовать. Входные данные Первая строка входного файла содержит два целых числа: m и n — количество ящиков в первом и во втором шкафу, соответственно (1 ≤ m, n ≤ 100000). Вторая строка содержит m целых чисел: a1, a2, ..., am высоты ящиков в первом шкафу. Третья строка содержит n целых чисел: b1, b2, ..., bn — высоты ящиков во втором шкафу. Высоты ящиков положительные и не превышают 109. Выходные данные На первой строке входного файла выведите два числа k и l количество ящиков, которые следует использовать в первом и втором шкафу, соответственно. Сумму k + l вам следует максимизировать. На второй строке выведите k целых чисел номера ящиков в первом шкафу, которые следует использовать. На третьей строке выведите l целых чисел номера ящиков во втором шкафу, которые следует использовать. Если оптимальных решений несколько, выведите любое. Примеры Входные данные 5 51 2 3 4 56 4 3 2 1Выходные данные 4 31 2 3 4 3 4 5
Школа танцев В школу бальных танцев профессора Падеграса записались n учеников — мальчиков и девочек. Профессор построил их в один ряд, и хочет отобрать из них для первого занятия группу стоящих подряд учеников, в которой количество мальчиков и девочек одинаково. Сколько вариантов выбора есть у профессора? Входные данные В первой строке задано число n (1 ≤ n≤ 106). Во второй строке задается описание построенного ряда из мальчиков и девочек — строка из n символов a и b (символ a соответствует девочке, а символ b — мальчику). Выходные данные В единственной строке должно содержаться единственное число — количество вариантов выбора требуемой группы. Система оценки Тесты в этой задаче разбиты на группы. Баллы начисляются только за группу целиком в том случае, когда пройдены все тесты группы, а также все тесты предыдущих групп.
Примеры Входные данные 8aabbaabbВыходные данные 10Валютные махинации Петя, изучая, как меняется курс рубля по отношению к доллару и евро, вывел закон, по которому происходят эти изменения (или думает, что вывел). По этому закону Петя рассчитал, каков будет курс рубля по отношению к доллару и евро в ближайшие N дней. У Пети есть 100 рублей. В каждый из дней он может обменивать валюты друг на друга по текущему курсу без ограничения количества (при этом курс доллара по отношению к евро соответствует величине, которую можно получить, обменяв доллар на рубли, а потом эти рубли — на евро). Поскольку Петя будет оперировать не с наличной валютой, а со счетом в банке, то он может совершать операции обмена с любым (в том числе и нецелым) количеством единиц любой валюты. Напишите программу, которая вычисляет, какое наибольшее количество рублей сможет получить Петя к исходу N-го дня. Законы изменения курсов устроены так, что в течение указанного периода рублевый эквивалент той суммы, которая может оказаться у Пети, не превысит 108 рублей. Входные данные Первая строка входного файла содержит одно число N (1≤N≤5000). В каждой из следующих N строк записано по 2 числа, вычисленных по Петиным законам для соответствующего дня — сколько рублей будет стоить 1 доллар, и сколько рублей будет стоить 1 евро. Все эти значения не меньше 0.01 и не больше 10000. Значения заданы точно и выражаются вещественными числами не более, чем с двумя знаками после десятичной точки. Выходные данные В выходной файл выведите искомую величину с точностью не менее двух знаков после десятичной точки. Примеры Входные данные 130.00 9999.99Выходные данные 100.00Увлекательная игра Петя и Маша играют в увлекательную игру. Маша загадывает число от 1 до n, записывает его на чистый тетрадный лист, кладёт в конверт и запечатывает. После этого Петя пытается это число отгадать. Он может задавать любые вопросы про это число: "Верно ли, что это число равно трем?", "Верно ли, что это число – число Фибоначчи?", "Верно ли, что это число простое?" и так далее. Получив ответ "Да", Петя отдает Маше a конфет, а в случае ответа "Нет" – b конфет. В какой-то момент Петя произносит сакраментальную фразу: "Я знаю, что это за число". После этого они распечатывают конверт в присутствии свидетелей, убеждаются в Петиной правоте, и, таким образом, Маша получает внушительную порцию конфет, а Петя – моральное удовлетворение. Петя очень любит играть в эту игру, но его кондитерские запасы ограничены. Поэтому Петя хочет выяснить, какое минимальное количество конфет может ему потребоваться, чтобы отгадать Машино число в худшем случае. Помогите Пете найти указанный минимум. Входные данные Входной файл содержит три целых числа: n (1 ≤ n ≤ 1000), a и b (0 ≤ a, b ≤ 106). Выходные данные Выведите одно число – минимальное количество конфет, которое должен иметь Петя, чтобы отгадать Машино число в худшем случае. Примеры Входные данные 8 1 1Выходные данные 3Входные данные 10 5 0Выходные данные 5Входные данные 7 0 2Выходные данные 2Приключение Теплым весенним днем группа из N школьников-программистов гуляла в окрестностях города Кисловодска. К несчастью, они набрели на большую и довольно глубокую яму. Как это случилось — непонятно, но вся компания оказалась в этой яме. Глубина ямы равна H. Каждый школьник знает свой рост по плечи hi и длину своих рук li. Таким образом, если он, стоя на дне ямы, поднимет руки, то его ладони окажутся на высоте hi + li от уровня дна ямы. Школьники могут, вставая друг другу на плечи, образовывать вертикальную колонну. При этом любой школьник может встать на плечи любого другого школьника. Если под школьником i стоят школьники j1, j2, …, jk, то он может дотянуться до уровня hj1 + hj2 + … + hjk + hi + li. Если школьник может дотянуться до края ямы (то есть hj1 + hj2 + … + hjk + hi + li ≥ H), то он может выбраться из нее. Выбравшиеся из ямы школьники не могут помочь оставшимся. Найдите наибольшее количество школьников, которые смогут выбраться из ямы до прибытия помощи, и перечислите их номера. Входные данные В первой строке входных данных задается натуральное число N (1 ≤ N ≤ 2000) — количество школьников, попавших в яму. Далее в N строках содержится по два целых числа: рост i-го школьника по плечи hi (1 ≤ hi ≤ 105) и длина его рук li (1 ≤ li ≤ 105). В последней строке указано целое число — глубина ямы H (1 ≤ H ≤ 105). Выходные данные В первой строке выведите K — максимальное количество школьников, которые смогут выбраться из ямы. Если K > 0, то во второй строке в произвольном порядке выведите их номера, разделяя их пробелами. Школьники нумеруются с единицы в том порядке, в котором они заданы во входных данных. Если существует несколько решений, выведите любое. Примечание Решение, дающее правильный ответ только при N ≤ 100; H, hi, li ≤ 1000, будет оцениваться из 70 баллов. Примеры Входные данные 1239 239566Выходные данные 0Входные данные 31 21 24 17Выходные данные |
|
101, оцениваются в 30 баллов.