школьный этап 2022 олимпиада сириус

26 октября 2022 ответы и задания для олимпиады по информатике 5-11 класс Сириус

Задания, ответы и решения школьного этапа 2022 всероссийской олимпиады школьников ВСОШ по информатике 5, 6, 7, 8, 9, 10, 11 классов на платформе сайта «Сириус Курсы» пройдет 25-27 октября согласно графику проведения.

Школьный этап 2022 олимпиада по информатике 5 и 6 класс Сириус

1.Дети любят фрукты. В отряде N детей. Вожатому Мише надо раздать детям фрукты на полдник так, чтобы каждый из детей получил хотя бы одно яблоко и хотя бы одну грушу. Ребёнок доволен, если у него больше яблок или груш, чем у каждого другого ребёнка из отряда. Найдите минимальное суммарное количество фруктов, которое Мише необходимо раздать, чтобы все дети остались довольными.

Пример

Допустим, Мише надо раздать фрукты трём детям. Он может дать первому ребёнку 3 яблока и 1 грушу, второму ребенку — 1 яблоко и 3 груши, третьему рёбенку — 2 яблока и 2 груши. У первого ребёнка больше яблок, чем у других детей. У второго больше груш, чем у других детей. У третьего больше яблок, чем у второго, и больше груш, чем у первого. Все дети остались довольны. Всего Мише потребовалось 12 фруктов — это минимальное количество фруктов.

Найдите ответ, если известно, что в классе учится 4 ребёнка (N=4).

2.Числовой шифр

Даня узнал новый способ шифрования слов. Для этого он берёт буквы в слове и выписывает подряд их порядковые номера в латинском алфавите без пробелов и каких‑либо других разделяющих знаков (буква A имеет номер 1, буква B имеет номер 2 и так далее до буквы Z, имеющей номер 26). Результатом этого шифрования является какая-то последовательность цифр. Даня зашифровал какое-то слово и передал получившуюся последовательность цифр своему другу Мише. Тот знает, что при таком шифровании некоторые различные слова могут давать одинаковую последовательность цифр. Миша хочет выяснить, из каких слов могла получиться заданная последовательность цифр. Шифр, получившийся у Дани: 123234345456.

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

Пояснение. Рассмотрим пример. Для шифра «222» подходят три слова: 1. BBB 2. BV 3. VB Для решения задачи вам может потребоваться латинский алфавит с указанием номеров букв.

2 задание 5-6 класс ответ

3.Миша в комнате

Комната Миши имеет форму прямоугольника длиной A и шириной B. На уборку комнаты он выделяет D дней. Наводит чистоту Миша следующим образом: сначала выбирает какое‑то число X, а затем каждый день убирает ровно один квадрат в комнате размером X*X по своему усмотрению. Квадраты могут накладываться друг на друга. Однажды Миша задумался: какое наименьшее число X он может выбрать для того, чтобы убрать всю комнату, потратив на это D дней? 

Пример. Допустим, Мишина комната представляет собой прямоугольник длиной 6 и шириной 6, изображённый на рисунке.

3 задание ответы 5 и 6 класс

Из рисунка видно, что он может убрать комнату за 4 дня. Каждый день он убирает выделенный каким‑либо цветом квадрат размером 3×3. Это минимальный размер квадрата, необходимый для того, чтобы убрать всю комнату в отведённое количество дней. Миша хочет получить ответ для трёх комнат своей квартиры, для каждой из которых известны её размеры и количество дней, выделенное на уборку. Запишите в таблицу целочисленные значения X для этих комнат.

4 задание ответ

4.Компьютерная игра

Миша недавно начал играть в «ducktorio» — в этой игре нужно передвигаться по скалистой местности, используя машину-разрушитель.

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

На первом уровне игры перед разрушителем появились скалы с высотами: 5 9 3 7 5. Определите минимальное количество ударов, которое позволит Мише избавиться хотя бы от 2 скал. 

На втором уровне игры появились скалы с высотами: 5 4 7 4 8 6 3. Определите минимальное количество ударов, которое позволит избавиться хотя бы от 2 скал.

На третьем уровне появились скалы с высотами: 5 6 7 8 8 7 6 5. Определите минимальное количество ударов, которое позволит избавиться хотя бы от 3 скал. 

5.Ледяные кристаллы.

В замке Снежной королевы Кай выращивает льдинки на клетчатом поле, содержащем 100 строк и 100 столбцов. В первый день эксперимента Кай положил маленький кусочек льда высотой 1 в начальную клетку на пересечении первой строки и первого столбца.

