пригласительный этап 2023 2024 всош задания и ответы

25-26 мая 2023 Информатика пригласительный этап 2023 Сириус ВСОШ ответы и задания

Автор

Ответы и решения для заданий олимпиады по информатике для 4, 5, 6, 7, 8, 9 и 10 класса пригласительного школьного этапа 2023-2024 всероссийской олимпиады школьников ВСОШ, которая прошла 25-26 мая 2023 года на платформе сайта «Сириус олимпиада».

Пригласительный этап 2023 олимпиада по информатике 4-5 класс Сириус

1. Три подружки — Настя, Ксюша и Тая — отправились в магазин за подарками на 23 февраля для Артёма, Влада и Лёши. Они выбрали три разных подарка: наушники, книгу и рюкзак. Известно, что: 1. Тая и Настя не заходили в книжный магазин;2. Ксюша сказала, что Тая покупала подарок для Влада и что это не рюкзак;3. Лучший подарок для Лёши — книга.

Определите кто какие подарки и кому купил.

Ответ на эту задачу запишите в три поле ввода ответа. В первое поле ввода запишите, кому и какой подарок купила Настя, во второе поле ввода — кому и какой подарок купила Ксюша, в третье поле ввода — кому и какой подарок купила Тая.

В каждом поле ввода должно быть ровно две буквы. Сначала укажите первую букву имени мальчика («А», «В» или «Л»), потом — первую букву названия подарка («Н», «К» или «Р»). Например, запись «АН» обозначает, что Андрею подарили наушники. Кавычки, запятые, пробелы и прочие символы в ответе писать не нужно. Порядок записи частей ответа должен соответствовать тому, какая девочка какой подарок купила (сначала — Настя, потом — Ксюша, затем — Тая).

2. Вам нужно найти четырёхзначное число, в котором попарные разности всех цифр различны. Среди таких чисел необходимо выбрать минимальное.Например, число 1239 не удовлетворяет условию, так как разность между цифрами 1 и 2 равна 1, и разность между цифрами 2 и 3 тоже равна 1, то есть существуют две пары цифр с одинаковой разностью.Также условию не удовлетворяет число 1111, так как в нём можно выбрать пары цифр на первой и второй или на первой и третьей позициях и получить одинаковую разность между этими парами (она будет равна 0, т.к. все цифры числа равны).

3. Оксана прибавляет к числу его последнюю цифру и вычитает первую. Назовём такое действие операцией. К полученному числу она снова прибавляет его последнюю цифру и вычитает первую, затем прибавляет к результату его последнюю цифру и вычитает первую и т.д. Оксана начала с числа 12 и после первой операции получила число 13 (12 + 2 — 1), потом 15 (13 + 3 — 1), 19, 27 и так далее.Ответьте на следующие вопросы. Во всех случаях выполнение операций начинается с числа 12.1. Какое число получится после 8 операций?2. Какое наибольшее число можно получить, если количество операций не ограничено?3. Какое число получится после 1024 операций?4. Сколько раз за время 1024 операций встретится круглое число (оканчивающееся на 0)?

Ответы на вопросы запишите в поля ввода точно в таком же порядке.

4. Учитель информатики предложил Ивану задание: на клетчатом листе бумаги размером 8 × 8 нарисовать самого длинного «питона». «Питоном» называется цепочка из закрашенных клеток, в которой все клетки (кроме первой и последней) граничат по стороне ровно с двумя закрашенными клетками, а первая и последняя клетка в цепочке соседствуют только с одной закрашенной клеткой. Помогите Ивану выполнить это задание. 

Ответ на эту задачу нужно записать в виде 8 строк, в каждой строке должно быть ровно 8 символов «0» или «1». Символ «0» обозначает свободную клетку, а символ «1» обозначает клетку, занятую питоном. Кавычки, пробелы, запятые, иные символы в ответе указывать не нужно.

Чем длиннее получится питон, который удовлетворяет условию задачи, тем больше баллов вы заработаете.

5. Залина и Алан не могут ни секунды прожить без разговоров и не хотят прерывать звонок, даже пока идут навстречу друг другу. Их путь проходит через холмистую местность, но мобильная связь в этом районе работает только тогда, когда оба собеседника находятся на одинаковой высоте. Помогите Залине и Алану встретиться, не прерывая звонок.

Путь между Залиной и Аланом имеет форму ломаной (по оси абсцисс отложена горизонтальная координата, ось ординат отражает высоту местности в данной точке):

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

