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


«Цикл Интернет-олимпиад для школьников, сезон 2015-2016 Третья личная олимпиада, второй отбор на ИОИП, 7 февраля 2016 года Задача A. Почти ...»

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

Третья личная олимпиада, второй отбор на ИОИП, 7 февраля 2016 года

Задача A. Почти любимые числа

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

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

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

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

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

так как оно всего одно, на тот случай, если ему понадобится несколько чисел, Дэдпул придумал определение — «почти любимое число».

Число называется почти любимым, если оно заканчивается на любимое число Дэдпула. Так например, если любимое число Дэдпула — 25, то почти любимыми числами будут 625, 11225 и 25, а 5 и 2255 — нет.

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

Так как заказов у Дэдпула много, он просит вас помочь ему написать такую программу.

Формат входного файла В единственной строке входного файла содержится два целых числа n, m (1 n m 2 · 109 ) — любимое число Дэдпула и ограничение на размер почти любимого числа.

Формат выходного файла В единственной строке выходного файла выведите единственное число — количество почти любимых чисел, не превосходящих m.

Пример numbers.in numbers.out Система оценивания Первая группа тестов состоит из тестов, для которых выполняется ограничение n однозначное и m 1000. Баллы за эту группу начисляются только при прохождении всех тестов группы.

Стоимость группы составляет 27 баллов.

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

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

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

Обратите внимание на возможность узнать результат проверки вашего решения на всех тестах, нажав на ссылку «Request feedback» на вкладке «Runs».

Страница 1 из 6 Цикл Интернет-олимпиад для школьников, сезон 2015-2016 Третья личная олимпиада, второй отбор на ИОИП, 7 февраля 2016 года Задача B. Пароль от сейфа Имя входного файла: locker.in Имя выходного файла: locker.out Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт Во время первого своего задания Дэдпул понял, что даже с его регенерацией без оружия врагов так просто не одолеть. Поэтому он решил, что настало время открыть сейф, в котором он хранил свое оружие.

Но просто как всегда не получилось. На сейфе оказался замок с кодом, который Дэдпул забыл.

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

С этой задачей он и обратился к вам. Помогите супергерою — скажите, можно ли из набранной комбинации получить палиндром таким способом.

Формат входного файла В единственной строке входного файла содержится строка s (1 |s| 105 ), состоящая из строчных латинских букв.





Формат выходного файла В единственной строке выходного файла выведите «YES», если из строки s можно получить палиндром, поменяв не более двух символов местами и «NO» в противном случае.

Примеры locker.in locker.out abacaba YES abbcb NO abab YES Система оценивания Первая группа тестов состоит из тестов, для которых выполняются ограничения 1 |s| 100.

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

Вторая группа тестов состоит из тестов, для которых выполняется ограничение 1 |s| 2000.

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

Третья группа тестов состоит из тестов, для которых выполняется следующие ограничения:

1 |s| 105, длина строки — четная. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 35 баллов.

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

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

Обратите внимание на возможность узнать результат проверки вашего решения на всех тестах, нажав на ссылку «Request feedback» на вкладке «Runs».

Страница 2 из 6 Цикл Интернет-олимпиад для школьников, сезон 2015-2016 Третья личная олимпиада, второй отбор на ИОИП, 7 февраля 2016 года Задача C. Шифровка Имя входного файла: encryption.in Имя выходного файла: encryption.out Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт Источник, пожелавший остаться неизвестным, прислал Дэдпулу зашифрованное сообщение, в котором сообщались возможные координаты базы противника. Возможные координаты представляли собой отрезок натуральных чисел от x1 до x2 включительно. Шифровалось сообщение довольно простым способом: берется последовательность десятичных записей всех натуральных чисел, записанных подряд без пропусков (1234567891011121314...) и сообщается ее подотрезок [l, r], отвечающий за числа с x1 по x2 включительно. Например, если x1 = 1, x2 = 6, зашифрованное сообщение будет выглядеть так: [1, 6]. А если x1 = 11, x2 = 14, то так: [12, 19].

Однако, получив сообщение, Дэдпул сразу понял, что оно дошло не совсем правильно, возможно, кто-то его испортил по пути. Делать нечего, поэтому теперь по данным числам l, r он хочет понять хотя бы примерные координаты базы: найти все натуральные числа, которые полностью входят в отрезок шифровки.

Формат входного файла В первой строке входного файла записано два числа l, r (1 l r 1018 ) — шифровка, полученная Дэдпулом.

Формат выходного файла В единственной строке выходного файла выведите количество натуральных чисел, полностью содержащихся в отрезке [l, r] строки «1234567891011...», то есть координаты, в которых может находиться база противника. Для лучшего понимания условия смотрите примеры.

Примеры encryption.in encryption.out Комментарий В первом тесте подходят все натуральные числа от 1 до 9.

Во втором тесте подходят только числа 8, 9, 10, 11, 12, 13. У числа 14 в данном отрезке содержится только первая его цифра, поэтому оно не учитывается.

Система оценивания Первая группа тестов состоит из тестов, для которых выполняются ограничения 1 l r 1000. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 23 баллов.

Вторая группа тестов состоит из тестов, для которых выполняется ограничение l = 1. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 26 баллов.

Третья группа тестов состоит из тестов, для которых выполняется следующее ограничение: гарантируется, что сообщение было переслано без ошибок, то есть l, r — начало и конец каких-то натуральных чисел соответственно. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 22 баллов.

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

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

–  –  –

