Задания и ответы на Олимпиады по Информатике 5, 6, 7, 8, 9, 10, 11 класс 25.10.2024 (4 группа)

Содержание
  1. 5-6 класс
  2. Задание 1. Города. Города словесная игра для нескольких человек. Каждый участник по очереди называет город, причём его название должно начинаться на ту же букву, которой оканчивается название города, озвученное предыдущим игроком. Например, за Сочи (последняя буква в названии и) может последовать Ижевск и т.д. Попробуйте из названий их столиц составить как можно более длинную цепочку (в информатике такая структура данных называется линейным двусвязным списком) для игры в города.
  3. Задание 2. Первое сентября. Три подружки Маша, Таня и Даша на первое сентября купили себе платья белого, красного и жёлтого цветов. Чтобы хорошо сочетаться друг с другом, они решили надеть банты таких же цветов. Известно, что: Цвет платья и банта не совпадает у каждой девочки. У Даши и Тани платье и бант белого цвета, но неизвестно, у кого что. У Маши и Тани платья красного и жёлтого цветов. Бант Даши и платье Маши красного цвета.
  4. Задание 3. Разрезанное число. У Тимофея есть полоска бумаги, на которой записано число 60966909609 (нетрудно заметить, что в его записи используются только цифры 0, 6 и 9). Мальчик хочет разрезать это число на две части и соединить их так, чтобы получилось как можно большее число. При этом каждую из двух получившихся частей можно переворачивать на 180 градусов и соединять в любом порядке.
  5. Задание 4. Сок. В бочке 12 литров сока. С помощью четырёх ёмкостей объёмами 3, 5, 6 и 7 литров нужно разделить сок между тремя людьми так, чтобы у каждого была ёмкость (или бочка) с одинаковым количеством сока. Как это сделать?От вас требуется составить как можно более короткий алгоритм распределения сока. Обозначим ёмкости 3, 5, 6 и 7 л буквами A, B, C и D соответственно, а 12-литровую бочку буквой Z. Для записи алгоритма используются команды вида X>Y (вместо X и Y используйте два различных символа из A, B, C, D), которые означают, что из ёмкости X происходит переливание сока в ёмкость Y.
  6. Задание 5. Многообещающая дата. Старик Хоттабыч называет дату многообещающей, если все цифры в её записи различны. При этом дата записывается в формате dd.mm.yyyy с ведущими нулями. Например, пятнадцатое марта 2025 года запишется как 15.03.2025. Эта дата не будет многообещающей, так как в её записи несколько раз встречаются цифры 0 и 2. А вот дата пятнадцатое марта 2469 года будет многообещающей в её записи 15.03.2469 все цифры различны.
  7. 7-8 класс
  8. Задание 1. Робот‑пылесос. Робот пылесос каждую ночь проводит уборку на территории склада, схему которого вы можете видеть ниже: прямоугольное поле размером w×h разделено на квадратные секции. Зарядная станция робота, с которой он начинает своё движение, расположена в одном из углов склада. На уборку каждой секции робот затрачивает одну минуту, после чего перемещается на соседнюю. К сожалению для уборщика, для удобства хранения товаров склад разделён полками, расположенными «змейкой». Сквозь полки робот пройти не может, поэтому по ходу движения ему приходится проходить через некоторые секции дважды (и дважды там убираться). На рисунке такие секции обозначены звёздочками. По данным w и h определите время, которое робот пылесос затратит на уборку склада.
  9. Задание 2. Маскарад. На школьном этапе ВсОШ по технологии участникам было предложено смоделировать и изготовить маску животного. С заданием успешно справились Белла, Захар, Егор и Харитон.Поскольку тур олимпиады, на котором необходимо защищать проект, довольно продолжителен, для перекуса каждый из ребят принёс свой любимый «лесной» продукт питания: грибы, орехи, ягоды и фрукты. Участникам необходимо представить свою работу: маски медведя, орла, кенгуру и бегемота.
  10. Задание 3. Разрезание строки. Сегодня на уроке информатики Данила узнал, что слова можно сравнивать в лексикографическом (алфавитном) порядке.Лексикографический порядок слов это способ их упорядочивания, аналогичный расположению в словаре. Сравнение слов при этом осуществляется по следующим правилам.Сравнение букв: сначала сравниваются первые символы слов. Слово, первый символ которого стоит раньше в алфавите, считается меньшим. Например, слово «яблоко» будет стоять после слова «груша», потому что «я» стоит позже «г».Длина слов: если два слова начинаются с одинаковых букв, то дальше сравниваются их символы по порядку.
  11. Задание 4. Головоломка с простыми числами. Для освоения темы «Простые числа» учитель математики Николай Николаевич предложил своим ученикам следующую задачу‑головоломку: в клетки таблицы 3×3 нужно расставить произвольные (возможно, повторяющиеся) целые числа от 0 до 10. После этого понадобится подсчитать суммы чисел в каждой из трёх строк и в каждом из трёх столбцов этой таблицы. Среди этих шести сумм нужно найти все простые числа и выписать каждое из них ровно по одному разу (то есть повторяющиеся простые числа не учитываются).
  12. Задание 5. Всё могут короли!Не могут они только стоять рядом друг с другом на шахматной доске (даже по диагонали). По размеру доски определите наибольшее количество королей, которое можно на ней расставить так, чтобы ещё одного короля поставить было невозможно.Формат входных данных. Единственная строка входного файла содержит одно натуральное число nn (1≤n≤109) размер квадратной шахматной доски.Формат выходных данных. Выведите одно натуральное число ответ на вопрос задачи.Обратите внимание, что при заданных ограничениях для хранения входных данных и ответа может понадобиться 64‑битный тип данных, например, long long в C++, int64 в Free Pascal, long в Java.
  13. Задание 6. Натуральный ряд. В научно‑исследовательском институте, где работает Тимофей, продолжается успешное исследование ряда натуральных чисел. Каждый день его коллеги открывают всё новые и новые свойства этой последовательности, и Тимофей старается от них не отставать. Сегодня Тимофей, как обычно, выписал на доске в ряд натуральные числа. Потом пришёл начальник отдела и стёр все числа, делящиеся на 2. Потом пришёл начальник другого отдела и стёр все числа из оставшихся, делящиеся на 3. Какое число теперь стоит на n-м месте в списке?Формат входных данных. Единственная строка входных данных содержит натуральное число nn (1≤n≤109).
  14. Задание 7. Городки. Городки старинная русская народная спортивная игра. В ней необходимо «выбивать» метанием биты различные деревянные фигуры, находящиеся на некотором расстоянии от игрока. Обычно участники самостоятельно приобретают комплекты для игры в спортивных магазинах, однако есть Очень Богатые Люди, готовые выложить за набор для игры из дорогих сортов древесины круглую сумму.Начинающий предприниматель Тимофей заинтересовался этим перспективным бизнесом. Для организации официальных соревнований требуется изготовить для участников одинаковые биты, а для этого сначала необходимо где‑то раздобыть как можно больше одинаковых деревянных палочек.
  15. 9-11 класс
  16. Задание 1. Всё могут короли!Не могут они только стоять рядом друг с другом на шахматной доске (даже по диагонали). По размеру доски определите наибольшее количество королей, которое можно на ней расставить так, чтобы ещё одного короля поставить было невозможно.Формат входных данных. Единственная строка входного файла содержит одно натуральное число nn (1≤n≤109) размер квадратной шахматной доски.Формат выходных данных. Выведите одно натуральное число ответ на вопрос задачи.
  17. Задание 2. Натуральный ряд. В научно‑исследовательском институте, где работает Тимофей, продолжается успешное исследование ряда натуральных чисел. Каждый день его коллеги открывают всё новые и новые свойства этой последовательности, и Тимофей старается от них не отставать. Сегодня Тимофей, как обычно, выписал на доске в ряд натуральные числа. Потом пришёл начальник отдела и стёр все числа, делящиеся на 2. Потом пришёл начальник другого отдела и стёр все числа из оставшихся, делящиеся на 3. Какое число теперь стоит на n-м месте в списке?Формат входных данныхЕдинственная строка входных данных содержит натуральное число nn (1≤n≤109).
  18. Задание 3. Городки. Городки старинная русская народная спортивная игра. В ней необходимо «выбивать» метанием биты различные деревянные фигуры, находящиеся на некотором расстоянии от игрока. Обычно участники самостоятельно приобретают комплекты для игры в спортивных магазинах, однако есть Очень Богатые Люди, готовые выложить за набор для игры из дорогих сортов древесины круглую сумму.Начинающий предприниматель Тимофей заинтересовался этим перспективным бизнесом. Для организации официальных соревнований требуется изготовить для участников одинаковые биты, а для этого сначала необходимо где‑то раздобыть как можно больше одинаковых деревянных палочек.
  19. Задание 4. Сон Пифагора. Если во сне вы производите вычитание,то это свидетельствует о неразвитостивашей личности и неготовности жить своим умом!Любовь Поливалина, «Сонник Пифагора». Пифагору снится тревожный сон ему следует из числа nn постоянно вычитать его последнюю цифру, не равную нулю. Например, при n=27 Пифагор сначала получит число 27−7=20, потом 20−2=18, 18−8=10, 10−1=9, 9−9=0. Получив число 0, великий учёный избавится от кошмара, но проблема лишь в том, что ему снится очень большое число.
  20. Задание 5. Геометрическая игра на планшете. Маленький Андрей изучает геометрические фигуры при помощи игры на планшете. У него есть равнобедренные прямоугольные треугольники четырёх цветов и ориентаций: жёлтые, зелёные, красные и синие. Для каждой разновидности треугольников есть заданное количество экземпляров этих треугольников. Более точно, у Андрея есть a жёлтых, b зелёных, c красных и d синих треугольников. Известно, что a≥b≥c≥d. Все треугольники одинаковые по размеру, но у каждого есть своя ориентация, которую нельзя менять. Треугольники одного цвета имеют одну и ту же ориентацию.Помимо этого, у мальчика есть n пустых ячеек, стороны которых совпадают с катетами треугольников.