На второй день ледяной кристалл начал увеличиваться и прорастать на соседних клетках. Рост кристалла в каждый из дней подчиняется следующим правилам: если в клетке уже есть кристалл, то он увеличивается на высоту, равную количеству соседних клеток с кристаллами; если в клетке ещё не пророс кристалл, то он сразу там появляется.

Высота появившегося кристалла в этой клетке равна количеству соседних по сторонам клеток, в которых находятся кристаллы. Кристаллы очень хрупкие, и могут сломаться под собственным весом. Если в какой-то момент высота кристалла в клетке, расположенной на пересечении строки X и столбца Y, превысит H, то весь кристалл сломается.

Кай внимательно следит за экспериментом и хочет знать номер дня, когда льдинка сломается.

Пример. В первый день Кай поставил кристалл на поле в начальную клетку. Он знает, что кристалл сломается, если в клетке на пересечении третьей строки и третьего столбца высота кристалла превысит 1. Рассмотрим рисунок.

5-6 класс сириус информатика ответ

В первый день у начальной клетки не было «соседок» с кристаллами, поэтому во второй день кристалл в начальной клетке не увеличился по высоте. Зато в клетках, соседних с начальной, появились кристаллы высотой 1. Рост кристалла продолжался в 3, 4 и 5 дни.

В пятый день в клетке ячейке на пересечении третьей строки и третьего столбца появился кристалл высотой 2. Поэтому в этот день весь кристалл сломался. Ответ для примера — 5. Кай провёл серию экспериментов с различными ледяными кристаллами. Укажите ответы для каждого из них.

В первом эксперименте кристалл разрушается, если его высота в ячейке на пересечении первой строки и первого столбца превысит 21.

Во втором эксперименте кристалл разрушается, если его высота в ячейке на пересечении 15-й строки и 1-го столбца превысит 31.

В третьем эксперименте кристалл разрушается, если его высота в ячейке на пересечении 50-й строки и 50-го столбца превысит 10.

ответы для олимпиады

Школьный этап 2022 олимпиада по информатике 7 и 8 класс Сириус

1.Полёт на игру. Баскетбольная команда «Воины золотого штата» вот-вот должна вылететь на игру с командой «Востон Келтикс». Двум игрокам Стефу и Дреймонду достались в самолёте места A и B соответственно. При этом A кратно K — количеству кресел в ряду. Заняв места, они увидели, что сидят друг от друга через проход. Всего в каждую сторону от прохода в ряду K кресел, а общее количество мест кратно 2. Игрокам стало интересно, достаточно ли в самолёте мест для того, чтобы поместилась вся баскетбольная команда. Помогите им в этом, если известно, что согласно правилам нумерации билетов сначала нумеруются все места слева от прохода, а затем справа.

Составьте формулу, помогающую это посчитать. Ответом на данную задачу является строка, в которой записана формула подсчёта количества мест в самолёте. Выражение может содержать целые числа, переменные A, B и K (обозначаются соответствующими английскими буквами), операции сложения (обозначаются +), вычитания (обозначаются -), умножения (обозначаются *), деления (обозначаются /) и круглые скобки. Запись вида 2A для обозначения произведения числа 2 и переменной A некорректна, нужно писать 2 * A. Если вы не знаете формулы, вместо неё следует написать число «0» (без кавычек). Пример правильной формы записи ответа:

Для текущих K, A и B, равных 3,6,16, справедливо следующее расположение мест.

1 задание ответ 7-8 класс

2.Шифровка

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

2 задание ответ 7-8 класс

При остановке колеса на какой-то цифре она записывается в шифр, а выбранные указателями буквы записываются в сообщение. Сначала фиксируется согласная буква, находящаяся на правом колесе, а затем — гласная буква, находящаяся на левом колесе. Если колесо сделало полный оборот, но ни одна пара букв выбрана не была, то в сообщение записывается — (тире). Помогите Стефу и его напарникам дешифровать сообщение, если тренер им передал шифр 4365.

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

Задание 3 Проблемы с двигателями.

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

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

топливо сириус ответ

Пример. Допустим, двигатели потребляют 1,4,5,2,6 и 3 единицы топлива соответственно.

3 задание ответ 7-8 класс

Если мы заглушим двигатели с расходом 5 и 6, то самолёт долетит на остальных двигателях.

3 задание ответ 7-8 класс 2022

