WWW.KN.LIB-I.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Различные ресурсы
 


«Цикл Интернет-олимпиад для школьников, сезон 2011-2012 Третья индивидуальная олимпиада. 17 декабря 2011 года. Задача A. Кубики Имя ...»

Цикл Интернет-олимпиад для школьников, сезон 2011-2012

Третья индивидуальная олимпиада. 17 декабря 2011 года.

Задача A. Кубики

Имя входного файла: cubes.in

Имя выходного файла: cubes.out

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 мегабайт

Когда Вова был маленьким, родители подарили ему набор из n кубиков, на каждом из которых

написано некоторое натуральное число. В этом наборе нет двух кубиков, на которых написаны

одинаковые числа.

Недавно, вспомнив про этот набор, Вова достал все кубики и разложил их в один ряд.

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

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

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

Зайдя в комнату, Вова сразу почуял неладное. Допросив Олю, он узнал как получилось так, что кубики перемешались. И тут Вову заинтересовало — может ли он выяснить каким количеством кубиков играл Петя (при этом Оля играла оставшимися)? Он поручил вам решить эту задачу!

Формат входного файла Первая строка входного файла содержит единственное число n (1 n 300000) — количество кубиков у Вовы.

Вторая строка содержит n целых чисел ai (1 ai 109 ) — числа, написанные на кубиках, выложенных в порядке слева направо в тот момент, когда Вова вернулся домой. Все ai различны.

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

Примеры cubes.in cubes.out Примечание Решения, работающие при n 1000 будут оцениваться из 40 баллов.

Страница 1 из 5 Цикл Интернет-олимпиад для школьников, сезон 2011-2012 Третья индивидуальная олимпиада. 17 декабря 2011 года.

Задача B. Стаканчики Имя входного файла: stacks.in Имя выходного файла: stacks.out Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт С самого раннего детства Маша мечтала облететь весь земной шар и побывать в разных странах.

И вот наконец-то её мечта сбылась — ей предложили работу в одной из крупнейших авиакомпаний мира. Теперь Маша работает стюардессой. В её обязанности входит разносить еду и напитки пассажирам, а также собирать использованную посуду.

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





Перед началом сбора использованной посуды Маша знает, сколько напитка в стакане осталось у каждого пассажира. Теперь ее интересует вопрос — сможет ли она донести поднос со стаканчиками, не уронив его. Для этого ей необходимо знать высоту самой большой стопки. Но так как пассажиров очень много, она не может посчитать это сама, поэтому просит вас помочь ей!

Формат входного файла В первой строке входного файла задано единственное целое число n — количество пассажиров (1 n 106 ).

В следующей строке через пробел заданы n целых чисел ai — количество оставшегося напитка в стаканчиках (0 ai 100) в том порядке, в котором Маша будет их собирать. Пустому i-ому стакачику соответствует ai = 0.

Формат выходного файла В выходной файл выведите единственное целое число — количество стаканчиков в самой большой стопке.

Примеры stacks.in stacks.out Примечание Решения, корректно работающие для n 1000 будут оцениваться из 40 баллов.

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

–  –  –

Задача C. Интересные числа Имя входного файла: interesting.in Имя выходного файла: interesting.out Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт Вася — юный математик. Папа часто рассказывает ему истории связанные с папиным детством, особенно то, что он, как и многие его сверстники, любил коллекционировать марки. У каждой марки была своя история, и папа Васи все эти истории помнил до последних мелочей. Особенными были истории о том, как были добыты марки из серии «Раритетные автомобили». Васе очень нравились рассказы его отца. Он тоже решил попробовать себя в этом деле. Так как Вася любил не раритетные автомобили, а математику, он решил собирать марки с различными числами.

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

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

Например, если k = 2, то марки с числами 22, 111, 100, 556 являются интересными, а с числами 2, 121, 1212 не являются.

Вам заданы числа a, b и k. Требуется посчитать количество интересных марок с числами от a до b.

Формат входного файла Во входном файле заданы три целых числа a, b (1 a b 4 · 1018 ) и k (1 k 20).

Формат выходного файла В выходной файл выведите единственное целое число — ответ на задачу.

Примеры interesting.in interesting.out Примечание Решения, работающие при 1 a b 106 будут оцениваться из 40 баллов.

В первом примере интересными являются марки с числами 11, 22, 33, 44, 55, 66, 77, 88, 99 и 100.

Во втором примере интересными являются марки с числами 111, 112, 113, 114, 115, 116, 117, 118, 119, 122 и 133.

–  –  –

Задача D. Карточки Имя входного файла: cards.in Имя выходного файла: cards.out Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт Вова очень тихий мальчик, он очень любит тихонько сидеть и что-нибудь делать. Недавно родители подарили Вове набор карточек, на которых написаны различные слова из латинских букв.

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

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

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