5-6 класс

Задание 1. Города. Города словесная игра для нескольких человек. Каждый участник по очереди называет город, причём его название должно начинаться на ту же букву, которой оканчивается название города, озвученное предыдущим игроком. Например, за Сочи (последняя буква в названии и) может последовать Ижевск и т.д. Попробуйте из названий их столиц составить как можно более длинную цепочку (в информатике такая структура данных называется линейным двусвязным списком) для игры в города.

Для определённости считайте, что если название населённого пункта пишется через дефис, то оно начинается с первой буквы первого слова и заканчивается последней буквой второго слова. В игре используются все буквы русского алфавита.Расположите города в подходящем порядке. Чем длиннее будет ваша цепочка, тем больше баллов вы получите. Оцениваться будут только наборы названий городов, удовлетворяющие требованиям. Начать можно с любого населённого пункта из списка.Абакан-Анадырь-Барнаул-Биробиджан-Благовещенск-Владивосток-Горно-Алтайск-Иркутск-Кемерово-Красноярск-Кызыл-Магадан-Новосибирск-Петропавловск-Камчатский-Томск-Улан-Удэ-Хабаровск-Чита-Южно-Сахалинск-Якутск

Ответ: Чита Абакан Новосибирск Красноярск Кемерово

Задание 2. Первое сентября. Три подружки Маша, Таня и Даша на первое сентября купили себе платья белого, красного и жёлтого цветов. Чтобы хорошо сочетаться друг с другом, они решили надеть банты таких же цветов. Известно, что: Цвет платья и банта не совпадает у каждой девочки. У Даши и Тани платье и бант белого цвета, но неизвестно, у кого что. У Маши и Тани платья красного и жёлтого цветов. Бант Даши и платье Маши красного цвета.