Каждое перемещение записывайте в отдельную строку в поле ввода, используя ровно два символа. Первый символ — ход Залины, второй — ход Алана. Символ «<» (знак «меньше») означает движение налево, символ «>» (знак «больше») — движение направо, символ «=» (знак равенства) — отсутствие движения персонажа на данном ходе. Одна строка в поле ответа соответствует одному перемещению Зарины и Алана. Собеседники не могут выходить за пределы заданной ломаной.

Например, следующий ответ:><=>означает, что на первом ходе Залина движется направо, Алан — налево. На втором ходе Залина стоит на месте, а Алан движется направо. Этот ответ не может быть началом правильного решения, потому что на втором ходе Залина и Алан окажутся на разной высоте.

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

Пригласительный этап 2023 олимпиада по информатике 6-7 класс Сириус

1.Оксана прибавляет к числу его последнюю цифру и вычитает первую. Назовём такое действие операцией. К полученному числу она снова прибавляет его последнюю цифру и вычитает первую, затем прибавляет к результату его последнюю цифру и вычитает первую и т.д. Оксана начала с числа 12 и после первой операции получила число 13 (12 + 2 — 1), потом 15 (13 + 3 — 1), 19, 27 и так далее.Ответьте на следующие вопросы. Во всех случаях выполнение операций начинается с числа 12.1. Какое число получится после 8 операций?2. Какое наибольшее число можно получить, если количество операций не ограничено?3. Какое число получится после 1024 операций?4. Сколько раз за время 1024 операций встретится круглое число (оканчивающееся на 0)?

Ответы на вопросы запишите в поля ввода точно в таком же порядке.

2. Молодой предприниматель Тимофей организовал производство и реализацию такой нужной для любого домашнего гардероба продукции, как вешалка для брюк. Поскольку конкуренция на этом рынке велика, Тимофей решил проявить клиентоориентированность и предложил потенциальным покупателям самим выбирать наиболее подходящие для использования размеры этого предмета. Неизменным остаётся только одно – расстояния между горизонтальными перекладинами и размеры крючка всегда равны 1.

По выбранным клиентом ширине w и количеству горизонтальных перекладин h (на рисунке выделены красным цветом) вешалки определите длину проволоки, необходимой для производства одного изделия. Обратите внимание на то, что ширина самой верхней перекладины на 1 меньше остальных.Ответом на эту задачу является некоторое выражение, которое может содержать целые числа, переменные w и h (обозначаются английскими буквами), операции сложения (обозначаются +), вычитания (обозначаются -), умножения (обозначаются *) и круглые скобки. Запись вида 2h для обозначения произведения числа 2 и переменной h некорректна, нужно писать 2 ∗h. Ваше выражение должно давать правильный ответ для любых натуральных значений w > 2 и h > 1. Например, для приведённых на первом рисунке w = 7 и w = 2 значение выражения должно быть равно 25, а для приведённых на втором рисунке w = 7 и h = 2 значение выражения должно быть равно 33.Пример правильной формы записи ответа:w * w — 2 * (h — 1)

3. Залина и Алан не могут ни секунды прожить без разговоров и не хотят прерывать звонок, даже пока идут навстречу друг другу. Их путь проходит через холмистую местность, но мобильная связь в этом районе работает только тогда, когда оба собеседника находятся на одинаковой высоте. Помогите Залине и Алану встретиться, не прерывая звонок.

Путь между Залиной и Аланом имеет форму ломаной (по оси абсцисс отложена горизонтальная координата, ось ординат отражает высоту местности в данной точке):

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

Каждое перемещение записывайте в отдельную строку в поле ввода, используя ровно два символа. Первый символ — ход Залины, второй — ход Алана. Символ «<» (знак «меньше») означает движение налево, символ «>» (знак «больше») — движение направо, символ «=» (знак равенства) — отсутствие движения персонажа на данном ходе. Одна строка в поле ответа соответствует одному перемещению Зарины и Алана. Собеседники не могут выходить за пределы заданной ломаной.Например, следующий ответ:><=>означает, что на первом ходе Залина движется направо, Алан — налево. На втором ходе Залина стоит на месте, а Алан движется направо. Этот ответ не может быть началом правильного решения, потому что на втором ходе Залина и Алан окажутся на разной высоте.

