Задания для 5-6 классаОтветы школьного этапа ВСОШ «Сириус» по Информатике 23.10.2024
Задания 5-6 класс
Задание 1. Блины
На столе лежит стопка блинов. Между соседними блинами находится либо сметана, либо одна из двух сладких начинок мёд или варенье. Верхняя и нижняя стороны стопки блинов не покрыты никакими начинками.
Известно, что у каждого блина ровно одна сторона намазана сметаной. Кроме того, одна сторона у трети всех блинов покрыта вареньем, а у 10 блинов одна сторона покрыта мёдом. Найдите общее количество блинов в стопке.
Задание 2. Выражение
Недавно Катя узнала про одну интересную операцию взятие остатка от деления. Обозначается она mod. К примеру, 13 mod5=3, так как при делении числа 13 на 5 получится целое число 2 и остаток 3: 13=5 ∗ 2+3. Таким образом, 26 mod9=8, а 21 mod3=0.
Катя очень любознательна, поэтому она решила изобрести новую операцию и составить задачу с её использованием. И вот что у девочки получилось.
Есть шесть карточек, на которых записаны числа 1, 2, 3, 4, 5, 6, и пять карточек с символом X. Данный символ обозначает некоторую операцию, которая определяется следующим образом: aXb=ab−a mod b, где mod операция взятия остатка от деления a на b. Например, 10X7=10⋅7−10 mod7=70−3=63. Здесь 3 это результат операции взятия остатка от деления 10 на 7.
Составьте из этих карточек правильное математическое выражение, значение которого было бы как можно большим. В ответ запишите строку, содержащую по одной цифре 1, 2, 3, 4, 5, 6 и пять символов X между данными цифрами. Необходимо использовать все карточки, выражение должно начинаться и заканчиваться цифрой.
Пример правильного выражения: 1X2X3X4X5X6. Вычисление данного выражения идёт слева направо, т.е. сначала посчитается значение 1X2, потом выражение (1X2)X3 и т.д. Например, 3X2X4 будет вычисляться следующим образом: сначала посчитаем 3X2=3⋅2−3 mod2=6−1=5, затем полученный результат будет участвовать в операции с 4:5X4=5⋅4−5 mod4=20−1=19. Чем больше окажется результат вашего выражения, тем больше баллов вы получите.
Задание 3. Вёдра с водой
У Кати есть два пустых ведра A и B, имеющих различную ёмкость. Катя может проделывать следующие операции:
1. Набрать полное ведро A.
2. Набрать полное ведро B.
3. Перелить воду из ведра A в B до наполнения B (в ведре A может остаться вода) или до тех пор, пока A не опустеет.
4. Перелить воду из ведра B в A до наполнения A (в ведре B может остаться вода) или до тех пор, пока B не опустеет.
5. Опустошить ведро A.
6. Опустошить ведро B.
Ответьте на вопросы.
1. Известно, что ёмкость ведра A составляет 8 литров, а ведра B 6 литров. Найдите минимальную последовательность операций, которые необходимо выполнить Кате, чтобы после их выполнения в двух ведрах вместе было 4 литра воды. В ответ запишите номера операций без пробелов и запятых, например, 1316. В этом случае Катя сначала набирает воду в ведро A (операция 1), затем переливает из ведра A в ведро B воду (операция 3), потом снова набирает ведро A (операция 1) и, наконец, выливает воду из ведра B (операция 6).
2. Известно, что ёмкость ведра A составляет 8 литров, а ведра B 6 литров. Сколько различных ненулевых объёмов воды в двух вёдрах вместе можно получить в этом случае?
3. Известно, что ёмкость ведра A составляет 8 литров, а ведра B 5 литров. Запишите через пробел все возможные ненулевые объёмы воды, которые можно набрать в оба ведра вместе, используя не более 8 действий.
Задание 4. Правда или ложь
Рядом с Кудыкиной горой есть три села: Правдино, Лжецово и Хитрецово. Достоверно известно, что в селе Правдино живут только правдолюбы, в селе Лжецово лжецы, а в селе Хитрецово хитрецы, которые не хотят, чтобы их обложили налогами, поэтому всегда лгут о своём местоположении, а обо всём остальном могут говорить и правду, и ложь.
Переписчик Иванов пошёл на хитрость: он опросил всех жителей, задавая каждому лишь три вопроса:
1. Ты из села Правдино?
2. Ты из села Лжецово?
3. Ты из села Хитрецово?
На первый вопрос он получил 360 ответов «Да», на второй вопрос и третий вопросы вместе 480 ответов «Нет». Количество ответов «Да» и «Нет» он записывал в журнал, но, к сожалению, часть записей была утеряна, как и информация об общем числе жителей.
Осведомитель из числа жителей сообщил ему два утверждения
1. В селе Лжецово вдвое больше жителей, чем в селе Хитрецово.
2. В сёлах Лжецово и Хитрецово разное число жителей, причём их количество отличается ровно в 2 раза.
Утверждения осведомителя могут быть либо истинными, либо ложными.
Ответьте на вопросы.
1. Сколько всего жителей живёт во всех трёх сёлах?
2. Сколько всего правдолюбов живёт в селе Правдино?
3. Сколько всего лжецов и хитрецов живёт в сёлах Лжецово и Хитрецово вместе?
4. Сколько лжецов живёт в селе Лжецово, если считать, что оба утверждения осведомителя оказались истинными?
5. Сколько хитрецов живёт в деревне Хитрецово, если считать, что оба утверждения осведомителя оказались ложными?
Задание 5. Азбука Морзе v2
Ваня недавно открыл для себя азбуку Морзе, где каждую букву можно представить в виде двух сигналов длинного (тире) и короткого (точка). Но его беспокоит, что без использования разделителя между отдельными буквами одно и то же сообщение можно расшифровать несколькими способами, поэтому Ваня начал размышлять, как можно усовершенствовать данную систему кодировки букв.
Ваня узнал, что для однозначной расшифровки сообщения нужно, чтобы ни одна последовательность точек и тире для одной буквы не была началом другой последовательности для другой буквы. Вооружившись этой идеей и подсчитав, сколько раз каждый символ встречается в тексте, Ваня задумался: как придумать такие кодовые слова для символов, чтобы закодировать текст с минимальным количеством точек и тире?
В таблице показано, сколько букв в тексте насчитал Ваня.
Помогите ему придумать для каждой буквы такую последовательность точек и тире, чтобы их суммарное количество, необходимое для кодирования текста, было минимальным. Обратите внимание: Ваня хочет, чтобы в дальнейшем данный текст можно было однозначно расшифровать.
Задания 7-8 класс
Задание 1. Стена
При возведении стены крайне важно заказать ровно нужное количество кирпичей. Это количество можно вычислить. Разработайте формулу для расчёта необходимого количества целых кирпичей для стены длиной L метров и высотой H метров (L, H натуральные числа), принимая, что длина одного кирпича составляет 25 сантиметров, а высота 5 сантиметров. При укладке кирпичей в несколько рядов каждый следующий ряд смещается на половину кирпича (см. рисунок). Половинки кирпичей учитывать не нужно, так как их на складе и так очень много. Толщиной раствора между кирпичами можно пренебречь.
Ответом на эту задачу является некоторое выражение (формула), которое может содержать целые числа, переменные L и H (обозначаются заглавными английскими буквами), операции сложения (обозначаются «+»), вычитания (обозначаются «−»), умножения (обозначаются «*»), деления (обозначаются «/») и круглые скобки. Запись вида 2H для обозначения произведения числа 2 и переменной H некорректна, нужно писать 2 * H.
Ваше выражение должно давать правильный ответ для любых натуральных значений L и H. Например, для приведённых на рисунке L=1 и H=1 значение выражения должно быть равно 70. Пример правильной формы записи ответа: H * L−2 * (L−1) +4
Задание 2. Правда или ложь
Рядом с Кудыкиной горой есть три села: Правдино, Лжецово и Хитрецово. Достоверно известно, что в селе Правдино живут только правдолюбы, в селе Лжецово лжецы, а в селе Хитрецово хитрецы, которые не хотят, чтобы их обложили налогами, поэтому всегда лгут о своём местоположении, а обо всём остальном могут говорить и правду, и ложь.
Переписчик Иванов пошёл на хитрость: он опросил всех жителей, задавая каждому лишь три вопроса:
1. Ты из села Правдино?
2. Ты из села Лжецово?
3. Ты из села Хитрецово?
На первый вопрос он получил 360 ответов «Да», на второй вопрос и третий вопросы вместе 480 ответов «Нет». Количество ответов «Да» и «Нет» он записывал в журнал, но, к сожалению, часть записей была утеряна, как и информация об общем числе жителей.
Осведомитель из числа жителей сообщил ему два утверждения
1. В селе Лжецово вдвое больше жителей, чем в селе Хитрецово.
2. В сёлах Лжецово и Хитрецово разное число жителей, причём их количество отличается ровно в 2 раза.
Утверждения осведомителя могут быть либо истинными, либо ложными.
Ответьте на вопросы.
1. Сколько всего жителей живёт во всех трёх сёлах?
2. Сколько всего правдолюбов живёт в селе Правдино?
3. Сколько всего лжецов и хитрецов живёт в сёлах Лжецово и Хитрецово вместе?
4. Сколько лжецов живёт в селе Лжецово, если считать, что оба утверждения осведомителя оказались истинными?
5. Сколько хитрецов живёт в деревне Хитрецово, если считать, что оба утверждения осведомителя оказались ложными?
Задание 3. Азбука Морзе v2
Ваня недавно открыл для себя азбуку Морзе, где каждую букву можно представить в виде двух сигналов длинного (тире) и короткого (точка). Но его беспокоит, что без использования разделителя между отдельными буквами одно и то же сообщение можно расшифровать несколькими способами, поэтому Ваня начал размышлять, как можно усовершенствовать данную систему кодировки букв.
Ваня узнал, что для однозначной расшифровки сообщения нужно, чтобы ни одна последовательность точек и тире для одной буквы не была началом другой последовательности для другой буквы. Вооружившись этой идеей и подсчитав, сколько раз каждый символ встречается в тексте, Ваня задумался: как придумать такие кодовые слова для символов, чтобы закодировать текст с минимальным количеством точек и тире?
В таблице показано, сколько букв в тексте насчитал Ваня.
Помогите ему придумать для каждой буквы такую последовательность точек и тире, чтобы их суммарное количество, необходимое для кодирования текста, было минимальным. Обратите внимание: Ваня хочет, чтобы в дальнейшем данный текст можно было однозначно расшифровать.
Задание 4. Поезда
Ваня очень любит поезда и часто проводит время на железнодорожной станции, наблюдая за их движением. Однажды ему в руки попалось расписание поездов, и он решил разобраться, как устроена работа станции.
Помогите Ване ответить на несколько вопросов.
Для выполнения задания вы можете использовать электронные таблицы из офисного пакета или любые другие средства вашего компьютера. Данные находятся в файле, который вы можете скачать в одном из двух форматов: Microsoft Excel (XLSX) или LibreOffice Calc (ODS).
В этой таблице в столбце с данными B содержится время прибытия поездов, а в столбце с данными C время их отправления. Все данные в этих столбцах заданы в 24-часовом формате ЧЧ:MM, где Ч часы, M минуты. В момент прибытия и отправления поезд считается находящимся на станции. И обратите внимание, что некоторые поезда могут прибывать на станцию до полуночи, а отбывать уже после полуночи на следующий день.
Если вы не знаете ответ на какой‑либо вопрос, запишите вместо него любое число.
1. Сколько минимально путей должно быть на станции, чтобы на них могли находиться все поезда, не мешая друг другу в течение всего дня?
2. В какой период времени на станции находится наибольшее количество поездов одновременно? Ответ запишите в минутах.
3. В течение какого времени за сутки на станции нет ни одного поезда? Ответ запишите в минутах.
4. Ваня хочет выбрать самое интересное время для наблюдений. Сколько поездов будет на станции ровно в 10:00?
Задание 5. Мастер‑класс
Антон Алексеевич, преподаватель математики в старшей школе, решил продемонстрировать практическое применение математических расчётов и провести мастер‑класс по очистке квадратной маркерной доски длины n квадратной губкой длины a.
Антон Алексеевич использует свой фирменный метод, затирая каждый сантиметр доски без лишних движений. Он начинает с верхнего левого угла доски, двигаясь слева направо, затем вниз, влево, вверх, повторяя этот процесс, пока вся доска не будет очищена, но не проходя губкой по тем местам, которые уже очищены (см. рисунок ниже). Губка не вращается во время стирания с доски. Гарантируется, что длина стороны губки делит длину стороны доски без остатка.
Определите длину ломаной линии, которую описывает верхний левый угол квадратной губки при затирании квадратной доски.
Формат входных данных
Первая строка содержит целое число n (1≤n≤109) длину стороны доски.
Вторая строка содержит целое число a (1≤a≤109, a≤n) длину стороны губки. nn делится на a без остатка.
Формат выходных данных
В единственной строке выведите число длину ломаной, которую пройдёт левый верхний угол губки.
Обратите внимание, что ответ в этой задаче может превышать возможное значение 32‑битной целочисленной переменной, поэтому необходимо использовать 64‑битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Система оценки
Решения, правильно работающие при n, a≤103, будут оцениваться в 40 баллов.
Замечание
Проиллюстрируем пример к условию. Жёлтым на схеме обозначена губка, голубым очищенная область, красным маршрут левого верхнего угла губки.
Ввод
6
2
Вывод
16
Задание 6. Наши слоны
На столе лежит шахматная доска, в которой n строк и m столбцов. Слон может ходить по диагонали на любое количество клеток. Пустая клетка находится «под боем», если какой‑либо из слонов на доске может одним ходом перейти на эту клетку. На доске в четырёх углах стоят четыре слона. Сколько клеток находится «под боем»?
Формат входных данных
В первой строке содержится количество строк шахматной доски nn, во второй столбцов mm (2≤n, m≤108).
Формат выходных данных
В единственной строке выведите целое число количество клеток, находящихся «под боем».
Система оценки
Решения, правильно работающие при nn, m≤500, будут оцениваться в 52 балла.
Замечание
Ввод
2
4
2
2
4
7
Вывод
4
0
10
Задание 7. Пирамидки
Ваня хочет построить из кубиков n пирамидок. Он собирает пирамидки следующим образом:
1. Изначально в каждой пирамидке имеется по a1 кубиков в первом ряду.
2. В каждой второй пирамидке, т.е. номер которой делится на 2, к ним добавляется по a2 кубиков во второй ряд.
3. В каждой четвёртой пирамидке, т.е. номер которой делится на 4, добавляется по a3 кубиков в третий ряд.
4. В каждой восьмой пирамидке, т.е. номер которой делится на 8, добавляется по a4 кубиков в четвёртый ряд.
И так далее.
Выразим условие более формально: в каждой пирамидке, номер которой делится на (i−1)-ую степень числа 2, к исходному числу кубиков a1 добавляется по ai кубиков в i ряд. Помогите Ване определить количество кубиков, которое ему нужно для построения всех пирамидок.
Формат входных данных
Первая строка входных данных содержит число nn (1≤n≤109) количество пирамидок, которые хочет построить Ваня.
Вторая строка входных данных содержит число kk (1≤k≤30) количество рядов, для которых известно, сколько в них будет кубиков. Гарантируется, что в каждой пирамидке не более чем k рядов.
Каждая из следующих k строк содержит aiai (1≤ai≤109) количество кубиков в i-м ряде пирамидки. Количество кубиков, требующихся для каждого следующего слоя, не убывает.
Формат выходных данных
В единственной строке выведите число количество кубиков, которые нужны Ване для постройки всех пирамидок.
Обратите внимание, что ответ в этой задаче может превышать возможное значение 32‑битной целочисленной переменной, поэтому необходимо использовать 64‑битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Система оценки
Решения, правильно работающие при n≤15, ai≤100, будут оцениваться в 20 баллов.
Решения, правильно работающие при n≤105, будут оцениваться в 50 баллов.
Замечание
Рассмотрим первый пример. Пирамидки с нечётными номерами 1, 3, 5 имеют по одному ряду и состоят из 1 кубика. Пирамидки с номерами 2, 6 имеют по два ряда и состоят из 1+3 кубиков. Пирамидка с номером 4 имеет 3 ряда и состоит из 1+3+8 кубиков. В сумме Ване потребуется 1+(1+3)+1+(1+3+8)+1+(1+3) = 23 кубика. Пирамидки изображены на рисунке.
Ввод
6
3
1
3
8
Вывод
23
63
Задания 9-11 класс
Задание 1. Мастер‑класс
Антон Алексеевич, преподаватель математики в старшей школе, решил продемонстрировать практическое применение математических расчётов и провести мастер‑класс по очистке квадратной маркерной доски длины n квадратной губкой длины a.
Антон Алексеевич использует свой фирменный метод, затирая каждый сантиметр доски без лишних движений. Он начинает с верхнего левого угла доски, двигаясь слева направо, затем вниз, влево, вверх, повторяя этот процесс, пока вся доска не будет очищена, но не проходя губкой по тем местам, которые уже очищены (см. рисунок ниже). Губка не вращается во время стирания с доски. Гарантируется, что длина стороны губки делит длину стороны доски без остатка.
Определите длину ломаной линии, которую описывает верхний левый угол квадратной губки при затирании квадратной доски.
Формат входных данных
Первая строка содержит целое число n (1≤n≤109) длину стороны доски.
Вторая строка содержит целое число a (1≤a≤109, a≤n) длину стороны губки. nn делится на a без остатка.
Формат выходных данных
В единственной строке выведите число длину ломаной, которую пройдёт левый верхний угол губки.
Обратите внимание, что ответ в этой задаче может превышать возможное значение 32‑битной целочисленной переменной, поэтому необходимо использовать 64‑битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Система оценки
Решения, правильно работающие при n, a≤103, будут оцениваться в 40 баллов.
Замечание
Проиллюстрируем пример к условию. Жёлтым на схеме обозначена губка, голубым очищенная область, красным маршрут левого верхнего угла губки.
Ввод
6
2
Вывод
16
Задание 2. Наши слоны
На столе лежит шахматная доска, в которой n строк и m столбцов. Слон может ходить по диагонали на любое количество клеток. Пустая клетка находится «под боем», если какой‑либо из слонов на доске может одним ходом перейти на эту клетку. На доске в четырёх углах стоят четыре слона. Сколько клеток находится «под боем»?
Формат входных данных
В первой строке содержится количество строк шахматной доски nn, во второй столбцов mm (2≤n, m≤108).
Формат выходных данных
В единственной строке выведите целое число количество клеток, находящихся «под боем».
Система оценки
Решения, правильно работающие при nn, m≤500, будут оцениваться в 52 балла.
Замечание
Ввод
2
4
2
2
4
7
Вывод
4
0
10
Задание 3. Пирамидки
Ваня хочет построить из кубиков n пирамидок. Он собирает пирамидки следующим образом:
1. Изначально в каждой пирамидке имеется по a1 кубиков в первом ряду.
2. В каждой второй пирамидке, т.е. номер которой делится на 2, к ним добавляется по a2 кубиков во второй ряд.
3. В каждой четвёртой пирамидке, т.е. номер которой делится на 4, добавляется по a3 кубиков в третий ряд.
4. В каждой восьмой пирамидке, т.е. номер которой делится на 8, добавляется по a4 кубиков в четвёртый ряд.
И так далее.
Выразим условие более формально: в каждой пирамидке, номер которой делится на (i−1)-ую степень числа 2, к исходному числу кубиков a1 добавляется по ai кубиков в i ряд. Помогите Ване определить количество кубиков, которое ему нужно для построения всех пирамидок.
Формат входных данных
Первая строка входных данных содержит число nn (1≤n≤109) количество пирамидок, которые хочет построить Ваня.
Вторая строка входных данных содержит число kk (1≤k≤30) количество рядов, для которых известно, сколько в них будет кубиков. Гарантируется, что в каждой пирамидке не более чем k рядов.
Каждая из следующих k строк содержит aiai (1≤ai≤109) количество кубиков в i-м ряде пирамидки. Количество кубиков, требующихся для каждого следующего слоя, не убывает.
Формат выходных данных
В единственной строке выведите число количество кубиков, которые нужны Ване для постройки всех пирамидок.
Обратите внимание, что ответ в этой задаче может превышать возможное значение 32‑битной целочисленной переменной, поэтому необходимо использовать 64‑битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Система оценки
Решения, правильно работающие при n≤15, ai≤100, будут оцениваться в 20 баллов.
Решения, правильно работающие при n≤105, будут оцениваться в 50 баллов.
Замечание
Рассмотрим первый пример. Пирамидки с нечётными номерами 1, 3, 5 имеют по одному ряду и состоят из 1 кубика. Пирамидки с номерами 2, 6 имеют по два ряда и состоят из 1+3 кубиков. Пирамидка с номером 4 имеет 3 ряда и состоит из 1+3+8 кубиков. В сумме Ване потребуется 1+(1+3)+1+(1+3+8)+1+(1+3) = 23 кубика. Пирамидки изображены на рисунке.
Ввод
6
3
1
3
8
Вывод
23
63
Задание 4. Тайна магического домино
В далёком королевстве, где магия и реальность переплетаются, существует легенда о бесконечной цепи магических костяшек домино. Эти костяшки выстроены вдоль старинной дороги и обладают особыми свойствами. Каждая костяшка расположена на координате xi и имеет магическую силу, равную hi, определяющую её способность влиять на другие костяшки.
Однажды юная волшебница Оля решила испытать силу этой цепи и толкнула первую костяшку. При падении костяшка выпускает магический импульс, который распространяется вперёд и заставляет падать все костяшки, находящиеся на координатах не больше, чем xi+hi. Каждая следующая костяшка, попавшая под действие импульса, действует аналогично, создавая эффект магической цепной реакции.
Строго говоря, при воздействии на костяшку на позиции xi будут задеты, и как следствие, выпустят уже свой магический импульс, все костяшки с такими координатами xj, что xi+hi≤xj.
К Оле решила присоединиться её подруга Яло. Она решила проверить, как поведут себя костяшки, если их толкнуть с другой стороны. Девочка толкнула последнюю костяшку, которая находилась на самой правой позиции. И вот что произошло.
Самая правая костяшка, которую толкнула Яло, выпустила магический импульс, который распространяется назад, заставляя падать костяшки, находящиеся на координатах не больших чем xi−hi. Иными словами, если костяшка на позиции xi падает, то она сама выпускает магический импульс, под воздействие которого попадают все костяшки, чьи координаты удовлетворяют условию xi−hi>xj.
Таким образом, костяшки, падающие с одной стороны, могут встретиться с костяшками, падающими с другой, при этом магические импульсы с двух сторон продолжат распространяться так же, как и до встречи. Теперь обе цепные реакции Оли и Яло идут навстречу друг другу, и вы очень хотите узнать, сколько же суммарно костяшек упадёт.
Формат входных данных
Первая строка содержит одно целое число N (2≤N≤105) количество волшебных костяшек.
Следующие 2N строк содержат два набора целых чисел:
Первые N строк содержат координаты костяшек xi (0≤xi≤109). Следующие N строк содержат магическую силу костяшек hi (0≤hi≤109). Гарантируется, что координаты образуют возрастающую последовательность (никакие две костяшки не имеют одинаковых координат).
Формат выходных данных
Выведите одно целое число общее число костяшек, которые упадут после удара.
Система оценки
Решения, правильно работающие при n≤1000, будут оценены не менее чем в 50 баллов.
Замечание
В первом примере первая костяшка, которую толкнула Оля, не достанет до следующей (т.к. её «высота» составляет всего 2), а поэтому от импульса слева упадёт только она. Стоящая на координате 8 костяшка, которую толкнула Яло, заденет костяшку, стоящую на координате 7, которая, в свою очередь, не заденет костяшку на координате 5, т.к. её «высота» равна 1. На рисунке ниже показаны костяшки до того, как их толкнули, и их итоговое состояние (красным отмечены места, которые «задела» хотя бы одна костяшка).
Ввод
4
1
5
7
8
2
3
1
1
Вывод
3
Задание 5. Покраска забора
Недавно Егор узнал, что средняя зарплата маляра в России составляет более ста тысяч рублей в месяц. Сейчас он получает немного меньше (примерно ноль рублей в месяц), а потому пошёл работать маляром.
В первый же день работы он получил свое первое задание покрасить забор, состоящий из k досок. Опишем этот процесс немного подробнее. Забор можно представить в виде k досок, стоящих в ряд. Слева от забора стоит телега, в которой есть n банок с краской, при этом i-й банки хватит ровно на ai досок.
Изначально Егор стоит слева от забора (прямо перед телегой), при этом в его руке нет банки с краской. Егор пока что не окончил вуз, поэтому набор его навыков ограничен:
Взять банку с краской. Если Егор стоит перед телегой, то он может взять в руку любую банку, в которой ещё осталась краска. Если у Егора уже была какая‑то банка в руке, то он возьмёт новую, а старую оставит у телеги. Это действие не занимает времени.
Сдвинуться вправо. После этого Егор перейдёт к следующей доске. Если Егор стоял у телеги, то после этого перемещения он будет стоять перед первой доской. При этом Егор не может сдвинуться вправо, если он уже у находится у последней доски. Это действие занимает 1 секунду.
Сдвинуться влево. После этого Егор перейдёт к предыдущей доске. Если Егор стоит у первой доски, то после этого перемещения он будет стоять перед телегой. Конечно же, Егор не может сдвинуться влево, если он стоит перед телегой. Это действие занимает 1 секунду.
Покрасить доску. Если Егор сейчас стоит перед непокрашенной доской и у него в руках есть банка с краской, то он может покрасить эту доску. Это действие занимает 1 секунду.
Раньше Егор был пасечником, а потому ему не понаслышке известна фраза «Время —— деньги!». Соответственно, он хочет как можно быстрее покрасить весь забор. Вы ведь помните, что Егор не окончил вуз? Именно поэтому вам придётся посчитать, какое минимальное время потребуется на покраску всего забора. Обратите внимание на то, что Егор имеет право закончить покраску в любом месте забора и что ему не надо после этого возвращаться к телеге.
Формат входных данных
В первой строке дано целое число k (1≤k≤109) количество досок в заборе.
Во второй строке дано целое число n (1≤n≤2⋅105) количество банок в телеге.
В следующих nn строках даны целые числа ai (1≤ai≤109) число досок, которые можно покрасить краской из банки с номером i.
Формат выходных данных
Выведите минимальное количество секунд, которое потребуется Егору для покраски всего забора. Если Егору не хватит краски для выполнения его задания, то выведите «−1» (без кавычек).
Замечание
Рассмотрим первый пример. В заборе всего пять досок. Чтобы покрасить его как можно быстрее, Егору нужно сначала взять третью банку, потом покрасить первые две доски на это у него уйдёт 4 секунды. Затем он должен вернуться назад и взять банку, которой хватит на три доски, на это ещё 2 секунды. Затем надо докрасить забор на это он потратит ещё 8 секунд, первые две из которых будет идти рядом с уже покрашенными досками. Итого потребуется 4+2+8=14 секунд.
Во втором примере у Егора есть возможность покрасить только одну доску, но этого не хватит на покраску всего забора.
Ввод
5
3
1
3
2
Вывод
14
Ввод
100
1
1
Вывод
-1
Ввод
6
3
5
5
5
Вывод
14