Задача D. Захват провинций Имя входного файла: occupation.in Имя выходного файла: occupation.out Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт Дэдпул решил поквитаться с канадским правительством. Одному ему будет справиться непросто, поэтому он решил осуществить свой план вместе с неподражаемой Копикэт.

Дэдпул решил захватить всю Канаду. А потом отпустить, забавы ради. Канада разбита на несколько административных единиц, для простоты будем называть их провинциями. Некоторые провинции соединены двунаправленными дорогами. Всего в Канаде n провинций и n 1 дорога.

Между любыми двумя провинциями существует единственный простой путь. Иными словами, Канада представляет собой дерево.

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

В некоторые моменты происходят поездки амбулаторной помощи из одной провинции в другую.

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

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

Изначально все провинции свободны.

Если одна или обе конечные провинции поездки находятся под контролем Дэдпула, то они так же учитываются при подсчете.

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

В каждой из следующих n1 строке находятся два натуральных числа u, v (1 u, v n, u = v) — номера провинций, соединеных двунаправленными дорогами. Гарантируется, что заданный граф является деревом.

В следующей строке находится натуральное число m (1 m 105 ) — количество событий.

В каждой из следующих m строк заданы события в хронологическом порядке, в следующем формате:

сначала идет натуральное число t (1 t 2) — тип запроса,

• если t = 1, то далее следует одно натуральное число x (1 x n) — номер провинции, с которой производит действие Дэдпул: захватывает, если до этого провинция была свободна, и освобождает, если до этого провинция была захвачена;

• если t = 2, то далее следуют два натуральных числа x, y (1 x, y n) — номера провинций, между которыми совершается поездка.

Формат выходного файла Для каждой поездки выведите, сколько подконтрольных Дэдпулу провинций встретится на пути ее следования.

–  –  –

Система оценивания Первая группа тестов состоит из тестов, в которых степень каждой вершины дерева не превосходит 2. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 19 баллов.

Вторая группа тестов состоит из тестов, для которых выполняются ограничения n, m 300.

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

Третья группа тестов состоит из тестов, для которых выполняются ограничения n, m 2000.

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

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

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




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

«Игорь Станиславович Прокопенко Территория заблуждений. Запрещенные факты Серия "Военная тайна" Текст предоставлен издательством http://www.litres.ru/pages/biblio_book/?art=6603041 Прокопенко И. С. Территория забл...»

«NS Retail Co. Ltd Company Profile Дистрибьютор компании NS Retail на территории РФ – ООО "Инес трейд" тел: +7(499)653-73-62 тел: +7(499)638-25-93 info@korcosmopt.ru 1. О компании 1.1. NS RETAIL GENERAL :Дата основания: июль 2007г.Бренды: Koelf, P...»

«Москва Издательство АСТ УДК 821.111 ББК 84(4Вел) У37 Серия "Platinum. Звезды фантастического детектива" Оформление серии и дизайн обложки: Юлия Межова Ben H. Winters T Last Policeman he Перевод с английского: Га...»

«ГАРАНТИЙНЫЕ ОБЯЗАТЕЛЬСТВА DATSUN На базе пробега или времени, в зависимости от того, ГАРАНТИЙНЫЕ ОБЯЗАТЕЛЬСТВА что наступит первым (Общий обзор. Подробнее на стр. 3) Годы Километры ГАРАНТИЯ НА НОВЫЙ АВТОМОБИЛЬ Распространяется на весь автомобиль – подроб...»

«УТВЕРЖДАЮ Тшйрбёков января 2014г. РЕШЕНИЕ Ученого совета по вопросам, рассмотренным на заседании Ученого совета 29.01.2014 г. Протокол №5 1. Итоги научно-исследовательской и инновационн...»

«В Д О М О С Т еИ з. * -*| ' Выхолитъ лпа раза въ іі11 Л 1 Г Води иска адресуется въ $ сяцъ 1 и 15. чиселъ. І М I Л, Архангельскъ, въ редакцію • \ Годопая цна 5 р. съ исрес. ** Еиархіольпыхъ Вдомостей. ?•ч/\.* %•"/. №1. 2 го ъ XXVIII. д 15 іюня Ч АСТЬ О Ф Ф И Ц ІА Л ЬН АЯ. —,. • 'л' \ 1 ' /'. •' •.В с чй а ба д...»

«Создание веб-приложений с быстрым интерфейсом Оптимизация JavaScript производительности Николас Закас По договору между издательством "Символ-Плюс" и Интернет-магазином "Books.Ru – Книги России" единственный легальный с...»

«УДК 796.332(092)(410) ББК 75.578 М45 Maarten Meijer Louis van Gaal. The Biography Перевод с английского Александра Радкевича Оформление обложки Галины Смирновой Серия "Биографии выдающихся людей" First published as LOUIS VAN GAAL: THE BIO...»

«Официальные правила рекламной Акции "Выиграй свой Смартфон"1. Общие положения 1.1. Заказчиком и медиапартнером рекламной Акции "Выиграй свой Смартфон" (далее – Акция) является ПрАО "МТС Украина" (далее – Заказчик).1.2. Исполнителем и рекламным партнером ре...»

«  ДАЙДЖЕСТ НОВОСТЕЙ В РОССИЙСКИХ СМИ Комментарии к нормативным документам НАЛОГООБЛОЖЕНИЕ 09 июля 2009 года (обзор подготовлен пресс-службой компании "РУФАУДИТ") Полезные разъяснения Что понимать под вновь созданной организацией для целей применения УСН? Минфин России дает разъяснения Те ситуации, когда Минфину России приходилось "боро...»








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

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