Определите цвет банта и платья для каждой девочки.

Цвет платья: Белый, Жёлтый, Красный

Цвет банта: Белый, Жёлтый, Красный

Ответ:

  • Маша: красное платье, желтый бант
  • Даша: белое платье, красный бант
  • Таня: желтое платье, белый бант

Задание 3. Разрезанное число. У Тимофея есть полоска бумаги, на которой записано число 60966909609 (нетрудно заметить, что в его записи используются только цифры 0, 6 и 9). Мальчик хочет разрезать это число на две части и соединить их так, чтобы получилось как можно большее число. При этом каждую из двух получившихся частей можно переворачивать на 180 градусов и соединять в любом порядке.

Например, если бы у мальчика было число 609, то он смог бы получить из него число 960, причём двумя способами.Во‑первых, можно просто разрезать число на две части (60 и 9) и переставить их местами.Во‑вторых, можно разрезать число по‑другому (6 и 09). Перевернём 6 получим 9, перевернём 09 получим 60. Соединим части в том же порядке получим 960.Какое наибольшее число может получить Тимофей?

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

Ответ: 

Задание 4. Сок. В бочке 12 литров сока. С помощью четырёх ёмкостей объёмами 3, 5, 6 и 7 литров нужно разделить сок между тремя людьми так, чтобы у каждого была ёмкость (или бочка) с одинаковым количеством сока. Как это сделать?От вас требуется составить как можно более короткий алгоритм распределения сока. Обозначим ёмкости 3, 5, 6 и 7 л буквами A, B, C и D соответственно, а 12-литровую бочку буквой Z. Для записи алгоритма используются команды вида X>Y (вместо X и Y используйте два различных символа из A, B, C, D), которые означают, что из ёмкости X происходит переливание сока в ёмкость Y.

