25 октября 2023 Ответы для 5, 6, 7, 8, 9, 10, 11 классов олимпиада по информатике Сириус школьный этап 2023 ВСОШ
Задания и ответы олимпиады по информатике для 5, 6, 7, 8, 9, 10, 11 класса Сириус школьного этапа 2023 всероссийской олимпиады школьников ВСОШ 2 группы регионов, для тех, кто пишет 25 октября. Решение задачи проходит на официальном сайте Сириус курсы uts.sirius.online.
Все ответы и решения для заданий: скачать
Ответы для 5-6 класса олимпиада Сириус по информатике
Задание 1: Волшебные дни
Совсем скоро наступит волшебный день —— 31 декабря! Он является волшебным, потому что в его записи —— 31.12.23 —— цифры 1, 2 и 3 встречаются по два раза. Вы решили воспользоваться свойством волшебного дня и отправиться в будущее, то есть в дату после 31 декабря 2023 г. Вам доступны только те даты, в записи которых цифры 1, 2 и 3 также встречаются по два раза. Однако вы не сможете отправиться в слишком далёкое будущее, а именно —— после 2100 года.
Определите все даты, в которых вы можете оказаться. Каждую дату записывайте в формате трёх чисел, разделённых точкой —— день, месяц и две цифры года —— в отдельное поле, добавляя их по мере необходимости. Ответы указывайте в порядке наступления дат.
Задание 2: Робот и конфеты
Робот, использующий в качестве источника энергии конфеты, может ходить только по прямой. Чтобы пройти один метр, он тратит одну конфету. У робота есть отсек, вмещающий M конфет. Когда отсек становится пустым, робот застывает на месте и больше не двигается. Вчера робот вышел из дома и, пройдя некоторое расстояние, выложил несколько конфет, сделав тайник. После этого робот вернулся обратно. Сегодня он снова взял из дома конфеты и отправился гулять. Робот решил пройти как можно дальше. Он добрался до тайника с конфетами, пополнил свои запасы и пошёл дальше. Домой он не вернулся —— кончились конфеты. Какое максимальное расстояние он мог пройти сегодня?
Вам нужно решить задачу для нескольких роботов с разными размерами отсеков (разными значениями M).
Задание 3: Великий детектив и статуи
Очередная погоня Шерлока Холмса за преступником завела его в ту часть города, где была целая аллея статуй, выстроенных в ряд. Каждая из них имела свою высоту, которую Шерлок решил записать в блокнот. Холмс очень спешил и потому записал только высоту первой статуи и тех статуй, чья высота была больше или равна высоте предыдущей скульптуры. После поимки преступника Шерлок отдал этот блокнот Ватсону и предложил отгадать высоты всех статуй аллеи. Доктор Ватсон понимал, что точно отгадать их он не сможет, поэтому решил записать один из возможных вариантов. Помогите ему. Длина ответа ограничена и не должна превышать размер записанной Шерлоком последовательности высот более чем в два раза.
Вам нужно решить задачу для нескольких аллей, которые мог видеть Холмс. Для каждой записи детектива подберите возможный вариант высот статуй.
Задание 4: Интересные коробки
Новые коробки для конфет начали выпускать в форме правильных шестиугольников, как изображено на рисунке. Сами конфеты имеют вид правильных треугольников. Буквой L обозначено количество конфет, прилегающих своими сторонами снаружи к одной стороне коробки. Вам необходимо посчитать минимальное количество конфет, которое требуется уложить в коробку, чтобы покупатель не увидел её дна.
Пример коробки с правильной укладкой конфет для L=2 приведён ниже. В такую коробку можно уложить 24 конфеты, чтобы покрыть дно.
Запишите ответ для разных значений L.
Задание 5 : Сломанные часы
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Сегодня утром Миша проснулся и понял, что проспал и теперь опаздывает на олимпиаду! Он быстро собрался, сделал себе чай и по неосторожности пролил его на свои любимые электронные часы, на котором цифры отображаются следующим образом.
К счастью, часы не сломались, но сильно испачкались —— некоторые элементы табло теперь не видно. Помогите Мише определить время в данный момент, если сейчас часы выглядят как на рисунке 1, а через 1 час 8 минут будут выглядеть, как на рисунке 2.
Рисунок 1
Рисунок 2
Запишите все подходящие под условие значения времени в формате ЧЧ:ММ. Каждый ответ записывайте в отдельное поле, добавляя их при необходимости.
Ответы для 7-8 класса олимпиада Сириус по информатике
Задание 1: Игра Арсения
Арсений играет в игру «Раскраска». Мальчик выбирает на белой клетчатой доске, имеющей n строк и m столбцов, начальную клетку и красит её в чёрный цвет, после чего происходит несколько ходов.
За первый ход все непосредственные соседи выбранной клетки (то есть клетки, имеющие с выбранной общую границу) будут окрашены в чёрный цвет.
За второй ход все соседи клеток, окрашенных на предыдущем ходу, тоже окажутся окрашены в чёрный цвет и так далее.
Арсений хочет выбрать начальную клетку таким образом, чтобы таблица окрасилась полностью через как можно меньшее число ходов. Через сколько ходов таблица будет окрашена?
Даны четыре значения n и m, для которых требуется посчитать минимальное число ходов, после которых таблица будет полностью окрашена. Если вы не знаете ответ для какого‑то из примеров, запишите 0.
Номер примера Значение n Значение m Ответ13326632054125125
Задание 2: Капибары
Амир хочет подарить Ляйсан n капибар, пронумерованных натуральными числами от 1 до n.
Ляйсан не может оставить всех капибар у себя, так как любые две капибары, у которых сумма номеров кратна разности номеров, будут ссориться. Капибар, которых девочка не сможет у себя оставить, она подарит ответственным друзьям.
Амир знает, что Ляйсан оставит у себя наибольшее количество капибар. Помогите Амиру узнать номера грызунов, которых оставит у себя Ляйсан для разных значений n. Учтите, что Ляйсан хочет оставить у себя как можно больше капибар.
Даны четыре возможных значения n, для которых Амир хочет узнать ответ. Для каждого примера запишите через пробел номера капибар, которых Ляйсан сможет оставить у себя.
Номер примера Значение n Номера капибар 132538415
Задание 3: Секретные слова
Ваш знакомый Петя работал шифровальщиком на секретном предприятии и столкнулся с проблемой создания нового качественного шифра. После длительной работы ему наконец удалось это сделать. Петя попросил вас оценить его труды.
В шифре Пети запрещено использовать слова, в которых есть хотя бы две подряд идущие буквы, такие, что и в алфавите они тоже идут подряд. Например, слова «аббревиатура», «деятельный» —— содержат пары букв АБ и ДЕ соответственно. Такие слова в шифре использовать нельзя. А вот слово «банк» —— подходит для шифра Пети.
Дана последовательность букв —— Б, А, Й, Т —— из которой необходимо составить как можно больше слов для шифра Пети. Каждую букву из набора можно использовать только один раз. Словом считается любая последовательность символов, не обязательно осмысленная.
Выпишите все возможные четырёхбуквенные слова для шифра, используя для каждого слова заданный набор целиком. Каждое слово записывайте в отдельное поле, добавляя их по мере необходимости.
Задание 4: Трёхзначный вариант
Ваш учитель математики для подготовки к контрольной создал огромное количество вариантов (с номерами от 100 до 999) и выдал их ученикам заранее. При этом, чтобы у учеников появился интерес, он поставил интересное условие. На доске написано три трёхзначных числа. Учитель сказал, что если ученик сможет назвать ещё одно трёхзначное число, такое, что у него будет совпадать с каждым из написанных чисел ровно один разряд, то ученик может выбрать этот вариант. При этом вы понимаете, что сложность вариантов возрастает с увеличением их номера.
Постарайтесь выбрать минимальное число, удовлетворяющее заданному условию, тогда вы с лёгкостью получите отличную оценку на контрольной. Поняв алгоритм действий, помогите трём своим лучшим друзьям.
Даны четыре примера троек чисел, записанных на доске. Для каждого из них укажите минимальное возможное трёхзначное число, удовлетворяющее заданному условию. Если вы не знаете ответ для какого‑то из примеров, запишите 0.
Номер примера Числа на доске Ответ 1123 456 7892373 886 8933316 526 5144147 545 126
Задания по программированию.
Задание 1: Вирус
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
По сети распространяется вирус, который заражает по t компьютеров в конце каждого дня. Специалист по информационной безопасности Евгений узнал про вирус и уже готовится от него избавиться. Как только вирус заразит хотя бы k компьютеров, Евгений сразу же идентифицирует угрозу и начнёт с ней работать. Однако, чтобы обезвредить вирус, Евгению понадобится ещё m дней, и только в конце m-го дня ему удастся спасти пользователей сети.
Сейчас Евгений занят расчётами —— ему интересно, сколько суммарно дней пройдёт прежде, чем вирус будет обезврежен. Помогите Евгению ответить на этот вопрос.
Формат входных данных
Первая строка содержит одно целое число t (1⩽t⩽109) —— количество компьютеров, которые заражаются вирусом каждый день.
Вторая строка содержит одно целое число k (1⩽k⩽109) —— количество компьютеров, которые должен заразить вирус, чтобы его можно было идентифицировать.
Третья строка содержит одно целое число m (1⩽m⩽109) —— количество дней, которые понадобятся Евгению, чтобы обезвредить вирус после его обнаружения.
Формат выходных данных
Выведите одно целое число —— количество дней, которые потребуются Евгению, чтобы избавиться от вируса, начиная с момента его появления.
Система оценки
Решения, правильно работающие при k⩽100 000, будут оцениваться в 30 баллов.
Решения, правильно работающие при k, делящемся на t, будут оцениваться в 45 баллов.
Замечание
Рассмотрим первый пример. В нём вирус заражает по два компьютера в конце каждого дня. Чтобы идентифицировать вирус, необходимо, чтобы было заражено хотя бы три компьютера. Это означает, что вирус будет найден только в конце второго дня. После чего Евгению потребуется ещё один день, чтобы обезвредить вирус. Таким образом, в конце третьего дня вирус будет обезврежен.
Задание 2: Кинотеатр
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Евгений насколько усердно боролся с компьютерным вирусом, что сам заболел, и, поскольку он не мог оставить работу, Евгений заразил всех своих коллег, которые заразили своих знакомых и так далее. В итоге весь ваш город оказался заражён. На фоне этой эпидемии власти ввели масочный режим, а в ваш любимый кинотеатр «Малина» теперь пускают только по электронному сертификату о прививке.
Сегодня вы решили сходить в ваш любимый кинотеатр. Подойдя ко входу в здание кинотеатра, вы встали в очередь, в которой вместе с вами находятся n человек. В начале очереди у посетителей проверяют наличие сертификата о прививке. Подтверждение сертификата каждого посетителя занимает q секунд, после чего человек отправляется в зал на показ фильма. Как и всегда, у входа в зал собралась очередь из m человек с билетами, которые предстоит проверить контролёру. Проверка билета одного человека занимает t секунд, после чего человек сразу же занимает место в кинозале.
Перерыв в кинотеатре закончится с минуты на минуту, после чего очереди двинутся, и в скором времени вы сможете посмотреть фильм. Но вас, как настоящего программиста, интересуют точные значения. Поэтому, пока перерыв не закончился, вам предлагается написать программу, которая по заданным значениям n, q, m и t посчитает, сколько секунд вам придется подождать после окончания перерыва, прежде чем вы окажетесь в кинозале.
Формат входных данных
Первая строка содержит одно целое число n (1⩽n⩽109) —— количество человек в первой очереди, считая вас.
Вторая строка содержит одно целое число q (1⩽q⩽109)—— время проверки сертификата.
Третья строка содержит одно целое число m (1⩽m⩽109) —— количество людей во второй очереди.
Четвёртая строка содержит одно целое число t (1⩽t⩽109) —— время проверки билета контролёром.
Формат выходных данных
Выведите одно целое число —— количество секунд, по истечении которых вы окажетесь в кинозале.
Система оценки
Решения, правильно работающие в ситуации, когда последнему человеку из первой очереди после прохода контроля сертификата не придётся ждать проверки во второй очереди, будут оцениваться в 50 баллов.
Решения, правильно работающие в ситуации, когда в момент прохода контроля сертификата последним человеком из первой очереди вторая очередь ещё не пуста, будут оцениваться в 50 баллов.
Замечание
Рассмотрим первый тестовый пример. В первой очереди стоят два человека, каждому из которых требуется одна секунда, чтобы перейти во вторую очередь. Во второй очереди стоят три человека, каждому из которых также требуется по секунде, чтобы выйти из очереди.
Таким образом, в первую секунду первый человек из первой очереди перейдёт во вторую очередь, а первый человек из второй покинет очередь. После чего во второй очереди останется три человека, а в первой—— один. По истечении второй секунды оставшийся в первой очереди человек перейдёт во вторую, а первый человек из второй очереди покинет её. Таким образом, во второй очереди останется три человека, а в первой уже никого не останется. После чего этим трём людям потребуется суммарно три секунды, чтобы пройти очередь. Поэтому ответ в данном случае —— пять секунд.
Обратите внимание, что ответы могут получиться достаточно большими, поэтому следует использовать 64-битный тип данных, например long long в C/C++, long в Java, int64 в Free\Pascal.
Задание 3: Подотрезок
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Переполненные впечатлениями после фильма, вы вышли из кинотеатра. «Побег из матрицы» оставил очень много вопросов без ответа.
В самом конце фильма была показана битовая строка s, состоящая из n символов, каждый из которых был равен 0 или 1. Играла напряжённая музыка, и Мёбиусу предстояло принять судьбоносное решение. Он должен был выбрать два индекса l и r, после чего инвертировать биты на подотрезке sl, sl+1, …… , sr. Иными словами, на выбранном подотрезке Мёбиус должен был заменить каждый символ, равный 0, на 1 и наоборот. Судьба Мёбиуса зависела от того, сможет ли он найти такие индексы, чтобы после инвертирования битов на соответствующем подотрезке битовая строка s состояла бы из одинаковых символов.
И вот, в самый интересный момент фильм закончился, а зрители так и не узнали, какой выбор сделал Мёбиус. Не желая дожидаться следующей части фильма, вы захотели сами разгадать тайну. Для этого вы решили написать программу, которая по заданной строке s, состоящей из n символов, найдёт такие индексы l и r, что после инвертирования битов на подотрезке sl, sl+1, …… , sr строка s будет состоять из одинаковых символов.
Формат входных данных
Первая строка содержит одно целое число n (1⩽n⩽100 000).
Вторая строка состоит из n символов 0 или 1 и описывает битовую строку s.
Формат выходных данных
Выведите два целых числа l и r (1⩽r⩽n) —— границы подотрезка, который мог бы выбрать Мёбиус. Если существует несколько подходящих пар индексов, выведите любую из них. Если такого подотрезка не существует, выведите число −1.
Система оценки
Решения, правильно работающие при n⩽100, будут оцениваться в 30 баллов.
Решения, правильно работающие при n⩽1000, будут оцениваться в 60 баллов.
Замечание
В первом примере Мёбиус мог выбрать подотрезок, который состоит из одного символа, стоящего на второй позиции. Тогда после инвертирования второго бита строка «010» станет равна строке «000», состоящей только из нулей.
Во втором примере Мёбиус мог выбрать всю строку как подотрезок, тогда после инвертирования строка будет равна строке «1111», состоящей только из единиц.
Ответы для 9-11 класса олимпиада Сириус по информатике
Задание 1: Флеш и Зум на пробежке
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Флеш и Зум сильно постарели, из‑за чего у них больше нет сил для того, чтобы сражаться друг с другом. Поэтому сейчас они просто друзья, которые каждое утро выходят на пробежку.
Сегодня они решили бегать по стадиону, который представляет собой окружность длины d километров. Герои одновременно начнут бежать в одном направлении из одной точки. При этом Флеш побежит со скоростью v1 км/с, а Зум —— со скоростью v2 км/с. После t секунд бега они оба остановятся и будут отдыхать. А вам нужно посчитать, сколько километров ещё надо пробежать Флешу (не обязательно в том же направлении, в котором он бежал ранее), чтобы оказаться с Зумом в одной точке.
Формат входных данных
Первая строка содержит одно целое число d (1⩽d⩽109) —— длину стадиона в километрах.
Вторая строка содержит одно целое число v1 (1⩽v1⩽109) —— скорость Флеша в км/с.
Третья строка содержит одно целое число v2 (1⩽v2⩽109)—— скорость Зума в км/с.
Четвертая строка содержит одно целое число t (1⩽t⩽109) —— длительность пробежки в секундах.
Гарантируется, что v1⋅t⩽109 и v2⋅t⩽109.
Формат выходных данных
Выведите одно целое число —— минимальное количество километров, которое необходимо пробежать Флешу, чтобы оказаться с Зумом в одной точке.
Система оценки
Решения, правильно работающие при t⩽100 000, будут оцениваться в 50 баллов.
Замечание
Рассмотрим первый пример. За три секунды Флеш пробежит 9 километров, а Зум —— 15 километров. Тогда расстояние по направлению бега от Флеша до Зума будет равно 6 километрам, а если Флеш развернётся, то 4 километрам. Таким образом, ответ —— 4 километра.
Задание 2: Миша и сериалы
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Недавно вышел новый сезон любимого сериала Миши. Каждая серия длится ровно n секунд. При этом перед началом каждой серии проигрывается одинаковое интро длиной m секунд, которое очень надоело Мише.
Миша купил себе новую клавиатуру, на которой есть кнопка для перемотки видео. Одно нажатие на такую кнопку перематывает воспроизведение видео на k секунд вперёд. Нажатие на кнопку и перемотка происходят мгновенно, а также Мише не нужно делать перерывов между нажатиями, поэтому он может мгновенно несколько раз нажать на кнопку перемотки.
К сожалению, не всегда удаётся перемотать интро так, чтобы не потерять ни секунды событий сериала. Миша решил, что если придётся пропустить не более чем t секунд сериала, то он готов смириться с этим. Теперь Мише интересно, какое максимальное количество секунд сериала он посмотрит, если пропустит как можно больше интро, не пропустив при этом более t секунд сериала.
Проще говоря, если у Миши получится перемотать интро целиком, потеряв при этом не более t секунд сериала, то он поступит именно так. Иначе он пропустит столько секунд интро, сколько возможно.
Формат входных данных
Первая строка содержит одно целое число n (1⩽n⩽109) —— длительность одной серии в секундах.
Вторая строка содержит одно целое число m (0⩽m⩽109)—— длительность интро в секундах.
Третья строка содержит одно целое число k (1⩽k⩽109) —— количество секунд, которые перематываются при нажатии на кнопку.
Четвёртая строка содержит одно целое число t (0⩽t<n) —— максимальное количество секунд сериала, которые Миша готов пропустить.
Формат выходных данных
Выведите одно целое число —— количество секунд сериала, которые посмотрит Миша.
Система оценки
Помимо примеров из условия, задача содержит 25 тестов. Каждый из них оценивается в 4 балла.
Замечание
В первом примере серия начинается с интро длиной 5 секунд, после чего начинается основная часть серии, которая длится 10 секунд. За одно нажатие на кнопку Миша проматывает 2 секунды, при этом он готов пропустить не более 1 секунды сериала. Поэтому мальчик может три раза нажать на кнопку перемотки, после чего он посмотрит 9 секунд сериала.
Во втором примере Миша не готов жертвовать просмотром серии, поэтому он посмотрит всю серию целиком, перемотав 4 секунды интро из 5.
В третьем примере Миша сможет полностью пропустить интро за два нажатия, после чего он посмотрит всю серию.
Задание 3: Серверы
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Школьный этап всемарсианской олимпиады по информатике проводится на лучшей тестирующей системе. Однако участникам неизвестно, как устроена система внутри. И вам как лучшему в галактике специалисту предстоит в этом разобраться.
Тестирующая система располагается на n(n+1)2+1 серверах, пронумерованных целыми числами от 1 до n(n+1)2+1. Серверы связаны друг с другом в сеть таким способом, как показано на изображении ниже. Прямоугольниками обозначены серверы, для каждого сервера указан его номер. Линиями указаны кабели, соединяющие серверы.
Главный сервер системы имеет номер 1. Остальные серверы соединены в n цепочек при помощи кабелей. Первая цепочка состоит из n серверов с номерами от 2 до n+1. Вторая цепочка состоит из n−1 серверов с номерами от n+2 до 2n. Третья цепочка состоит из n−2 серверов с номерами от 2n+1 до 3n−2. И так далее. Последняя цепочка состоит из одного сервера с номером n(n+1)2+1. Серверы в каждой цепочке соединены друг с другом, как показано на иллюстрации. Главный сервер соединён с первым сервером каждой цепочки.
Когда участник отправляет решение задачи на проверку, оно поступает на главный сервер. После этого происходит следующий процесс: сначала главный сервер тратит a секунд на подготовку данных, после чего мгновенно отправляет их первому серверу первой цепочки (то есть серверу с номером 2). Затем главный сервер тратит ещё a секунд на подготовку данных, после чего мгновенно отправляет их первому серверу второй цепочки (то есть серверу с номером n+2). И так далее до тех пор, пока главный сервер не отправит последнее сообщение, которое адресовано первому серверу n-й цепочки.
Каждый из серверов, кроме главного, работает следующим образом: после получения сообщения сервер тратит b секунд на обработку данных, после чего мгновенно передает их следующему серверу в цепочке. Когда данные доходят до последнего сервера цепочки, он тратит b секунд на их обработку, после чего мгновенно передает их предпоследнему серверу в цепочке. После этого данные начинают передаваться между серверами по направлению к началу цепочки таким же образом, каким они передавались ранее (каждый сервер тратит b секунд на обработку данных, после чего передает их предыдущему серверу по цепочке).
Наконец, когда данные проходят по всей цепочке серверов и попадают на первый сервер цепочки, он тратит a секунд на обработку данных и передаёт их на главный сервер. После этого работа данной цепочки серверов прекращается.
Как видите, на Марсе процесс проверки решения участника является достаточно сложной задачей. Вам предстоит вычислить, через сколько времени главный сервер получит обработанные данные от первых серверов всех цепочек. Считайте, что главный сервер получил решение на проверку в момент времени 0.
Формат входных данных
Первая строка содержит одно целое число n (1⩽n⩽104) —— количество цепочек серверов.
Вторая строка содержит одно целое число a (1⩽a⩽104) —— количество секунд, которое тратит на обработку данных главный сервер.
Третья строка содержит одно целое число b (1⩽b⩽104) —— количество секунд, которое тратят на обработку данных остальные серверы.
Формат выходных данных
Выведите одно целое число —— количество секунд после приёма решения на проверку, после которых главный сервер получит обработанные данные от первых серверов всех цепочек.
Обратите внимание, что ответ в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Система оценки
В этой задаче, помимо тестов из условия, есть 20 тестов. Каждый из них оценивается в 5 баллов. Решения, правильно работающие при n⩽105, будут набирать не менее 50 баллов.
Замечание
Рассмотрим первый пример. Перемещение данных по первой цепочке выглядит следующим образом:
- В момент времени 3 сервер 1 передаст данные серверу 2.
- В момент времени 5 сервер 2 передаст данные серверу 3.
- В момент времени 7 сервер 3 передаст данные серверу 4.
- В момент времени 9 сервер 4 передаст данные серверу 3.
- В момент времени 11 сервер 3 передаст данные серверу 2.
- В момент времени 14 сервер 2 передаст данные серверу 1.
Перемещение данных по второй цепочке выглядит следующим образом:
- В момент времени 6 сервер 1 передаст данные серверу 3.
- В момент времени 8 сервер 3 передаст данные серверу 4.
- В момент времени 10 сервер 4 передаст данные серверу 3.
- В момент времени 13 сервер 3 передаст данные серверу 1.
Перемещение данных по третьей цепочке выглядит следующим образом:
- В момент времени 9 сервер 1 передаст данные серверу 4.
- В момент времени 12 сервер 4 передаст данные серверу 1.
Таким образом, главный сервер получит обработанные данные в моменты 14, 13 и 12, поэтому ответ равен 14.
Задание 4: Скучные квартиры
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Как известно, одно из самых весёлых занятий для маленького ребёнка —— звонить в случайные квартиры, используя домофон.
Мальчик Вася решил обзвонить квартиры в своём доме. Всего в доме n квартир, которые пронумерованы целыми числами от 1 до n. Мальчик решил звонить только в квартиры со скучными номерами. Номер называется скучным, если и только если он состоит из одинаковых цифр. Например, квартиры с номерами 222, 1 и 999 являются скучными, а квартиры с номерами 42 и 20 —— не являются.
Для того чтобы Васе было весело, он решил обзванивать квартиры в следующем порядке. Сначала мальчик обзвонит все квартиры с номерами, состоящими только из единиц, в порядке возрастания номеров квартир. Затем он обзвонит все квартиры с номерами, состоящими только из двоек, в порядке возрастания номеров, и так далее. Таким образом, последовательность номеров квартир, в которые будет звонить мальчик, окажется следующей:
1, 11, 111, …… , 2, 22, 222, …… , 3, 33, 333, . . . , 4, 44, 444, …… , 5, 55, 555, …… , 6, 66, 666, …… , 7, 77, 777, …… , 8, 88, 888, …… , 9, 99, 999, ……
Шалость Васи могла бы продолжаться долго, но люди, живущие в квартире с номером k, ответили мальчику, из‑за чего он испугался и сразу же убежал. Теперь Васе интересно, как много квартир он успел обзвонить. Но он ещё очень маленький, поэтому посчитать количество квартир придётся вам.
Формат входных данных
Первая строка содержит одно целое число n (1⩽n⩽109) —— количество квартир в доме.
Вторая строка содержит одно целое число k (1⩽k⩽n) —— номер квартиры, жители которой ответили Васе. Гарантируется, что k является скучным номером.
Формат выходных данных
Выведите одно целое число —— количество квартир, которое успел обзвонить Вася. Обратите внимание, что квартира с номером k также должна быть учтена.
Система оценки
Решения, правильно работающие, если n является скучным номером, будут оцениваться не менее чем в 40 баллов. Решения, правильно работающие, если n⩽1000, будут оцениваться в 60 баллов.
Замечание
В доме из первого примера 100 квартир, а Васе ответили жители 22-й квартиры. То есть Вася успел позвонить в квартиры 1, 11, 2 и 22 (именно в таком порядке), после чего убежал.
В доме из второго примера 10 квартир, и Васе ответили жители квартиры 1.
В доме из третьего примера 100 квартир, а Васе ответили жители 99-й квартиры. Поэтому он позвонил во все квартиры с двузначными и однозначными скучными номерами.
Задание 5: Университетская команда
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Ваш университет вовсю готовится к новому сезону командных олимпиад. Как несложно догадаться, для этого необходимо собрать команду, которая будет представлять учебное заведение.
Всего в университете учатся n студентов, i-й из них имеет силу ai. Для участия в олимпиадах необходимо выбрать ровно k людей и расположить их в каком‑то порядке. Пусть были выбраны студенты с номерами i1, i2, …… , ik (именно в таком порядке). Тогда слабость команды равна |ai2−ai1|+ |ai3−ai2|+ …+|aik−aik−1|. Иначе говоря, слабость команды равна сумме модулей разностей сил соседних участников команды, если их расположить в выбранном порядке. Обратите внимание, что порядок студентов вы выбираете сами.
Администрация университета просит вас определить минимально возможную слабость команды.
Формат входных данных
Первая строка содержит одно целое число n (1⩽n⩽100 000) —— количество студентов, обучающихся в университете.
Вторая строка содержит одно целое число k (1⩽k⩽n) —— количество людей в составе команды.
Каждая из следующих n строк содержит целое число ai (1⩽ai⩽109) —— силу i-го студента.
Формат выходных данных
Выведите одно целое число —— минимально возможную слабость команды.
Система оценки
Решения, правильно работающие при n⩽10, будут оцениваться в 25 баллов.
Решения, правильно работающие при n⩽1000, будут оцениваться в 50 баллов.
Решения, правильно работающие при ai⩽100 000, будут оцениваться в 50 баллов.
Замечание
Рассмотрим пример. Если взять студентов с номерами 1, 5 и 4 (именно в таком порядке), то слабость команды будет равна |1−1|+|2−1|=0+1=1. Можно доказать, что меньшую слабость получить не получится.
Ответы для регионов:
Белгородская область 22. Брянская область 23. Владимирская область 24. Воронежская область 25. город Санкт-Петербург 26. Ивановская область 27. Калининградская область 28. Калужская область 29. Кировская область 30. Костромская область 31. Курская область 32. Ленинградская область 33. Липецкая область 34. Нижегородская область 35. Орловская область 36. Республика Марий Эл 37. Республика Мордовия 38. Республика Татарстан 39. Республика Чувашия 40. Рязанская область 41. Смоленская область 42. Тамбовская область 43. Тверская область 44. Тульская область 45. Ярославская область.