Формат входного файла В первой строке входного файла содержится слово t, названное родителями. Длина этого слова не превышает 105.

В следующей строке задано число n (1 n 105 ) — количество имеющихся различных карточек у Вовы. Далее следует n строк, каждая из которых содержит слово, написанное на карточке. Сумма длин всех слов на карточках не превосходит 105.

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

Формат выходного файла В первой строке выходного файла необходимо вывести единственное число k — количество использованных карточек (в том числе и полученных с помощью копировальной машины). Во второй строке необходимо вывести слово s, сложенное из k Вовиных карточек и содержащее слово t как подстроку. Если ответов несколько, выведите любой.

Если невозможно выложить карточки заданным образом, выведите в выходной файл единственную строку «No solution».

–  –  –

Примечание Решения, работающие при сумме длин слов на карточках не превосходящей 1000, N 100 и длине строки t не более 1000 символов будут оцениваться из 20 баллов.

Решения, работающие при сумме длин слов на карточках не превосходящей 105, N 1000 и длине строки t не более 10000 символов будут оцениваться из 60 баллов.




Похожие работы:

«Інженерні системи та техногенна безпека Випуск 2013 5(103) УДК 629.13 А. Н. НАЗАРЕНКО Запорожская государственная инженерная академия РАЗРАБОТКА КОНЦЕПЦИИ УПРАВЛЕНИЯ НАДЕЖНОСТЬЮ СИСТЕМ ПРОИЗВОДСТВЕННОГО ВОДОСНАБЖЕНИЯ Система водоснабжения представляет собой комплекс сооружений для обеспечения группы потребителей в...»

«Т7-1100 УВАЖАЕМЫЙ ПОКУПАТЕЛЬ! Мы благодарим Вас за предпочтение, оказанное нашей продукции. Каждый прибор марки "ВАСИЛИСА" отличается современным эргономичным дизайном и высоким качеством исполнения. Приобретая наш электрический чайник, Вы можете быть уверены...»

«СИСТЕМА УПРАВЛЕНИЯ НАГРЕВОМ БЫСТРОДВИЖУЩИХСЯ ТРУБНЫХ ЗАГОТОВОК В ИНДУКЦИОННЫХ ПРОХОДНЫХ ПЕЧАХ Одним из наиболее эффективных методов подогрева и выравнивания температуры трубных заготовок перед прокаткой в редукционном стане при производстве бесшовных труб является индукци...»

«1. Не настаивайте на своей позиции Касаются ли проводимые вами переговоры важного контракта, семейной проблемы или установления мира во всем мире, людям часто приходится идти на позици...»

«ПАО МТС Тел. 8-800-250-0990 www.corp.irkutsk.mts.ru Успех Федеральный/городской номер Авансовый/кредитный метод расчетов Ежемесячная плата за тариф Федеральный номер 280,00 Городской номер 280,00 в том числе: на мобильные телефоны абонентов МТС Иркутской области и других регионов России 30 минут в сутки на мобиль...»

«"АВЕРС" ИНФОРМАЦИОННО-АНАЛИТИЧЕСКАЯ СИСТЕМА "АВЕРС: ЭЛЕКТРОННЫЙ КЛАССНЫЙ ЖУРНАЛ" (ВЕРСИЯ 3.1) РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ Телефоны: +7 (495) 909-03-60, +7 (903) 250-61-59 Электронная почта: office@iicavers.ru, h-line@iicavers.ru Skype: avers-journal...»

«HP iPAQ Руководство по продукту © Copyright 2007 Hewlett-Packard Data Source © 2007 Tele Atlas N.V. Development Company, L.P. © BEV, GZ 1368/2003 В продуктах HP iPAQ используется © DAV, нарушение данных авторских...»

«Чайник электрический RК-G135 АНТИ АР Г Я М В ЕС ЯЦЕ РУКОВОДСТВО ПО ЭКСПЛУАТАЦИИ УВАЖАЕМЫЙ ПОКУПАТЕЛЬ! Благодарим за то, что вы отдали предпочтение бытовой технике REDMOND. REDMOND — это качество, надежност...»

«Улучшение прототипа Окошки и сценарии использования Окошки: 1) connect to server 2) ftp browser 3) edit questions 4) choose encoding 5) license key 6) install ATC 7) about 8) protect script Для перехода с (1...»

«Инженерный Центр СтройЭнергоПроект Профессиональное проектирование зданий и сооружений НАМ ДОВЕРЯЮТ Свидетельство СРО о допуске к проектным работам П-008-6321234234-29012016-104 Тел./факс: (8482) 30-54-22, 50-82-06, 555-790 e-mail: fskstroyenergo@list.ru сайт: www.icsep.ru О ЦЕНТРЕ Инженерный Центр СтройЭнергоПроект — ведущая п...»








 
2017 www.kn.lib-i.ru - «Бесплатная электронная библиотека - различные ресурсы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.