Потребление оставшихся двигателей равно 1 4 2 3, что в сумме даёт 10.

Задание 4 Вкусные конфеты

Когда проблема с двигателями была решена, а спортсмены заселились в гостиницу, Стеф предложил своей команде подарить тренеру пакет конфет, чтобы тот не нервничал во время матча. Его друзья захотели, чтобы количество конфет тренер определил сам. Для этого игроки ведущей пятёрки подарили ему несколько карточек с числами, а капитан сообщил волшебное число, изначально равное 0. Для игры тренеру необходимо вытягивать карточки и к каждой из них применять одно из двух действий на выбор:

Увеличить волшебное число на значение, записанное на карточке, Взять столько конфет, сколько составляет произведение числа на карточке и текущего значения волшебного числа. Вытягивать карточки можно в любом порядке, но использовать каждую карточку разрешено только один раз. Какое наибольшее количество конфет сможет получить тренер?

Даны 3 набора карточек и информация о числах на них. Заполните таблицу.

таблица сириус информатика

Пример. Если в какой-то момент волшебное число равно 4, и тренер захочет вытянуть карточку 3, он может либо сделать волшебное число равным 7, либо взять 12 конфет, а волшебное число останется прежним.

Задание 6 Стеф и его команда

Ограничение по времени: 1 секунда. Идёт матч между командами «Воины золотого штата» и «Востон Келтикс». На текущий момент табло показывает время m:s (m — число минут, s — число секунд) и счёт p:q (число очков команд соответственно), атаку совершают «Воины золотого штата». Команда «Воины золотого штата» выбрала следующую стратегию: они тратят на одну атаку ровно 24 секунды; забивают только трёхочковые броски.

В свою очередь, команда «Востон Келтикс» ничего не может противопоставить: совершают только двухочковые броски, забивая только через одну атаку (первая атака команды с момента времени m:s — удачная); также тратят на одну атаку ровно 24 секунды. Учтите, что ни одна из команд не старается перехватить мяч, а это значит, что атаки совершаются по очереди. Длительность матча 48 минут. Предскажите итоговый счёт.

Формат входных данных. В первой и второй строках дано количество минут m (0≤m≤48) и секунд s (0≤s≤59) на табло соответственно. В третьей строке дано количество очков p, набранное командой «Воины золотого штата», в четвёртой — количество очков q, набранное командой «Востон Келтикс» (0≤p,q≤1000).

Формат выходных данных. Выведите итоговый счёт: вначале количество очков, набранное командой «Воины золотого штата», затем — командой «Востон Келтикс». Числа разделите пробелом или переводом строки.

Система оценки Решения, работающие при m=0 и s=0, будут набирать не менее 10 баллов. Решения, работающие в случае, когда до конца матча осталось столько времени, что все начатые атаки будут завершены, будут набирать не менее 50 баллов.

Пояснение. Предположим, что на табло сейчас 46:06, а счёт игры 120:120. Согласно условию задачи, первой атакует команда «Воины золотого штата», забивая трёхочковый бросок и затрачивая на атаку 24 секунды. После этого табло показывает 46:30, а счёт игры становится 123:120.

сириус информатика 2022

Заметим, что во второй атаке «Востон Келтикс» не забивает, и счет сохраняется неизменным. При этом остаётся 18 секунд на атаку команды «Воины золотого штата», но по условию задачи на проведение атаки требуется ровно 24 секунды.

Ввод

Вывод

  • 47
  • 0
  • 120
  • 120
  • 123
  • 122

Задание 7

Гонка за лидерством. Ограничение по времени: 1 секунда. С учётом прошлой победы Стеф набрал за сезон K очков. У его главного конкурента уже набрано L очков. До конца сезона осталось N игр. Определите, сможет ли Стеф стать лучшим бомбардиром сезона, если он будет за каждую игру набирать S очков, а его конкурент в два раза меньше. Для того, чтобы стать лучшим бомбардиром, Стефу достаточно набрать очков не меньше, чем у его главного конкурента.

Формат входных данных. В первой строке входных данных записано число K (0≤K≤3000) — количество очков Стефа на данный момент. Во второй дано число L (0≤L≤3000) — количество очков у главного конкурента Стефа. В третьей строке дано число N (0≤N≤1000) — количество оставшихся игр. В четвёртой строке указано чётное число S (2≤S≤1000) — чётное число очков, постоянно набираемых Стефом за матч.

