Официальные задания и ответы пригласительного этапа по Информатике 8-10 класс 2024-2025 всероссийской олимпиады школьников ВСОШ по каждому предмету и для каждого класса.
🦘Задания и ответы Пригласительный этап ВСОШ “Информатика” 2024 для 8-10 класса🦘
Задание 1.
Змейка
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Успешно решив раньше времени контрольную работу по математике, Тимофей выбрал на клетчатой бумаге квадрат со стороной n𝑛 клеток и стал заполнять его «змейкой» от левого верхнего угла так, как показано на рисунке. Определите длину проведённых линий.
Формат входных данных
Единственная строка входных данных содержит натуральное число n𝑛 (1≤n≤109).
Формат выходных данных
Выведите одно натуральное число —— ответ на вопрос задачи.
Обратите внимание, что значение ответа в этой задаче может превышать возможное значение 32‑битной целочисленной переменной, поэтому необходимо использовать 64‑битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Система оценки
Решения, правильно работающие при n≤104, будут оцениваться в 40 баллов.
Ввод
1
5
Вывод
3
35
🔓 Узнать ответ
Задание 2.
Две сестры
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Аполлинария Прокофьевна и Белла Прокофьевна —— две сестры‑пенсионерки. Аполлинарии Прокофьевне каждый день необходимо принимать одну таблетку от забывчивости. К сожалению, этот режим она не соблюдает и вспоминает о лекарстве только раз в a𝑎 дней (то есть приняв лекарство сначала в первый день, в следующий раз она примет его в день номер 1+a). Белле Прокофьевне каждый день необходимо принимать одну таблетку от жадности. Ко всеобщему огорчению, и её болезнь сильнее лекарства, поэтому каждый день она глотает b𝑏 таблеток. Внешне эти таблетки выглядят совершенно одинаково и каждая из сестёр считает, что вот этот пузырёк с n𝑛 пилюлями именно её. На сколько дней им хватит этого количества лекарств?
Формат входных данных
Три строки входных данных содержат три целых числа a𝑎, b (1≤a,b≤100) и n (1≤n≤1018).
Обратите внимание, что значения переменных в этой задаче могут превышать возможные значения 32‑битной целочисленной переменной, поэтому необходимо использовать 64‑битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Формат выходных данных
Программа должна вывести одно число —— ответ на задачу.
Система оценки
Решения, верно работающие при a=1 (Аполлинария принимает лекарство каждый день), будут оцениваться в 20 баллов.
Решения, верно работающие при n≤105, будут оцениваться 40 баллов.
Замечание
В первом примере Аполлинария Прокофьевна принимает по одной таблетке раз в два дня (начиная с первого), Белла Прокофьевна принимает по три таблетки каждый день. В пузырьке 12 таблеток.
В первый день Аполлинария принимает одну таблетку, а Белла —— три. В пузырьке осталось восемь пилюль.
Во второй день Аполлинария забывает принять таблетку, а Белла опять съедает три. В пузырьке осталось пять пилюль.
В третий день Аполлинария принимает одну таблетку, а Белла —— три. В пузырьке осталась последняя пилюля, ещё на один день этого количества сёстрам не хватит.
Во втором примере начального количества таблеток не хватит даже на один день.
Ввод
2
3
12
Вывод
3
Ввод
3
4
2
Вывод
0
🔓 Узнать ответ
Задание 3.
Мастерство фотографии
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Фотографа попросили сделать фотосессию группы детей для выпускного альбома в детском саду. В числе прочих, он должен сделать групповой снимок, на котором должны присутствовать все дети одновременно. Фотограф считает, что для красивой фотографии группы требуется очень тщательно расставить детей в кадре. В частности, с его точки зрения, группа должна расположиться как можно компактнее по ширине, то есть количество людей в самом длинном ряду на фотографии должно быть как можно меньше.
Для гармоничного расположения детей фотограф размещает детей не более чем в четыре ряда. Девочек он располагает либо во втором ряду, сидящими на стульчиках, либо стоящими третьем ряду. Мальчиков он размещает либо в первом ряду, сидящими на корточках, либо в четвёртом ряду, стоящими на стульчиках. Группа состоит из a𝑎 мальчиков и b девочек. В студии есть стулья в количестве c штук. Какие‑то ряды могут быть пустыми. Все стулья использовать не обязательно.
По заданным числам a, b и c требуется определить, какого наименьшего по ширине расположения группы сможет добиться фотограф.
Формат входных данных
Программа получает на вход три целых неотрицательных числа a𝑎, b𝑏 и c𝑐, записанных в отдельных строках —— количество мальчиков, девочек и стульев соответственно. Все числа не превосходят 1018.
Обратите внимание, что значения переменных в этой задаче могут превышать возможные значения 32‑битной целочисленной переменной, поэтому необходимо использовать 64‑битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Формат выходных данных
Вывести одно целое число —— минимальную ширину группы, которую сможет организовать фотограф.
Система оценки
Решения, правильно работающие при 0≤ a, b, c ≤50, будут оцениваться в 20 баллов.
Решения, правильно работающие при 0≤ a, b, 𝑐 ≤1000, будут оцениваться в 30 баллов.
Решения, правильно работающие при 0≤ a, b, c ≤106, будут оцениваться в 50 баллов.
Кроме того, независимо от размера входных данных, решения, правильно работающие для случаев, когда все числа во входных данных чётные, будут оцениваться в 3030 баллов.
Замечание
Во всех примерах в условии группа состоит из 9 мальчиков и 15 девочек.
В первом примере стульев нет, поэтому все девочки стоят, все мальчики сидят на корточках, общая ширина группы 15.
Во втором примере есть 4 стула. Можно посадить 4 девочек во втором ряду на эти стулья, остальные 11 девочек будут стоять в третьем ряду. Все мальчики будут сидеть на корточках в первом ряду. Общая ширина группы 11.
В третьем примере есть 7 стульев. Тогда есть два способа получить группу ширины 9. Например, можно посадить на все стулья девочек, тогда в первом ряду будет 9 мальчиков, во втором ряду будет 7 девочек, в третьем ряду 8 девочек. Либо можно посадить на стулья 6 девочек и поставить одного мальчика в четвёртый ряд. Тогда получим 8 мальчиков в первом ряду, 6 девочек во втором, 9 девочек в третьем и 1 мальчика в четвёртом. В любом из этих двух случаев ширина группы равна 9.
В четвёртом примере стульев много и есть несколько способов организовать группу ширины 8. Один из способов такой: посадим на корточки 4 мальчика в первом ряду, далее посадим 8 девочек на стулья во втором ряду, оставшиеся 7 девочек встанут в третьем и 5 мальчиков поставим на стульчики в четвёртом.
Ввод
9
15
0
Вывод
15
Ввод
9
15
4
Вывод
11
Ввод
9
15
7
Вывод
9
Ввод
9
15
100
Вывод
8
🔓 Узнать ответ
Задание 4.
Места в ряду
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
В зале есть ряд из n𝑛 мест, пронумерованных числами от 1 до n слева направо. Пройти к любому месту можно либо с левого конца ряда, либо с правого. Первоначально некоторые места уже заняты и ещё k человек по одному садятся на свободные места. Каждый человек выбирает себе свободное место, до которого ближе всего идти от одного из концов ряда. Если же есть два свободных места, одинаково удалённых от левого и правого концов ряда, то человек выберет левое место (с меньшим номером).
Определите номера мест, которые будут выбирать люди, в порядке их прихода.
Формат входных данных
Первая строка входных данных содержит целое число n𝑛 (1≤n≤2⋅105) —— количество мест в ряду.
Вторая строка содержит целое число k (1≤k≤n) —— количество приходящих людей.
Третья строка содержит строку s длины n𝑛, состоящую из символов «0» и «1» и задающую первоначальную рассадку. Занятые места обозначаются единицами, пустые —— нулями. Гарантируется, что в строке s содержится не менее k нулей.
Формат выходных данных
Программа должна вывести k чисел —— номера выбранных мест в порядке прихода новых людей.
Система оценки
Решения, правильно работающие при k=1, будут оцениваться в 20 баллов.
Решения, правильно работающие, когда строка s𝑠 состоит только из символов «0», будут оцениваться в 32 балла.
Решения, правильно работающие при 1≤k≤n≤1000, будут оцениваться в 28 баллов.
Замечание
В первом примере первоначально заняты места 1, 2 и 6 (рисунок А).
Если первый пришедший будет двигаться с левой стороны ряда, он пройдёт мимо 1 и 2 места, прежде чем доберётся до свободного места с номером 3. Если же он будет двигаться с правой стороны ряда, то ему понадобится пройти мимо одного места с номером 6, после чего он сможет занять место 5. Именно это место он и выберет (рисунок Б).
Второй пришедший может занять либо место с номером 3, двигаясь с левой стороны и проходя мимо двух занятых мест 1 и 2, либо место с номером 4, двигаясь с правой стороны и проходя мимо двух занятых мест 6 и 5. Поскольку в обоих случаях ему нужно пройти мимо двух занятых мест, он будет двигаться с левой стороны и займёт место с номером 3.
Во втором примере в ряду 6 мест, второе и пятое места изначально уже заняты, заходят ещё 3 человека. Первый заходящий человек будет выбирать между первым и шестым местами, заходя с левого или правого края соответственно. В обоих случаях ему придётся пройти мимо нуля занятых мест, поэтому он решит зайти слева и сесть на 1 место. Второй человек будет выбирать между третьим и шестым местами. В первом случае ему придётся идти мимо двух занятых мест, во втором —— мимо нуля, поэтому он выберет зайти справа —— 6 место. Третий человек будет выбирать между третьим и четвертым местами. В обоих случаях ему придётся пройти мимо двух занятых мест, поэтому он выберет зайти слева —— 3 место.
Ввод
6
2
110001
Вывод
5
3
Ввод
6
3
010010
Вывод
1
6
3
🔓 Узнать ответ
Задание 5.
Гармония
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Совсем недавно Васе на день рождения подарили строку, состоящую только из символов «0» и «1». Обрадованный этим подарком, он тут же начал эту строку изучать —— искать в ней гармоничные части. Для начала Васю интересует только количество различных непустых гармоничных подстрок. А поскольку подарок оказался слишком большим, мальчик решил обратиться за помощью к вам. Помогите Васе!
В понимании Васи, строка является гармоничной, если и символов 0, и символов 1 в ней чётное количество.
Подстрокой строки s называется строка, полученная из s выкидыванием нескольких символов с начала и с конца (возможно, нуля или всех). Так, строка «12» является подстрокой строки «123», а строка «13» —— нет. Подстроки считаются одинаковыми, если у них совпадает количество удалённых символов с начала и с конца.
Формат входных данных
В первой строке дано одно число n𝑛 —— длина подарка (1≤n≤2⋅1051≤𝑛≤2⋅105).
Во второй строке дана строка s𝑠 длины n𝑛 —— Васин подарок. Гарантируется, что s𝑠 состоит только из нулей и единиц.
Формат выходных данных
Выведите единственное число —— количество различных гармоничных подстрок в s.
Обратите внимание, что значение ответа в этой задаче может превышать возможные значения 32‑битной целочисленной переменной, поэтому необходимо использовать 64‑битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Система оценки
Решения, правильно работающие для строк, целиком состоящих из нулей, будут оцениваться в 20 баллов.
Решения, правильно работающие при n≤100, будут оцениваться в 20 баллов.
Решения, правильно работающие при n≤1000, будут оцениваться в 30 баллов.
Замечание
В первом примере из условия подходят следующие подстроки (выделены жирным): 001100, 001100, 001100, 001100, 001100, 001100, 001100.
Ввод
6
001100
Вывод
7
Ввод
1
0
Задание 5.
Гармония
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Совсем недавно Васе на день рождения подарили строку, состоящую только из символов «0» и «1». Обрадованный этим подарком, он тут же начал эту строку изучать —— искать в ней гармоничные части. Для начала Васю интересует только количество различных непустых гармоничных подстрок. А поскольку подарок оказался слишком большим, мальчик решил обратиться за помощью к вам. Помогите Васе!
В понимании Васи, строка является гармоничной, если и символов 0, и символов 1 в ней чётное количество.
Подстрокой строки s называется строка, полученная из s выкидыванием нескольких символов с начала и с конца (возможно, нуля или всех). Так, строка «12» является подстрокой строки «123», а строка «13» —— нет. Подстроки считаются одинаковыми, если у них совпадает количество удалённых символов с начала и с конца.
Формат входных данных
В первой строке дано одно число n𝑛 —— длина подарка (1≤n≤2⋅1051≤𝑛≤2⋅105).
Во второй строке дана строка s𝑠 длины n𝑛 —— Васин подарок. Гарантируется, что s𝑠 состоит только из нулей и единиц.
Формат выходных данных
Выведите единственное число —— количество различных гармоничных подстрок в s.
Обратите внимание, что значение ответа в этой задаче может превышать возможные значения 32‑битной целочисленной переменной, поэтому необходимо использовать 64‑битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Система оценки
Решения, правильно работающие для строк, целиком состоящих из нулей, будут оцениваться в 20 баллов.
Решения, правильно работающие при n≤100, будут оцениваться в 20 баллов.
Решения, правильно работающие при n≤1000, будут оцениваться в 30 баллов.
Замечание
В первом примере из условия подходят следующие подстроки (выделены жирным): 001100, 001100, 001100, 001100, 001100, 001100, 001100.
Ввод
6
001100
Вывод
7
Ввод
1
0
🔓 Узнать ответ