4. На олимпиаду по информатике в другой город едут 100 школьников, для которых нужно приобрести билеты на поезд. Все школьники должны приехать одним поездом, при этом олимпиада начинается 20 апреля. Поэтому из всех подходящих поездов нужно выбрать тот, который приезжает как можно позже, но не позднее 20-го апреля. Если таких поездов несколько, то требуется выбрать тот поезд, на который получится приобрести 100 билетов по минимальной суммарной стоимости.

Для решения этой задачи вам понадобится файл с электронной таблицей, содержащей сведения о поездах и имеющихся в продаже билетах. Скачать файл в формате Microsoft Excel(xlsx), скачать файл в формате Open Document Spreadsheet (ods).

В столбце A содержится номер поезда. В столбце B записана дата прибытия поезда, число n в этом столбце обозначает, что поезд прибывает n-го апреля. Все поезда прибывают приблизительно в одно и то же время, поэтому имеет значение только дата прибытия, но не точное время. Количество билетов на поезд указано в столбце C, а их цена — в столбце D. Одному поезду в этой таблице может соответствовать несколько строк, поскольку в одном поезде могут быть билеты разной стоимости. В таком случае значения в столбцах А и В этих строк будут совпадать.

Вам нужно выбрать поезд так, чтобы в нём было хотя бы 100 свободных мест (возможно, по разным ценам), и он прибывает не позднее 20 числа. Среди таких поездов нужно выбрать тот, который прибывает как можно позже. Если несколько подходящих поездов прибывают в один день, то среди них необходимо выбрать поезд, 100 билетов на который обойдутся дешевле  остальных. Гарантируется, что после этого ответ будет однозначным.

В ответе укажите три числа. Первое число должно быть равно дате прибытия выбранного поезда. Второе число должно быть равно номеру выбранного поезда. Третье число — минимальная стоимость 100 билетов на данный поезд.

5. Женя готовится к городским спортивным соревнованиям, где хочет показать себя самым сильным.

Он тренируется по системе шаолиньских монахов. Тренировка должна состоять из N подходов, каждый из которых длится M минут и S секунд, между каждой парой подряд идущих подходов должен быть перерыв длительностью P секунд.

Помогите Жене определить, сколько всего времени займёт тренировка.

Формат входных данныхПервая строка содержит целое число N (1 ≤ N ≤ 100) — количество подходов.

Вторая строка содержит целое число M (0 ≤ M ≤ 59) — количество минут в одном подходе.

Третья строка содержит целое число S (0 ≤ S ≤ 59) — количество секунд в одном подходе.

Четвёртая строка содержит целое число P (0 ≤ P ≤ 120) — длительность паузы между подходами, выраженная в секундах.

Гарантируется, что один подход занимает ненулевое время. Формат выходных данных Выведите два целых числа — продолжительность тренировки в минутах и секундах. Первое число должно быть равно количеству полных минут в тренировке. Второе число — количеству секунд в тренировке, находящемуся в диапазоне от 0 до 59 включительно. Пример

стандартный ввод стандартный вывод
432470 176

Замечание В примере из условия Жене нужно выполнить 4 подхода, каждый из которых имеет длительность 3 минуты 24 секунды. При этом между походами у него будет 3 перерыва, каждый из которых имеет длительность 70 секунд. Следовательно, вся тренировка займёт 17 минут и 6 секунд.

Ограничения:  Время выполнения: < 1000 ms  Выделяемая память 256 mb

6. Родители Лизы подключили пакет, содержащий N телевизионных каналов, пронумерованных числами от 1 до N.

Переключать каналы можно с помощью двух кнопок на пульте: «+» и «–».

Короткое нажатие на кнопку «+» приведёт к переключению на следующий канал, если номер текущего канала меньше N; если же номер текущего канала равен N, то телевизор продолжит показывать этот канал. Если кнопку «+» нажать и удерживать некоторое время, произойдёт переход на K каналов вперёд, при условии, что номер текущего канала не превосходит N – K. В противном случае произойдёт переход на канал N.

Аналогично, короткое нажатие на кнопку «–» приведёт к переключению на предыдущий канал, если номер текущего канала больше 1; если же номер текущего канала равен 1, телевизор продолжит показывать этот канал. Если кнопку «–» нажать и удерживать некоторое время, то произойдёт переход на K каналов назад при условии, что номер текущего канала превышает K. В противном случае произойдёт переход на канал 1.

Лиза включила телевизор и обнаружила, что он показывает канал P. Лиза знает, что очень скоро по каналу с номером U начнётся интересная передача. Определите, какое минимальное количество нажатий на кнопки пульта потребуется сделать Лизе, чтобы переключиться на канал U.

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