Формат выходных данных. Если Стеф не сможет стать лучшим, выведите «No». В противном случае выведите «Yes» и далее через пробел или перевод строки минимальное число игр, необходимое для выполнения поставленной цели.

Ввод

Вывод

  • 100
  • 120
  • 5
  • 40
  • Yes
  • 1

Задание 8

Последовательность. Ограничение по времени: 1 секунда.

Подходит к концу игровой сезон, и команды уже изучили стратегии своих соперников. Чтобы запутать соперников, главный тренер команды «Воины золотого штата» придумал интересную схему атак: анализируя будущий матч, он высчитывал число n — количество возможных атак команды, а затем на предматчевой тренировке сообщал команде волшебное число x, неизвестное сопернику.

Пронумеровав все свои атаки от 1 до n, команда выбирала максимальное их количество так, чтобы порядковые номера никаких двух из них не отличались ровно на x, и именно в этих атаках совершали трёхочковые броски. Помогите команде и напишите программу, делающую это максимально быстро, чтобы соперники не успевали просчитать, в каких атаках их кольцу будет угрожать Стеф.

Формат входных данных. В первой строке даётся число n (1≤n≤10000). Во второй строке даётся число x (1≤x≤10000).

Формат выходных данных. Выведите выбранные номера атак, в которых будет совершен трёхочковый бросок. Номера разделяйте пробелами или переводами строк.

Система оценки. Решения, работающие при x=1, будут набирать не менее 10 баллов.

Пояснение. Можно заметить, что из группы чисел 1,2, 3,4,5 возможно взять только три числа, удовлетворяющих условию. Ведь разница всех возможных пар 4−1, 5−1 и 5−4 не равна 2.

Ввод

Вывод

  • 5
  • 2
  • 1
  • 5
ответы для олимпиады

Школьный этап 2022 олимпиада по информатике 9, 10, 11 класс Сириус

1.Лука в кинотеатре. Ограничение по времени: 1 секунда.

Воскресным утром в кинотеатре в двух залах одновременно начался показ фильмов. Фильм, показываемый в первом зале, имеет длительность a минут, а фильм, показываемый во втором зале — b минут. В каждом из залов после окончания фильма его сразу начинают показывать с начала. Любой посетитель может войти в любой из залов. Лука знает, что с момента начала показа фильмов прошло t минут. Ему неважно, какой фильм посмотреть, так как Лука просто хочет весело провести время. Однако мальчик нетерпелив, поэтому хочет узнать, через какое минимальное время хотя бы в одном из залов начнут показывать фильм с начала.

Формат входных данных. Первая строка содержит одно целое число a (1≤a≤2⋅109) — длительность первого фильма в минутах. Вторая строка содержит одно целое число b (1≤b≤2⋅109) — длительность второго фильма в минутах. Третья строка содержит одно целое число t (0≤t≤2⋅1018) — время в минутах, прошедшее с начала показа фильмов. Обратите внимание, что входные данные и ответ могут быть достаточно большими, поэтому следует использовать 64-битный тип данных, например long long в C/C++, long в Java, int64 в Pascal.

Формат выходных данных. Выведите одно целое число — минимальное время в минутах, через которое хотя бы в одном зале начнут показывать фильм с начала.

Система оценки

Решения, правильно работающие только для случаев, когда t не превосходит 2⋅109, будут оцениваться в 60 баллов.

Пояснение

Рассмотрим первый пример из условия. Фильм, показываемый в первом зале, имеет длительность 3 минуты, а фильм, показываемый во втором зале — 7 минут. Таким образом, первый фильм начинается спустя 0,3,6,9,12; минут после начала показа, а второй фильм — спустя 0,7,14,21,28; минут после начала показа. Лука знает, что с начала показа фильмов прошло 10 минут. Для того, чтобы попасть на начало первого фильма, ему придётся подождать 12−10=2 минуты, а чтобы попасть на начало второго фильма — 14−10=4 минуты.

Рассмотрим второй пример из условия. Оба фильма имеют длительность 5 минут и начинаются спустя 0,5,10,15 ; минут после начала показа. Так как с момента начала показа прошло 10 минут, Луке не придётся ждать. Рассмотрим третий пример из условия. Оба фильма начнутся спустя 9 минут после начала показа, поэтому вне зависимости от выбора фильма Луке придётся подождать 9−8=1 минуту.

ввод вывод 9 10 11 класс

2.Лука покупает динозавров. Ограничение по времени: 1 секунда.