Команды записываются по одной в строке. Например, следующая последовательность команд:Z>B, Z>D, B>A, D>C, означает, что из бочки переливается сок в пятилитровую ёмкость, затем из бочки сок переливается в семилитровую ёмкость, затем из ёмкости вместимостью 5 л сок переливается в ёмкость объёмом 3 л, затем из ёмкости вместимостью 7 л сок переливается в шестилитровую ёмкость. После такой последовательности команд мы имеем 3+2+6+1=12 литров сока во всех ёмкостях.Обратите внимание нельзя перелить сок в количестве, не соответствующем свободному объёму хотя бы одной тары. Например, из полной семилитровой ёмкости нельзя перелить три литра в пустую шестилитровую. А вот если в шестилитровой уже есть три литра сока, то добавить ещё три можно.Оцениваться будут только решения, которые приводят к поставленной цели. Чем меньше шагов окажется в вашем алгоритме, тем больше баллов вы получите. За самый короткий алгоритм вы получите 100 баллов. За каждую избыточную команду будет сниматься по 15 баллов. Решения, в которых обнаружится некорректная команда (попытка перелить из пустой ёмкости, попытка перелить в полную ёмкость или попытка перелить из одной ёмкости в ту же самую), оцениваются в 0 баллов.

Ответ: 

Задание 5. Многообещающая дата. Старик Хоттабыч называет дату многообещающей, если все цифры в её записи различны. При этом дата записывается в формате dd.mm.yyyy с ведущими нулями. Например, пятнадцатое марта 2025 года запишется как 15.03.2025. Эта дата не будет многообещающей, так как в её записи несколько раз встречаются цифры 0 и 2. А вот дата пятнадцатое марта 2469 года будет многообещающей в её записи 15.03.2469 все цифры различны.

Считайте, что количество дней в месяце определяется по принятым сейчас правилам:28 дней в феврале невисокосного года;29 дней в феврале високосного года;30 дней в апреле, июне, сентябре, ноябре;31 день в январе, марте, мае, июле, августе, октябре и декабре.Ответьте на следующие вопросы.1) Сегодня 25 октября. В каком ближайшем году эта дата будет многообещающей?2) Когда была последняя многообещающая дата?3) Когда будет следующая многообещающая дата?4) Сколько многообещающих дат было в 1875 году?5) Какое наибольшее количество многообещающих дат может быть в календарном году при условии, что в его записи используется ровно четыре цифры?Если вы не можете ответить на какой‑то вопрос, то запишите в соответствующем поле любое положительное число. За каждый правильный ответ вам будет начислено по 20 баллов.

Ответ: 

7-8 класс

Задание 1. Робот‑пылесос. Робот пылесос каждую ночь проводит уборку на территории склада, схему которого вы можете видеть ниже: прямоугольное поле размером w×h разделено на квадратные секции. Зарядная станция робота, с которой он начинает своё движение, расположена в одном из углов склада. На уборку каждой секции робот затрачивает одну минуту, после чего перемещается на соседнюю. К сожалению для уборщика, для удобства хранения товаров склад разделён полками, расположенными «змейкой». Сквозь полки робот пройти не может, поэтому по ходу движения ему приходится проходить через некоторые секции дважды (и дважды там убираться). На рисунке такие секции обозначены звёздочками. По данным w и h определите время, которое робот пылесос затратит на уборку склада.

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

Ответ: (w-2)*(н-2) +w*н

Задание 2. Маскарад. На школьном этапе ВсОШ по технологии участникам было предложено смоделировать и изготовить маску животного. С заданием успешно справились Белла, Захар, Егор и Харитон.Поскольку тур олимпиады, на котором необходимо защищать проект, довольно продолжителен, для перекуса каждый из ребят принёс свой любимый «лесной» продукт питания: грибы, орехи, ягоды и фрукты. Участникам необходимо представить свою работу: маски медведя, орла, кенгуру и бегемота.

Известно, что: Харитон создал маску животного, впадающего в спячку. Харитон не любит есть грибы и фрукты. Белла и тот, кто принёс с собой орехи, создали маски хищников. Егор создал маску бегемота. Ни грибов, ни ягод у него с собой не было. Тот, кто создал маску орла, принёс с собой ягоды.Определите, кто какую маску создал и что с собой принёс на перекус.

Животное: Медведь, Орел, Кенгуру, Бегемот

Перекус: Грибы, Орехи, Ягоды, Фрукты

Ответ: 

  • Белла: маска орла, ягоды
  • Захар: маска кенгуру, грибы
  • Егор: маска бегемота, фрукты
  • Харитон: маска медведя, орехи