В первой строке содержится целое число N (3 ≤ N ≤ 109) — количество телевизионных каналов.

Во второй строке содержится целое число K (2 ≤ K < N) — количество каналов, на которое осуществится переход назад или вперёд при удерживании соответствующей кнопки переключения.

В третьей строке содержится целое число P (1 ≤ P ≤ N) — номер канала, который показывает телевизор.

В четвёртой строке содержится целое число U (1 ≤ U ≤ N) — номер канала, на который желает переключиться Лиза.

Гарантируется, что P ≠ U.

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

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

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

Решения, правильно работающие при P < U, N ≤ 100, будут оцениваться в 24 балла.

Решения, правильно работающие при N ≤ 100, будут оцениваться в 48 баллов.

Примеры

стандартный ввод стандартный вывод
205319 4
205317 4
2051412 2
205316 4

Замечание

В первом примере Лизе следует сначала выполнить одно короткое нажатие на кнопку «+» и переключиться с канала 3 на канал 4, а затем трижды осуществить переход вперёд на 5 каналов: сначала переключиться с 4 на 9, затем с 9 на 14 и, наконец, с 14 на 19 канал.

Во втором примере Лиза может сначала переключиться коротким нажатием на кнопку «–» на канал 2, после чего выполнить три перехода вперёд на 5 каналов: с канала 2 на канал 7, затем на канал 12 и, наконец, на канал 17.

В третьем примере Лиза дважды выполнит короткое нажатие кнопки «–».

В четвёртом примере Лизе нужно сначала перейти назад, на канал 1, после чего трижды выполнить переход вперёд, последовательно на каналы 6, 11, 16.

Условия выполнения

Правила автоматической проверки

Ограничения:  Время выполнения: < 500 ms  Выделяемая память 256 mb

7. На столе у большого начальника лежит стопка из N заявлений, пронумерованных сверху вниз от 1 до N.Первое заявление он подписывает и убирает из стопки, второе – выбрасывает в мусорную корзину, третье – кладёт вниз стопки. Далее процесс продолжается аналогично, пока заявления в стопке не закончатся.Определите, будет ли заявление с номером K подписано или выброшено, а также номер шага, на котором это произойдёт. Одним шагом является каждая из трёх операций, описанных выше.

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

Первая строка входных данных содержит целое число N, вторая строка – целое число K(1 ≤ N ≤ 109, 1 ≤ K ≤ N).

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

В первой строке выведите «Yes», если заявление с номером K будет подписано, и «No», если оно будет выброшено.

Во второй строке выведите номер шага, на котором это произойдёт.

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

Решения, правильно работающие при N ≤ 1000, будут оцениваться в 40 баллов.

Решения, правильно работающие при N ≤ 5 · 105, будут оцениваться в 60 баллов.

Примеры

стандартный ввод стандартный вывод
4 3 No5
53 Yes7

Замечание

В первом примере из условия в стопке находятся 4 заявления: (1, 2, 3, 4). Заявление 1 подписывается, заявление 2 выкидывается, заявление 3 перекладывается в конец. После выполнения трёх шагов в стопке будут заявления (4, 3). Поэтому на пятом шаге заявление 3 будет выброшено.Во втором примере из условия стопка имеет вид (1, 2, 3, 4, 5). После выполнения трёх шагов стопка будет иметь вид (4, 5, 3). За следующие три шага заявление 4 будет подписано, заявление 5 будет выброшено, а заявление 3 – переложено в конец стопки (в которой ничего не будет, кроме заявления 3). Поэтому после шести шагов стопка будет иметь вид (3). На седьмом шаге заявление 3 будет подписано.

Условия выполнения

Правила автоматической проверки

Ограничения:  Время выполнения: < 1000 ms  Выделяемая память 256 mb

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

Пригласительный этап 2023 олимпиада по информатике 8-10 класс Сириус

1.Женя готовится к городским спортивным соревнованиям, где хочет показать себя самым сильным. Он тренируется по системе шаолиньских монахов. Тренировка должна состоять из N подходов, каждый из которых длится M минут и S секунд, между каждой парой подряд идущих подходов должен быть перерыв длительностью P секунд.

Помогите Жене определить, сколько всего времени займёт тренировка.

Формат входных данных Первая строка содержит целое число N (1 ≤ N ≤ 100) — количество подходов.

Вторая строка содержит целое число M (0 ≤ M ≤ 59) — количество минут в одном подходе.