На карте «Шестёрочки» у Луки уже есть t бонусных баллов, за которые он может покупать фигурки динозавров. Лука хочет купить всю коллекцию новых динозавров, состоящую из r фигурок. Один динозавр стоит l бонусных баллов.

Баллы в «Шестёрочке» можно получить следующим образом: за покупку первого товара на карту начисляется p1 баллов, за покупку второго товара — p2 баллов, за покупку третьего товара — p3 баллов, за покупку четвёртого товара — снова p1 баллов, за покупку пятого товара — p2 баллов, и так далее. Какое минимальное количество товаров должен купить Лука, чтобы приобрести всю коллекцию динозавров? Обратите внимание на то, что покупка товаров осуществляется не на бонусные баллы, а за настоящие деньги.

Формат входных данных.

  • Первая строка содержит одно целое число t (0≤t≤1018) — изначальное количество баллов на карте.
  • Вторая строка содержит одно целое число r (0≤r≤109) — количество динозавров в коллекции.
  • Третья строка содержит одно целое число l (0≤l≤109) — стоимость одного динозавра.
  • Четвёртая строка содержит одно целое число p1 (0≤p1≤1017) — количество баллов, начисляемых за покупку.
  • Пятая строка содержит одно целое число p2 (0≤p2≤1017) — количество баллов, начисляемых за покупку.
  • Шестая строка содержит одно целое число p3 (0≤p3≤1017) — количество баллов, начисляемых за покупку.

Гарантируется, что p1+p2+p3. Обратите внимание, что входные данные и ответ могут быть достаточно большими, поэтому следует использовать 64-битный тип данных, например, long long в C/C++, long в Java, int64 в Pascal.

Формат выходных данных. Выведите одно число — минимальное количество товаров, которые должен купить Лука, чтобы приобрести всю коллекцию динозавров. Система оценки. Решения, правильно работающие только для случаев, когда t не превосходит 106, l и r не превосходят 103, а p1, p2 и p3 не превосходят 106, будут оцениваться в 35 баллов. Решения, правильно работающие только для случаев, когда Луке потребуется покупать по три товара, будут оцениваться в 25 баллов.

Пояснение

Рассмотрим второй пример. Изначально у Луки есть два бонусных балла, при том что в коллекции два динозавра, каждый из которых стоит по пять баллов. Сначала Лука купит первый товар и получит два балла за первую покупку. Далее Лука купит второй товар, получит один бонусный балл, в сумме пять. Далее он купит третий товар и получит ещё три бонусных балла, в итоге восемь баллов. На покупку всех моделей из коллекции до сих пор не хватает, поэтому Луке придётся сделать ещё одну, четвёртую покупку, после чего он получит два балла (потому что за четвёртую покупку начисляется столько же, сколько и за первую). Теперь у Луки десять баллов, на которых он может купить всю коллекцию динозавров. Значит, ответ — четыре.

3.Лука наблюдает за кузнечиками Ограничение по времени: 1 секунда

Любимое занятие Луки — наблюдать за кузнечиками. Сегодня утром, прогуливаясь по парку, он обнаружил кузнечика, который прыгал по окружности длиной n метров. Лука заметил, что за один прыжок кузнечик может переместиться по часовой стрелке на k или k+1 метров от своей текущей позиции на окружности. Мальчику стало интересно, какое минимальное количество прыжков потребуется кузнечику, чтобы, начав прыгать из некоторой точки окружности, снова оказаться в ней.

Формат входных данных. Первая строка содержит одно целое число n (1≤n≤106) — длина окружности в метрах. Вторая строка содержит одно целое число k (1≤k≤109) — характеристика длины прыжка кузнечика в метрах. Гарантируется, что 1≤n⋅k≤109.

Формат выходных данных. Выведите одно целое число — минимальное количество прыжков, которое придётся сделать кузнечику, чтобы, начав прыгать из некоторой точки окружности, снова оказаться в ней.

Система оценки

Решения, правильно работающие только для случаев, когда n не превосходит 100, будут оцениваться в 60 баллов.

Пояснение.

Рассмотрим первый пример из условия. Один из вариантов действий кузнечика таков: Выполнить прыжок длины 3, Выполнить прыжок длины 4, Выполнить прыжок длины 3. Таким образом, суммарно кузнечик преодолеет 3+4+3=10 метров, то есть вернётся в исходную точку. Во втором примере из условия кузнечику достаточно выполнить пять прыжков длины 2. В третьем примере из условия можно выполнить один прыжок длины 8 и два прыжка длины 7. Таким образом, суммарно кузнечик преодолеет 8+7+7=22 метра, то есть обойдёт окружность дважды и вернётся в исходную точку.