Задание 3. Разрезание строки. Сегодня на уроке информатики Данила узнал, что слова можно сравнивать в лексикографическом (алфавитном) порядке.Лексикографический порядок слов это способ их упорядочивания, аналогичный расположению в словаре. Сравнение слов при этом осуществляется по следующим правилам.Сравнение букв: сначала сравниваются первые символы слов. Слово, первый символ которого стоит раньше в алфавите, считается меньшим. Например, слово «яблоко» будет стоять после слова «груша», потому что «я» стоит позже «г».Длина слов: если два слова начинаются с одинаковых букв, то дальше сравниваются их символы по порядку.

Если одно слово является префиксом другого (например, «кот» и «котёнок»), то более короткое слово считается меньшим, даже если они совпадают до определённой позиции.Примеры: «собака» < «собачка», «дерево» < «долина», «апельсин» > «ананас». Такая система упорядочивания полезна для сортировки списков слов, поиска и обработки текстовой информации.В процессе подготовки к олимпиаде по информатике Данила написал на полоске бумаги слово «СИРИУСОЛИМП», разрезал полоску в nn местах и переставил получившиеся куски местами (все получившиеся части исходного слова были использованы). Он мечтает сделать исходный «СИРИУСОЛИМП» как можно большим.Ответьте на вопросы.1) Какое наибольшее слово в лексикографическом порядке он может получить при n=1 (то есть сделав единственный разрез)?2) Какое наибольшее слово в лексикографическом порядке он может получить при n=2?3) Какое наибольшее слово в лексикографическом порядке он может получить при n=3?4) Какое наименьшее количество разрезов необходимо сделать, чтобы получить из «СИРИУСОЛИМП» наибольшее лексикографическое слово?Каждый верный ответ даст 25 баллов. Менее точные ответы будут оцениваться меньшим количеством баллов.Буквы русского алфавита (для справки): А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я.

Ответ: 

Задание 4. Головоломка с простыми числами. Для освоения темы «Простые числа» учитель математики Николай Николаевич предложил своим ученикам следующую задачу‑головоломку: в клетки таблицы 3×3 нужно расставить произвольные (возможно, повторяющиеся) целые числа от 0 до 10. После этого понадобится подсчитать суммы чисел в каждой из трёх строк и в каждом из трёх столбцов этой таблицы. Среди этих шести сумм нужно найти все простые числа и выписать каждое из них ровно по одному разу (то есть повторяющиеся простые числа не учитываются).

Выигрывает тот ученик, у которого полученная сумма различных простых чисел окажется самой большой.Рассмотрим пример. Один из учеников Николая Николаевича расположил в таблице числа следующим образом:

Среди полученных шести сумм по строкам и столбцам этой таблицы встречаются один раз простое число 3 и три раза простое число 5. Так как в итоге учитываются только различные простые числа, результат этого ученика равен сумме 3+5, то есть 8.Вам предлагается поучаствовать в решении этой головоломки. Заполните ячейки в таблице целыми числами от 1 до 10. Далее проверяющая программа найдёт все суммы в вашей таблице по строкам и все суммы по столбцам и просуммирует все различные простые числа среди этих шести сумм. Чем больше окажутся значение этой суммы и количество различных простых чисел в ней, тем выше будет оценена попытка.Замечание. Далее приводится список всех простых чисел, не превосходящих 50: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

Ответ: 

Задание 5. Всё могут короли!Не могут они только стоять рядом друг с другом на шахматной доске (даже по диагонали). По размеру доски определите наибольшее количество королей, которое можно на ней расставить так, чтобы ещё одного короля поставить было невозможно.Формат входных данных. Единственная строка входного файла содержит одно натуральное число nn (1≤n≤109) размер квадратной шахматной доски.Формат выходных данных. Выведите одно натуральное число ответ на вопрос задачи.Обратите внимание, что при заданных ограничениях для хранения входных данных и ответа может понадобиться 64‑битный тип данных, например, long long в C++, int64 в Free Pascal, long в Java.

Система оценки. Решения, верно работающие при 1≤n≤100, получат не менее 30 баллов.Решения, верно работающие при 1≤n≤105, получат не менее 60 баллов.Замечание. Смотри рисунок:

Ввод3 Вывод4

Ответ: 

Задание 6. Натуральный ряд. В научно‑исследовательском институте, где работает Тимофей, продолжается успешное исследование ряда натуральных чисел. Каждый день его коллеги открывают всё новые и новые свойства этой последовательности, и Тимофей старается от них не отставать. Сегодня Тимофей, как обычно, выписал на доске в ряд натуральные числа. Потом пришёл начальник отдела и стёр все числа, делящиеся на 2. Потом пришёл начальник другого отдела и стёр все числа из оставшихся, делящиеся на 3. Какое число теперь стоит на n-м месте в списке?Формат входных данных. Единственная строка входных данных содержит натуральное число nn (1≤n≤109).