Третья строка содержит целое число S (0 ≤ S ≤ 59) — количество секунд в одном подходе.

Четвёртая строка содержит целое число P (0 ≤ P ≤ 120) — длительность паузы между подходами, выраженная в секундах.

Гарантируется, что один подход занимает ненулевое время.Формат выходных данных Выведите два целых числа — продолжительность тренировки в минутах и секундах. Первое число должно быть равно количеству полных минут в тренировке. Второе число — количеству секунд в тренировке, находящемуся в диапазоне от 0 до 59 включительно. Пример

стандартный ввод стандартный вывод
432470 176

Замечание В примере из условия Жене нужно выполнить 4 подхода, каждый из которых имеет длительность 3 минуты 24 секунды. При этом между походами у него будет 3 перерыва, каждый из которых имеет длительность 70 секунд. Следовательно, вся тренировка займёт 17 минут и 6 секунд.

Условия выполнения

Правила автоматической проверки

Ограничения:  Время выполнения: < 1000 ms  Выделяемая память 256 mb

2.Родители Лизы подключили пакет, содержащий N телевизионных каналов, пронумерованных числами от 1 до N.

Переключать каналы можно с помощью двух кнопок на пульте: «+» и «–».

Короткое нажатие на кнопку «+» приведёт к переключению на следующий канал, если номер текущего канала меньше N; если же номер текущего канала равен N, то телевизор продолжит показывать этот канал. Если кнопку «+» нажать и удерживать некоторое время, произойдёт переход на K каналов вперёд, при условии, что номер текущего канала не превосходит N – K. В противном случае произойдёт переход на канал N.

Аналогично, короткое нажатие на кнопку «–» приведёт к переключению на предыдущий канал, если номер текущего канала больше 1; если же номер текущего канала равен 1, телевизор продолжит показывать этот канал. Если кнопку «–» нажать и удерживать некоторое время, то произойдёт переход на K каналов назад при условии, что номер текущего канала превышает K. В противном случае произойдёт переход на канал 1.

Лиза включила телевизор и обнаружила, что он показывает канал P. Лиза знает, что очень скоро по каналу с номером U начнётся интересная передача. Определите, какое минимальное количество нажатий на кнопки пульта потребуется сделать Лизе, чтобы переключиться на канал U.

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

В первой строке содержится целое число N (3 ≤ N ≤ 109) — количество телевизионных каналов.

Во второй строке содержится целое число K (2 ≤ K < N) — количество каналов, на которое осуществится переход назад или вперёд при удерживании соответствующей кнопки переключения.

В третьей строке содержится целое число P (1 ≤ P ≤ N) — номер канала, который показывает телевизор.

В четвёртой строке содержится целое число U (1 ≤ U ≤ N) — номер канала, на который желает переключиться Лиза.

Гарантируется, что P ≠ U.

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

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

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

Решения, правильно работающие при P < U, N ≤ 100, будут оцениваться в 24 балла.

Решения, правильно работающие при N ≤ 100, будут оцениваться в 48 баллов.

Примеры

стандартный ввод стандартный вывод
205319 4
205317 4
2051412 2
205316 4

Замечание

В первом примере Лизе следует сначала выполнить одно короткое нажатие на кнопку «+» и переключиться с канала 3 на канал 4, а затем трижды осуществить переход вперёд на 5 каналов: сначала переключиться с 4 на 9, затем с 9 на 14 и, наконец, с 14 на 19 канал.

Во втором примере Лиза может сначала переключиться коротким нажатием на кнопку «–» на канал 2, после чего выполнить три перехода вперёд на 5 каналов: с канала 2 на канал 7, затем на канал 12 и, наконец, на канал 17.

В третьем примере Лиза дважды выполнит короткое нажатие кнопки «–».

В четвёртом примере Лизе нужно сначала перейти назад, на канал 1, после чего трижды выполнить переход вперёд, последовательно на каналы 6, 11, 16.

Условия выполнения

Правила автоматической проверки

Ограничения:  Время выполнения: < 500 ms  Выделяемая память 256 mb

3. Тимофею на день рождения родители подарили металлоискатель. Естественно, наутро мальчик отправился на поиски клада. Он предположил, что когда-то давно кто-то мог обронить золотую монету на древней прямой дороге и для облегчения поиска придумал систему координат. Ось абсцисс OX направлена вдоль дороги, а ось ординат OY направлена вверх.