Ввод

Вывод

  • 10
  • 3
  • 3
  • 10
  • 1
  • 5
  • 11
  • 7
  • 3

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

У Луки есть массив из n целых чисел a1, a2, . . . , an. K каждому элементу массива можно произвольное количество раз применять каждую из следующих магических операций: Выбрать некоторый элемент массива ai и заменить его на число [ai2] (данная запись обозначает число ai2, округлённое вниз). Для выполнения данной операции требуется k единиц энергии.

Выбрать некоторый элемент массива ai и заменить его на число ai−1. Для выполнения данной операции требуется одна единица энергии. Ваша задача — определить, какое минимальное количество энергии необходимо, чтобы после выполнения магических операций все элементы массива были равны единице (то есть a1=a2=…;=an=1).

Формат входных данных. Первая строка содержит одно целое число n (1≤n≤5⋅104) — количество элементов массива. Вторая строка содержит одно целое число k (1≤k≤105) — количество энергии, необходимое для выполнения операции первого типа. Каждая из следующих n строк содержит одно целое число ai (1≤ai≤109) — элементы массива. Обратите внимание, что ответ может быть достаточно большим, поэтому следует использовать 64-битный тип данных, например, long long в C/C++, long в Java, int64 в Pascal.

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

Система оценки

Решения, правильно работающие только для случаев, когда k=1, будут оцениваться в 25 баллов. Решения, правильно работающие только для случаев, когда все ai не превосходят 105, будут оцениваться в 50 баллов.

Пояснение. Рассмотрим первый пример из условия.

Первый элемент массива равен 4. Использовав одну единицу энергии, применим к нему первую магическую операцию, после чего первый элемент массива станет равен [42]=2. После этого применим к нему вторую операцию, также затратив одну единицу энергии. Второй элемент массива уже равен 1, поэтому применять к нему операции не нужно. К третьему элементу применим первую операцию, используя одну единицу энергии. После этого третий элемент станет равен [32]=1.

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

Ввод

Вывод

  • 3
  • 1
  • 4
  • 1
  • 3
  • 3
  • 1
  • 100
  • 10
  • 9

5.Лука и локальная сеть динозавров. Ограничение по времени: 1 секунда

Лука смог приобрести всю коллекцию динозавров из «Шестёрочки» и обнаружил, что в динозаврах есть коммутаторы, поэтому ему захотелось объединить их в одну локальную сеть. Он расставил на декартовой плоскости всю коллекцию, то есть местоположение каждого динозавра задана двумя числами — координатами по осям x и y. Лука хочет соединить их проводами так, чтобы между любыми двумя динозаврами существовал путь по этим проводам. Луку раздражают спутанные провода, поэтому никакие два провода не должны пересекаться (пересечения в концах отрезков разрешены). Кроме того, у Луки мало денег на покупку проводов, поэтому общее количество проведённых отрезков не должно превышать 2n.

Формат входных данных. Первая строка содержит одно целое число n (1≤n≤103) — количество динозавров. В следующих 2n строках заданы координаты динозавров. В каждой строке записано одно целое число: первая строка содержит координату по оси x для первого динозавра, вторая строка — координату по оси y для первого динозавра, третья строка — координату по оси x для второго динозавра, и так далее. Таким образом, координата xi для i-го динозавра находится в (2i)-й строке входных данных, координата yi для i-го динозавра находится в (2i+1)-й строке входных данных. Гарантируется, что (−109≤xi,yi≤109), а также никакие два динозавра не находятся в одной точке плоскости.

Формат выходных данных. В первой строке выведите одно число m — количество проведённых проводов, либо число −1, если соединить динозавров описанным в условии способом невозможно. Если существует подходящее под условие соединение, то в следующих m строках выведите по два целых числа — порядковые номера динозавров, соединённых очередным проводом. Если решений несколько, можно вывести любое из них.

Система оценки

Решения, правильно работающие только для случаев, когда n не превосходит 4, будут оцениваться в 25 баллов. Решения, правильно работающие только для случаев, когда никакие три динозавра не лежат на одной прямой, будут оцениваться в 25 баллов.

Решения, правильно работающие только для случаев, когда у всех динозавров координаты по оси x различны, будут оцениваться в 25 баллов.

Пояснение. Иллюстрация ответа для первого примера из условия:

олимпиада сириус
ответы для олимпиады

Добавить комментарий