Формат выходных данных. Выведите одно натуральное число ответ на вопрос задачи.Обратите внимание, что при заданных ограничениях для хранения входных данных и ответа может понадобиться 64‑битный тип данных, например, long long в C++, int64 в Free Pascal, long в Java.Система оценки. Решения, верно работающие при 1≤n≤105, получат не менее 40 баллов.Замечание. В примере дано n=5.Из исходного ряда натуральных чисел 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, …… сначала были удалены числа 2, 4, 6, 8, …… (как делящиеся на 2).Остался ряд 1, 3, 5, 7, 9, 11, 13, 15, ……Потом из него были удалены числа 3, 9, 15, …… (как делящиеся на 3).Остался ряд 1, 5, 7, 11, 13, ……На пятом месте число 13.Ввод5Вывод13

Ответ: 

Задание 7. Городки. Городки старинная русская народная спортивная игра. В ней необходимо «выбивать» метанием биты различные деревянные фигуры, находящиеся на некотором расстоянии от игрока. Обычно участники самостоятельно приобретают комплекты для игры в спортивных магазинах, однако есть Очень Богатые Люди, готовые выложить за набор для игры из дорогих сортов древесины круглую сумму.Начинающий предприниматель Тимофей заинтересовался этим перспективным бизнесом. Для организации официальных соревнований требуется изготовить для участников одинаковые биты, а для этого сначала необходимо где‑то раздобыть как можно больше одинаковых деревянных палочек.

В распоряжении Тимофея есть палочки‑заготовки из дорогого красного дерева в форме цилиндров одинакового радиуса, но самой разной длины, из которых он и собирается изготовить биты.Если длина палочки является чётным числом d, Тимофей может распилить её пополам и получить две палочки вдвое меньшей длины d2. Если же длина палочки является нечётным числом, Тимофей может распилить её на две части, как можно меньше отличающиеся друг от друга: ⌊d2(d пополам, округлённое вниз до целой части) и ⌈d2⌉ (d пополам, округлённое вверх до целой части). Распиливать уже распиленные ранее палочки Тимофею лень, и он переходит к следующей заготовке. Задача Тимофея получить наибольшее количество бит какого‑нибудь одного размера. Если таких размеров несколько, Тимофей выберет для организации соревнований наименьший.Формат входных данныхВ первой строке входных данных записано одно натуральное число: nn (1≤n≤105) длина самой длинной заготовки.В следующих nn строках записано по одному натуральному числу didi (0≤di≤109, dn≠0) количество палочек длины i−1. Так, во второй строке записано количество палочек длины 1, в третьей количество палочек длины 2 и так далее. В последней строке записано количество палочек длины nn.Обратите внимание, что при заданных ограничениях для хранения входных данных и ответа может понадобиться 64‑битный тип данных, например, long long в C++, int64 в Free Pascal, long в Java.Формат выходных данныхВыведите в двух строках два натуральных числа наибольшее количество получившихся палочек одного размера и сам этот размер.Система оценкиРешения, верно работающие при n≤3, получат не менее 30 баллов.Решения, верно работающие при n≤1000, получат не менее 70 баллов.ЗамечаниеУ Тимофея есть несколько палочек, самая длинная имеет длину 5. Более точно:Нет палочек длины 1;Одна палочка длины 2;Нет палочек длины 3;Одна палочка длины 4;Две палочки длины 5.Тимофей распилит пополам палочку длины 4 и получит две палочки длины 2. Также он распилит обе палочки длины 5 и получит две палочки длины 2 и две палочки длины 3. Вместе с имеющейся у него одной исходной палочкой длины 2 (её Тимофей пилить не будет) в его распоряжении окажется пять одинаковых палочек длины 2. Это наилучший результат, который может получить Тимофей (наибольшее количество палочек длины 1, которое можно получить из исходного набора, равно двум; палочек длины 3 двум; палочек длины 4 одному; палочек длины 5 двум).

Ввод501012 Вывод52

Ответ: 

9-11 класс

Задание 1. Всё могут короли!Не могут они только стоять рядом друг с другом на шахматной доске (даже по диагонали). По размеру доски определите наибольшее количество королей, которое можно на ней расставить так, чтобы ещё одного короля поставить было невозможно.Формат входных данных. Единственная строка входного файла содержит одно натуральное число nn (1≤n≤109) размер квадратной шахматной доски.Формат выходных данных. Выведите одно натуральное число ответ на вопрос задачи.

Обратите внимание, что при заданных ограничениях для хранения входных данных и ответа может понадобиться 64‑битный тип данных, например, long long в C++, int64 в Free Pascal, long в Java.Система оценки. Решения, верно работающие при 1≤n≤100, получат не менее 30 баллов.Решения, верно работающие при 1≤n≤105, получат не менее 60 баллов.Замечание. Смотри рисунок:

Ввод3 Вывод4

Ответ: 

Задание 2. Натуральный ряд. В научно‑исследовательском институте, где работает Тимофей, продолжается успешное исследование ряда натуральных чисел. Каждый день его коллеги открывают всё новые и новые свойства этой последовательности, и Тимофей старается от них не отставать. Сегодня Тимофей, как обычно, выписал на доске в ряд натуральные числа. Потом пришёл начальник отдела и стёр все числа, делящиеся на 2. Потом пришёл начальник другого отдела и стёр все числа из оставшихся, делящиеся на 3. Какое число теперь стоит на n-м месте в списке?Формат входных данныхЕдинственная строка входных данных содержит натуральное число nn (1≤n≤109).

Формат выходных данныхВыведите одно натуральное число ответ на вопрос задачи.Обратите внимание, что при заданных ограничениях для хранения входных данных и ответа может понадобиться 64‑битный тип данных, например, long long в C++, int64 в Free Pascal, long в Java.Система оценкиРешения, верно работающие при 1≤n≤105, получат не менее 40 баллов.ЗамечаниеВ примере дано n=5.Из исходного ряда натуральных чисел 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, …… сначала были удалены числа 2, 4, 6, 8, …… (как делящиеся на 2).Остался ряд 1, 3, 5, 7, 9, 11, 13, 15, ……Потом из него были удалены числа 3, 9, 15, …… (как делящиеся на 3).Остался ряд 1, 5, 7, 11, 13, ……На пятом месте число 13.Ввод5Вывод13

Ответ: 

Задание 3. Городки. Городки старинная русская народная спортивная игра. В ней необходимо «выбивать» метанием биты различные деревянные фигуры, находящиеся на некотором расстоянии от игрока. Обычно участники самостоятельно приобретают комплекты для игры в спортивных магазинах, однако есть Очень Богатые Люди, готовые выложить за набор для игры из дорогих сортов древесины круглую сумму.Начинающий предприниматель Тимофей заинтересовался этим перспективным бизнесом. Для организации официальных соревнований требуется изготовить для участников одинаковые биты, а для этого сначала необходимо где‑то раздобыть как можно больше одинаковых деревянных палочек.

В распоряжении Тимофея есть палочки‑заготовки из дорогого красного дерева в форме цилиндров одинакового радиуса, но самой разной длины, из которых он и собирается изготовить биты.Если длина палочки является чётным числом d, Тимофей может распилить её пополам и получить две палочки вдвое меньшей длины d2. Если же длина палочки является нечётным числом, Тимофей может распилить её на две части, как можно меньше отличающиеся друг от друга: ⌊d2(d пополам, округлённое вниз до целой части) и ⌈d2⌉ (d пополам, округлённое вверх до целой части). Распиливать уже распиленные ранее палочки Тимофею лень, и он переходит к следующей заготовке. Задача Тимофея получить наибольшее количество бит какого‑нибудь одного размера. Если таких размеров несколько, Тимофей выберет для организации соревнований наименьший.Формат входных данныхВ первой строке входных данных записано одно натуральное число: nn (1≤n≤105) длина самой длинной заготовки.В следующих nn строках записано по одному натуральному числу didi (0≤di≤109, dn≠0) количество палочек длины i−1. Так, во второй строке записано количество палочек длины 1, в третьей количество палочек длины 2 и так далее. В последней строке записано количество палочек длины nn.Обратите внимание, что при заданных ограничениях для хранения входных данных и ответа может понадобиться 64‑битный тип данных, например, long long в C++, int64 в Free Pascal, long в Java.Формат выходных данныхВыведите в двух строках два натуральных числа наибольшее количество получившихся палочек одного размера и сам этот размер.Система оценкиРешения, верно работающие при n≤3, получат не менее 30 баллов.Решения, верно работающие при n≤1000, получат не менее 70 баллов.ЗамечаниеУ Тимофея есть несколько палочек, самая длинная имеет длину 5. Более точно:Нет палочек длины 1;Одна палочка длины 2;Нет палочек длины 3;Одна палочка длины 4;Две палочки длины 5.Тимофей распилит пополам палочку длины 4 и получит две палочки длины 2. Также он распилит обе палочки длины 5 и получит две палочки длины 2 и две палочки длины 3. Вместе с имеющейся у него одной исходной палочкой длины 2 (её Тимофей пилить не будет) в его распоряжении окажется пять одинаковых палочек длины 2. Это наилучший результат, который может получить Тимофей (наибольшее количество палочек длины 1, которое можно получить из исходного набора, равно двум; палочек длины 3 двум; палочек длины 4 одному; палочек длины 5 двум).Ввод501012Вывод52