Устройство работает следующим образом: на его индикаторе выставляется натуральное число r и если ровно на этом расстоянии имеется золотой предмет, то загорается зелёная лампочка. Сначала юный кладоискатель выставил число r1 в точке x = 0, затем отошёл в точку с абсциссой x = a и выставил число r2, как показано на рисунке. Новичкам везёт, оба раза загорелась зелёная лампочка. Определите координаты потерянной когда-то давно золотой монетки.

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

Программа получает на вход три целых числа a, r1 и r2, записанных в отдельных строках (1 ≤ a; r1; r2 ≤ 109).

Формат выходных данных Выведите в двух строках два числа – координаты сокровища (сначала – абсциссу, потом – ординату). Значение ординаты должно быть не положительным (монетка не может висеть в воздухе). Гарантируется, что входные данные таковы, что ответ существует и обе координаты монеты будут целыми числами.

Система оценки Решения, правильно работающие при 1 ≤ a; r1; r2 ≤ 100, будут оцениваться в 40 баллов. Решения, правильно работающие при 1 ≤ a; r1; r2 ≤ 105, будут оцениваться в 60 баллов.

Пример

стандартный ввод стандартный вывод
211017 6-8

Замечание Рисунок соответствует примеру из условия.

Условия выполнения

Правила автоматической проверки

Ограничения:  Время выполнения: < 1000 ms  Выделяемая память 256 mb

4. На столе у большого начальника лежит стопка из N заявлений, пронумерованных сверху вниз от 1 до N. Первое заявление он подписывает и убирает из стопки, второе – выбрасывает в мусорную корзину, третье – кладёт вниз стопки. Далее процесс продолжается аналогично, пока заявления в стопке не закончатся.Определите, будет ли заявление с номером K подписано или выброшено, а также номер шага, на котором это произойдёт. Одним шагом является каждая из трёх операций, описанных выше.

Формат входных данных Первая строка входных данных содержит целое число N, вторая строка – целое число K(1 ≤ N ≤ 109, 1 ≤ K ≤ N).

Формат выходных данных В первой строке выведите «Yes», если заявление с номером K будет подписано, и «No», если оно будет выброшено. Во второй строке выведите номер шага, на котором это произойдёт.

Система оценки Решения, правильно работающие при N ≤ 1000, будут оцениваться в 40 баллов. Решения, правильно работающие при N ≤ 5 · 105, будут оцениваться в 60 баллов.

Примеры

стандартный ввод стандартный вывод
43 No5
53 Yes7

Замечание В первом примере из условия в стопке находятся 4 заявления: (1, 2, 3, 4). Заявление 1 подписывается, заявление 2 выкидывается, заявление 3 перекладывается в конец. После выполнения трёх шагов в стопке будут заявления (4, 3). Поэтому на пятом шаге заявление 3 будет выброшено.Во втором примере из условия стопка имеет вид (1, 2, 3, 4, 5). После выполнения трёх шагов стопка будет иметь вид (4, 5, 3). За следующие три шага заявление 4 будет подписано, заявление 5 будет выброшено, а заявление 3 – переложено в конец стопки (в которой ничего не будет, кроме заявления 3). Поэтому после шести шагов стопка будет иметь вид (3). На седьмом шаге заявление 3 будет подписано.

Условия выполненияПравила автоматической проверки

Ограничения:  Время выполнения: < 1000 ms  Выделяемая память 256 mb

5. Злым числом в математике называется неотрицательное целое число с чётным числом единиц в его двоичной записи (например, число 5 — злое, в его двоичной записи две единицы). Они используются в теории чисел при исследовании последовательности Морса–Туэ и применяются в алгоритмах фрактального сжатия изображений.Натуральное число будем называть очень злым, если само оно чётное и количество единиц в его двоичной записи также чётное. Это такие числа, как 6, 10, 12, 18, 20 и так далее.По данному n определите количество очень злых чисел, не превосходящих n.

Формат входных данных Единственная строка входного файла содержит натуральное число n (1 ≤ n ≤ 109).

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

Система оценки Решения, правильно работающие, когда число n не превосходит 105, будут оцениваться в 30 баллов. Решения, правильно работающие, когда число n является точной степенью числа 2, будут оцениваться в 30 баллов.

Пример

стандартный ввод стандартный вывод
20 5

Условия выполнения Правила автоматической проверки Ограничения:  Время выполнения: < 500 ms  Выделяемая память 256 mb

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

ПОДЕЛИТЬСЯ МАТЕРИАЛОМ