Ответ: 

Задание 4. Сон Пифагора. Если во сне вы производите вычитание,то это свидетельствует о неразвитостивашей личности и неготовности жить своим умом!Любовь Поливалина, «Сонник Пифагора». Пифагору снится тревожный сон ему следует из числа nn постоянно вычитать его последнюю цифру, не равную нулю. Например, при n=27 Пифагор сначала получит число 27−7=20, потом 20−2=18, 18−8=10, 10−1=9, 9−9=0. Получив число 0, великий учёный избавится от кошмара, но проблема лишь в том, что ему снится очень большое число.

Сколько вычитаний придётся совершить Пифагору, пока он не доберётся до нуля?Формат входных данных. Единственная строка входных данных содержит натуральное число n (1≤n≤1018).Формат выходных данных. Выведите одно натуральное число ответ на вопрос задачи.Система оценки. Решения, правильно работающие при n≤105, будут оцениваться в 30 баллов.Ввод27Вывод5→ Узнать ответ

Задание 5. Геометрическая игра на планшете. Маленький Андрей изучает геометрические фигуры при помощи игры на планшете. У него есть равнобедренные прямоугольные треугольники четырёх цветов и ориентаций: жёлтые, зелёные, красные и синие. Для каждой разновидности треугольников есть заданное количество экземпляров этих треугольников. Более точно, у Андрея есть a жёлтых, b зелёных, c красных и d синих треугольников. Известно, что a≥b≥c≥d. Все треугольники одинаковые по размеру, но у каждого есть своя ориентация, которую нельзя менять. Треугольники одного цвета имеют одну и ту же ориентацию.Помимо этого, у мальчика есть n пустых ячеек, стороны которых совпадают с катетами треугольников.

Игра происходит пошагово, на каждом шаге Андрей может взять очередной треугольник и переместить его параллельным сдвигом в одну из ячеек. При этом в одну ячейку можно поместить либо вместе жёлтый и красный треугольники, либо вместе зелёный и синий, либо один любой треугольник из имеющихся.На каждом шаге можно переместить треугольник строго одного текущего цвета. Сначала это жёлтый, на следующем ходе зелёный, далее красный и затем синий. Далее снова жёлтый, зелёный, красный, синий и т.д по циклу. Если места для текущего цвета нет либо треугольники текущего цвета закончились, то этот цвет пропускается и ходит следующий по порядку цвет.Допустим, в данном шаге есть треугольник текущего цвета. Если ещё есть пустая ячейка, данный треугольник обязательно помещается в эту ячейку. Если пустые ячейки закончились, но есть полупустая ячейка с парным текущему цветом, то треугольник помещается в неё. Игра длится до тех пор, пока есть цвет, который можно поместить в какую‑то ячейку.Определите, сколько каких треугольников Андрей распределит в конечном итоге по ячейкам.Формат входных данных. На вход подаются четыре числа a, b, c, d, каждое в своей строке. Гарантируется, что a≥b≥c≥da≥b≥c≥d. В пятой строке содержится число n количество пустых ячеек. 1≤a, b, c, d≤1018, 1≤n≤1018.Обратите внимание, что значения переменных в этой задаче могут превышать возможные значения 32-битной целочисленной переменной, поэтому необходимо использовать 6464-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, long в Java и C#).Формат выходных данных. Выведите ответ в четыре строки: для каждого соответствующего цвета укажите, сколько треугольников этого цвета получится поместить в ячейки. В первую строку выведите число жёлтых треугольников, во вторую зелёных, в третью красных и в четвёртую синих.Система оценки. Решения, верно работающие при 1≤a, b, c, d, n≤1000, будут оцениваться в 30 баллов.Решения, верно работающие при 4≤a+b+c+d≤106 и 1≤n≤106, будут оцениваться в 60 баллов.Замечание. Для первого примера из условия проиллюстрируем некоторые промежуточные ситуации:

Положение после 14 первых ходов, если Андрей раскладывал треугольники по ячейкам слева направо. На данный момент закончились все пустые ячейки и треугольники красного и синего цветов.

Итоговое положение после 18 ходов. Дополнительно получилось разложить ещё три жёлтых треугольника и один зелёный. Зелёные треугольники тоже закончились, а для жёлтых закончились места. Итого Андрей разложил 8 жёлтых, 5 зелёных, 3 красных и 2 синих треугольника.Ввод2053214Вывод8532Ввод77779Вывод5454

Ответ: 

Понравилась статья? Поделиться с друзьями:
Всё о функциональной грамотности
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: