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

Содержание
  1. 5-6 класс
  2. Задание 1: Квадрат. В квадрате 3×3 расставили числа от 1 до 9. Затем внутри этого квадрата взяли все квадраты 2×2 и посчитали сумму чисел в каждом их них, а потом сложили все полученные суммы.
  3. Задание 2: Переправа. Семье из мамы и пяти детей в возрасте 5, 6, 7, 8 и 9 лет нужно переправиться через реку, с левого берега на правый. У них есть лодка, которая может вместить маму (которая обязательно должна плыть в лодке) и не более чем двух детей.Если на берегу без мамы останутся два ребёнка, возраст которых отличается на 1 год (то есть 5 и 6 лет или 6 и 7 лет и т.д.), то они подерутся.
  4. Задание 3: Чаепитие. Слон Семён каждое утро пьёт чай и ест бутерброды с яблочным вареньем. У него есть длинный стол, на котором в ряд слева направо выставлены чашки чая и банки с вареньем и выложен хлеб. Чтобы чаепитие удалось, нужно, чтобы при просмотре слева направо сначала шёл весь хлеб, затем всё варенье, и затем весь чай. Слон использует хобот для перестановки предметов, поэтому за одну секунду он может поменять местами только два соседних предмета. Обозначим хлеб буквой «Х», варенье буквой «В», чай буквой «Ч».
  5. Задание 4: Набор на кружки. Учащиеся школы должны выбрать себе дополнительные занятия на год. Каждый из них выбрал как минимум один предмет из предложенных: биологии, музыки и шахмат. Известно, что 150 школьников выбрали биологию, 130 учеников музыку и 100 шахматы, но каждый учащийся мог выбрать и несколько предметов.
  6. Задание 5: Кратчайший поезд. Вам необходимо составить поезд из нескольких последовательно сцепленных вагонов, обозначенных буквами. Грузовой вагон (F). Таких вагонов в поезде должно быть 5. Вагон с ценностями (V). Таких вагонов в поезде должно быть 5. Вагон с охраной (G). Локомотив (L). При этом требуется соблюсти следующие правила. Первым и последним вагонами поезда должны быть локомотивы (L).
  7. 7-8 класс
  8. Задание 1: Чаепитие. Слон Семён каждое утро пьёт чай и ест бутерброды с яблочным вареньем. У него есть длинный стол, на котором в ряд слева направо выставлены чашки чая и банки с вареньем и выложен хлеб. Чтобы чаепитие удалось, нужно, чтобы при просмотре слева направо сначала шёл весь хлеб, затем всё варенье, и затем весь чай. Слон использует хобот для перестановки предметов, поэтому за одну секунду он может поменять местами только два соседних предмета. Обозначим хлеб буквой «Х», варенье буквой «В», чай буквой «Ч».
  9. Задание 2: Набор на кружки. Учащиеся школы должны выбрать себе дополнительные занятия на год. Каждый из них выбрал как минимум один предмет из предложенных: биологии, музыки и шахмат. Известно, что 150 школьников выбрали биологию, 130 учеников музыку и 100 шахматы, но каждый учащийся мог выбрать и несколько предметов.
  10. Задание 3: Кратчайший путь. Есть 7 городов, обозначенных буквами английского алфавита A, B, C, D, E, F, G. Вы хотите посетить эти все города ровно по одному разу каждый и вернуться в начальную точку своего путешествия. Для этого вы можете воспользоваться самолётами: между двумя любыми городами есть прямой авиарейс.
  11. Задание 4: Задание 4. Путешествие. Данис живёт на клетчатой плоскости и может перемещаться по плоскости в одном из четырёх направлений: направо, налево, вверх, вниз. За один шаг он перемещается на единицу длины. Ось OX (первая координата) направлена вправо, ось OY (вторая координата) направлена вверх. Данис начинает путь в точке (0; 0). Например, если он выполнит четыре команды перемещения «направо», «вниз», «налево», «вверх», то посетит следующие точки: (1; 0), (1; −1), (0; −1), (0; 0).
  12. Задание 5: Качели. Трое друзей Аня, Боря и Саша пришли на детскую площадку, чтобы покачаться на качелях‑балансире. Качели представляют собой длинную балку, закреплённую в центре, на которую дети садятся с разных концов. Массы детей равны A, B и C кг. Чтобы держать баланс на качелях, разница масс на двух концах качелей должна быть не более D кг.
  13. Задание 6. Фонари. Вдоль прямой улицы на равном расстоянии располагаются N домов. Будем считать расстояние между домами за единицу длины.Около каждого дома можно поставить один фонарь. Всего имеется A фонарей, которые могут освещать дома на расстоянии X (включительно), и B фонарей, которые могут освещать дома на расстоянии Y (включительно). В частности, при X=0 или Y=0 такой фонарь освещает только тот дом, у которого он установлен.Вам необходимо расставить минимальное число фонарей так, чтобы все дома были освещены. Один дом может быть освещён несколькими фонарями. Освещать участки улицы между домами необязательно.
  14. Задание 7. Деление шоколадки. У Маши есть прямоугольная шоколадка, состоящая из m×nm×n квадратных долек. Маша хочет разделить эту шоколадку между своими друзьями, разломив шоколадку по линиям на k кусочков, то есть каждому другу достанется прямоугольный кусочек шоколадки.У Юры сегодня день рождения, поэтому Маша хочет разделить шоколадку так, чтобы Юре достался самый большой кусок (содержащий как можно больше долек).
  15. 9-11 класс
  16. Задание 1: Качели. Трое друзей Аня, Боря и Саша пришли на детскую площадку, чтобы покачаться на качелях‑балансире. Качели представляют собой длинную балку, закреплённую в центре, на которую дети садятся с разных концов.
  17. Задание 2: Фонари. Вдоль прямой улицы на равном расстоянии располагаются N домов. Будем считать расстояние между домами за единицу длины.Около каждого дома можно поставить один фонарь. Всего имеется A фонарей, которые могут освещать дома на расстоянии X (включительно), и B фонарей, которые могут освещать дома на расстоянии Y (включительно). В частности, при X=0 или Y=0 такой фонарь освещает только тот дом, у которого он установлен.
  18. Задание 3: Красная Шапочка на болоте. Красная Шапочка отправилась на болото для сбора клюквы, чтобы испечь пирожки для бабушки. Клюквенное болото представляет собой координатную прямую. Берег, на котором стоит Шапочка, имеет координату 0, а клюквенная поляна координату N+1. В точках с координатами 1, 2, ……, NN расположены кочки.
  19. Задание 4: Деление шоколадки. У Маши есть прямоугольная шоколадка, состоящая из m×nm×n квадратных долек. Маша хочет разделить эту шоколадку между своими друзьями, разломив шоколадку по линиям на k кусочков, то есть каждому другу достанется прямоугольный кусочек шоколадки.У Юры сегодня день рождения, поэтому Маша хочет разделить шоколадку так, чтобы Юре достался самый большой кусок (содержащий как можно больше долек). Определите число долек в этом куске.
  20. Задание 5: Кодовый замок. В разведывательное управление доставили сейф с секретной информацией, кодовый замок на котором открывается комбинацией из nn цифр, каждая цифра может принимать b различных значений от 0 до b−1. Код неизвестен, однако разведчики передали несколько донесений о том, что сумма цифр кода в некоторых заданных позициях равна какому‑то известному числу. Используя информацию из всех полученных донесений, определите, сколько существует возможных кодов, удовлетворяющих этим условиям.

5-6 класс

Задание 1: Квадрат. В квадрате 3×3 расставили числа от 1 до 9. Затем внутри этого квадрата взяли все квадраты 2×2 и посчитали сумму чисел в каждом их них, а потом сложили все полученные суммы.

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

Ответ: 1  8  3

 7  9  5

             2  6  4

Задание 2: Переправа. Семье из мамы и пяти детей в возрасте 5, 6, 7, 8 и 9 лет нужно переправиться через реку, с левого берега на правый. У них есть лодка, которая может вместить маму (которая обязательно должна плыть в лодке) и не более чем двух детей.Если на берегу без мамы останутся два ребёнка, возраст которых отличается на 1 год (то есть 5 и 6 лет или 6 и 7 лет и т.д.), то они подерутся.

Составьте план переправы через реку так, чтобы никто не подрался.Запишите несколько строк, каждая из которых содержит одно или два числа, соответствующие возрасту детей (то есть одно или два числа из множества 5, 6, 7, 8, 9). Мама переплывает реку на каждом шаге. Если мама переплывает реку без детей, напишите в этой строке знак «-».Нечётные строки соответствуют перемещению лодки с левого берега на правый, чётные строки в противоположном направлении. Каждое перемещение указывайте в отдельном поле, добавляя их нажатием кнопки внизу экрана. Числа разделяйте пробелами.Чем меньше строк будет в вашем ответе, тем больше баллов вы получите.

Ответ:

6 8

7 9

6 8

6 5

6

6 8

 

Задание 3: Чаепитие. Слон Семён каждое утро пьёт чай и ест бутерброды с яблочным вареньем. У него есть длинный стол, на котором в ряд слева направо выставлены чашки чая и банки с вареньем и выложен хлеб. Чтобы чаепитие удалось, нужно, чтобы при просмотре слева направо сначала шёл весь хлеб, затем всё варенье, и затем весь чай. Слон использует хобот для перестановки предметов, поэтому за одну секунду он может поменять местами только два соседних предмета. Обозначим хлеб буквой «Х», варенье буквой «В», чай буквой «Ч».

Тогда последовательность предметов на столе задаётся строкой из этих букв. Например, при расстановке предметов «ВЧXВ» на подготовку стола потребуется три секунды. Предметы, которые переставляются местами каждую секунду, подчёркнуты.1. ВХЧХЧВ2. ХВХВЧВ3. ХВВЧВЧ. Слон торопится и поэтому хочет знать, при какой первоначальной расстановке предметов у него уйдёт наибольшее время на подготовку стола.Запишите последовательность из букв «Х», «В», «Ч» для четырёх случаев. Количество предметов каждого вида вы можете выбрать самостоятельно, но общее число букв в ответе должно соответствовать заданному.

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

Ответ:

ЧВХ

ЧЧВВХХ

ЧЧЧВВХХ

ЧЧЧВВХХХ

Задание 4: Набор на кружки. Учащиеся школы должны выбрать себе дополнительные занятия на год. Каждый из них выбрал как минимум один предмет из предложенных: биологии, музыки и шахмат. Известно, что 150 школьников выбрали биологию, 130 учеников музыку и 100 шахматы, но каждый учащийся мог выбрать и несколько предметов.

Ответьте на вопросы. Если вы не можете дать ответ на какой‑то вопрос, запишите в ответе любое число.1. Какое минимальное количество учащихся могло быть в школе?2. Какое максимальное количество учащихся могло быть в школе?3. Считайте, что одновременно биологию и музыку выбрали 85 учащихся. Сколько школьников выбрало ровно один из этих двух предметов?4. Считайте, что ни один школьник не выбрал одновременно биологию и шахматы, одновременно биологию и музыку выбрали 60 учеников, а всего в школе 250 учащихся. Сколько школьников выбрало и шахматы, и музыку?5. Считайте, что в ситуации из пункта 4 на кружки разрешили записываться учащимся других школ. Какое минимальное дополнительное количество школьников должно записаться на предложенные предметы, чтобы количество людей, посещающих только музыку, стало равняться количеству людей, не посещающих её?

Ответ:

Задание 5: Кратчайший поезд. Вам необходимо составить поезд из нескольких последовательно сцепленных вагонов, обозначенных буквами. Грузовой вагон (F). Таких вагонов в поезде должно быть 5. Вагон с ценностями (V). Таких вагонов в поезде должно быть 5. Вагон с охраной (G). Локомотив (L). При этом требуется соблюсти следующие правила. Первым и последним вагонами поезда должны быть локомотивы (L).

В середине поезда также необходимо расположить дополнительные вагоны‑локомотивы. В поезде не должно быть цепочки из подряд идущих 8 и более вагонов без локомотива.Каждый вагон с ценностями (V) должен быть непосредственно прицеплен к вагону с охраной (G).Каждый грузовой вагон (F) должен быть прицеплен к вагону с охраной (G) или другому вагону, прицепленному к вагону с охраной (то есть между грузовым вагоном и вагоном с охраной находится один вагон).Составьте поезд, удовлетворяющий этим условиям и содержащий наименьшее число вагонов. В вашем поезде должно быть ровно 5 грузовых вагонов (F) и ровно 5 вагонов с ценностями (V).

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

Ответ:

7-8 класс

Задание 1: Чаепитие. Слон Семён каждое утро пьёт чай и ест бутерброды с яблочным вареньем. У него есть длинный стол, на котором в ряд слева направо выставлены чашки чая и банки с вареньем и выложен хлеб. Чтобы чаепитие удалось, нужно, чтобы при просмотре слева направо сначала шёл весь хлеб, затем всё варенье, и затем весь чай. Слон использует хобот для перестановки предметов, поэтому за одну секунду он может поменять местами только два соседних предмета. Обозначим хлеб буквой «Х», варенье буквой «В», чай буквой «Ч».

Тогда последовательность предметов на столе задаётся строкой из этих букв. Например, при расстановке предметов «ВЧXВ» на подготовку стола потребуется три секунды. Предметы, которые переставляются местами каждую секунду, подчёркнуты.

1. ВХЧВ

2. ХВЧВ

3. ХВВЧ

Слон торопится и поэтому хочет знать, при какой первоначальной расстановке предметов у него уйдёт наибольшее время на подготовку стола.Запишите последовательность из букв «Х», «В», «Ч» для четырёх случаев. Количество предметов каждого вида вы можете выбрать самостоятельно, но общее число букв в ответе должно соответствовать заданному. Вы должны найти такую расстановку, при которой подготовка стола займёт наибольшее время для данного числа предметов.

Если вы не можете найти ответ для какого‑то случая, запишите любую строку из букв «Х», «В», «Ч» нужной длины.

Ответ:

  • 3 предмета – ЧВХ
  • 9 предметов – ЧЧЧВВВХХХ
  • 11 предметов – ЧЧЧЧВВВВХХХ
  • 13 предметов – ЧЧЧЧЧВВВВХХХХ

Задание 2: Набор на кружки. Учащиеся школы должны выбрать себе дополнительные занятия на год. Каждый из них выбрал как минимум один предмет из предложенных: биологии, музыки и шахмат. Известно, что 150 школьников выбрали биологию, 130 учеников музыку и 100 шахматы, но каждый учащийся мог выбрать и несколько предметов.

Ответ:

1. Какое минимальное количество учащихся могло быть в школе? – 150

2. Какое максимальное количество учащихся могло быть в школе? – 380

3. Считайте, что одновременно биологию и музыку выбрали 85 учащихся. Сколько школьников выбрало ровно один из этих двух предметов? – 195

4. Считайте, что ни один школьник не выбрал одновременно биологию и шахматы, одновременно биологию и музыку выбрали 60 учеников, а всего в школе 250 учащихся. Сколько школьников выбрало и шахматы, и музыку? – 250

5. Считайте, что в ситуации из пункта 4 на кружки разрешили записываться учащимся других школ. Какое минимальное дополнительное количество школьников должно записаться на предложенные предметы, чтобы количество людей, посещающих только музыку, стало равняться количеству людей, не посещающих её? – 180

Задание 3: Кратчайший путь. Есть 7 городов, обозначенных буквами английского алфавита A, B, C, D, E, F, G. Вы хотите посетить эти все города ровно по одному разу каждый и вернуться в начальную точку своего путешествия. Для этого вы можете воспользоваться самолётами: между двумя любыми городами есть прямой авиарейс.

Стоимость перелёта между парой городов приведена в следующей таблице.

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

Ответ:

Задание 4: Задание 4. Путешествие. Данис живёт на клетчатой плоскости и может перемещаться по плоскости в одном из четырёх направлений: направо, налево, вверх, вниз. За один шаг он перемещается на единицу длины. Ось OX (первая координата) направлена вправо, ось OY (вторая координата) направлена вверх. Данис начинает путь в точке (0; 0). Например, если он выполнит четыре команды перемещения «направо», «вниз», «налево», «вверх», то посетит следующие точки: (1; 0), (1; −1), (0; −1), (0; 0).

Всего Данис сделал 1000 шагов, после чего захотел узнать ответы на следующие вопросы.1. Сколько раз Данис прошёл через точку (−11; 9)?2. Какое количество различных точек посетил Данис?3. В какой точке Данис побывал больше всего раз?Абсцисса (первая координата): Ордината (вторая координата): 4. Какая посещённая им точка находится ближе всего к точке (10; 6)? Расстоянием между точками считается количество ходов, которые нужно сделать для того, чтобы попасть из одной точки в другую, то есть так называемое манхэттенское расстояние.Абсцисса (первая координата): Ордината (вторая координата): Для выполнения задания вы можете использовать электронные таблицы из офисного пакета или любые другие средства вашего компьютера. Вы можете скачать файл с данными для выполнения этого задания в одном из двух форматов: Microsoft Excel (XLSX) или LibreOffice Calc (ODS).В этой таблице в единственном столбце с данными A содержится последовательность перемещений Даниса.Если вы не знаете ответ на какой‑нибудь вопрос, запишите вместо него любое число.

Ответ:

Задание 5: Качели. Трое друзей Аня, Боря и Саша пришли на детскую площадку, чтобы покачаться на качелях‑балансире. Качели представляют собой длинную балку, закреплённую в центре, на которую дети садятся с разных концов. Массы детей равны A, B и C кг. Чтобы держать баланс на качелях, разница масс на двух концах качелей должна быть не более D кг.

Друзьям повезло: рядом с площадкой оказалась груда достаточно тяжёлых камней. Один из детей может взять с собой любой камень, чтобы сделать разность масс на концах качелей допустимой. Помогите друзьям определить минимальную массу камня, благодаря которому они смогут покачаться на качелях.Формат входных данныхПрограмма получает на вход три числа A, B, C, записанных в отдельных строках, массы друзей. В четвёртой строке записано число D наибольшая допустимая разница масс на концах качелей. Все числа целые, положительные и не превосходящие 109.Формат выходных данныхПрограмма должна вывести одно целое число минимально необходимую массу камня, которую нужно добавить на одну из сторон качелей, чтобы друзья смогли покачаться на них, сев оптимально. Если камень им не понадобится, программа должна вывести число 0.Система оценкиРешения, правильно работающие, когда все входные числа не превосходят 105, будут оцениваться в 40 баллов.ЗамечаниеВ первом примере Аня и Саша сядут на одну сторону, их суммарная масса будет равна 65 кг. На другую сторону сядет Боря, взяв 15-килограммовый камень, тогда масса Бори с камнем составит 55 кг. Разница весов на концах качелей примет значение 10 кг.Во втором примере Аня и Боря сядут на одну сторону (50 кг), Саша на другую сторону (45 кг). Разница весов будет равна 5 кг, поэтому камень не понадобится.Ввод30403510Вывод15Ввод30

Ответ:

Задание 6. Фонари. Вдоль прямой улицы на равном расстоянии располагаются N домов. Будем считать расстояние между домами за единицу длины.Около каждого дома можно поставить один фонарь. Всего имеется A фонарей, которые могут освещать дома на расстоянии X (включительно), и B фонарей, которые могут освещать дома на расстоянии Y (включительно). В частности, при X=0 или Y=0 такой фонарь освещает только тот дом, у которого он установлен.Вам необходимо расставить минимальное число фонарей так, чтобы все дома были освещены. Один дом может быть освещён несколькими фонарями. Освещать участки улицы между домами необязательно.

Формат входных данных. Первая строка входных данных содержит целое число N (1≤N≤105). Следующие четыре строки содержат целые неотрицательные числа A, X, B и Y соответственно, которые не превосходят 105.Формат выходных данныхПрограмма должна вывести столько строк, сколько фонарей необходимо установить. Каждая строка должна содержать два целых числа через пробел координату фонаря и расстояние, которое он освещает (то есть одно из чисел X или Y ). Координаты представляют из себя целые числа от 1 до N, рядом с каждым домом можно поставить только один фонарь.При наличии нескольких правильных ответов можно вывести любой из них. Если ответа не существует, программа должна вывести одно число −1.Система оценкиРешения, правильно работающие при A=0 или B=0, будут оцениваться в 30 баллов.Решения, правильно работающие при A≠0, B≠0, n≤1000, будут оцениваться в 40 баллов.ЗамечаниеВ ответе к первому примеру фонарь у дома 2 освещает также дома 1 и 3, фонарь у дома 5 также дома 3, 4, 6 и 7, а фонарь у дома 9 также дома 8 и 10. В результате все дома освещены. Во втором примере фонарей недостаточно.Ввод103112Вывод2 15 29 1Вывод101112Вывод-1

Ответ:

Задание 7. Деление шоколадки. У Маши есть прямоугольная шоколадка, состоящая из m×nm×n квадратных долек. Маша хочет разделить эту шоколадку между своими друзьями, разломив шоколадку по линиям на k кусочков, то есть каждому другу достанется прямоугольный кусочек шоколадки.У Юры сегодня день рождения, поэтому Маша хочет разделить шоколадку так, чтобы Юре достался самый большой кусок (содержащий как можно больше долек).

Определите число долек в этом куске.

Формат входных данных Программа получает на вход три натуральных числа, каждое в отдельной строке: m, n и k. Все числа целые положительные, при этом mm и nn не превосходят 106, а k≤mn.Обратите внимание на то, что значение mnmn, а значит, и значение k в этой задаче может превышать возможное значение 32‑битной целочисленной переменной, поэтому необходимо использовать 64‑битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).Формат выходных данных Программа должна вывести одно целое число максимально возможное количество долек в том прямоугольном куске, который получит Юра.Система оценки Решения, правильно работающие

Ответ:

9-11 класс

Задание 1: Качели. Трое друзей Аня, Боря и Саша пришли на детскую площадку, чтобы покачаться на качелях‑балансире. Качели представляют собой длинную балку, закреплённую в центре, на которую дети садятся с разных концов.

Массы детей равны A, B и C кг. Чтобы держать баланс на качелях, разница масс на двух концах качелей должна быть не более D кг. Друзьям повезло: рядом с площадкой оказалась груда достаточно тяжёлых камней. Один из детей может взять с собой любой камень, чтобы сделать разность масс на концах качелей допустимой. Помогите друзьям определить минимальную массу камня, благодаря которому они смогут покачаться на качелях.

Формат входных данных. Программа получает на вход три числа A, B, C, записанных в отдельных строках, массы друзей. В четвёртой строке записано число D наибольшая допустимая разница масс на концах качелей. Все числа целые, положительные и не превосходящие 109.Формат выходных данных. Программа должна вывести одно целое число минимально необходимую массу камня, которую нужно добавить на одну из сторон качелей, чтобы друзья смогли покачаться на них, сев оптимально. Если камень им не понадобится, программа должна вывести число 0. Система оценки. Решения, правильно работающие, когда все входные числа не превосходят 105, будут оцениваться в 40 баллов. Замечание. В первом примере Аня и Саша сядут на одну сторону, их суммарная масса будет равна 65 кг. На другую сторону сядет Боря, взяв 15-килограммовый камень, тогда масса Бори с камнем составит 55 кг. Разница весов на концах качелей примет значение 10 кг. Во втором примере Аня и Боря сядут на одну сторону (50 кг), Саша на другую сторону (45 кг). Разница весов будет равна 5 кг, поэтому камень не понадобится.Ввод30403510Вывод15Ввод30204510Вывод0

Ответ:

Задание 2: Фонари. Вдоль прямой улицы на равном расстоянии располагаются N домов. Будем считать расстояние между домами за единицу длины.Около каждого дома можно поставить один фонарь. Всего имеется A фонарей, которые могут освещать дома на расстоянии X (включительно), и B фонарей, которые могут освещать дома на расстоянии Y (включительно). В частности, при X=0 или Y=0 такой фонарь освещает только тот дом, у которого он установлен.

Вам необходимо расставить минимальное число фонарей так, чтобы все дома были освещены. Один дом может быть освещён несколькими фонарями. Освещать участки улицы между домами необязательно.Формат входных данныхПервая строка входных данных содержит целое число N (1≤N≤105). Следующие четыре строки содержат целые неотрицательные числа A, X, B и Y соответственно, которые не превосходят 105.Формат выходных данныхПрограмма должна вывести столько строк, сколько фонарей необходимо установить. Каждая строка должна содержать два целых числа через пробел координату фонаря и расстояние, которое он освещает (то есть одно из чисел X или Y ). Координаты представляют из себя целые числа от 1 до N, рядом с каждым домом можно поставить только один фонарь.При наличии нескольких правильных ответов можно вывести любой из них. Если ответа не существует, программа должна вывести одно число −1.Система оценкиРешения, правильно работающие при A=0 или B=0, будут оцениваться в 30 баллов.Решения, правильно работающие при A≠0, B≠0, n≤1000, будут оцениваться в 40 баллов.ЗамечаниеВ ответе к первому примеру фонарь у дома 2 освещает также дома 1 и 3, фонарь у дома 5 также дома 3, 4, 6 и 7, а фонарь у дома 9 также дома 8 и 10. В результате все дома освещены. Во втором примере фонарей недостаточно.Ввод103112Вывод2 15 29 1Вывод101112Вывод-1

Ответ:

Задание 3: Красная Шапочка на болоте. Красная Шапочка отправилась на болото для сбора клюквы, чтобы испечь пирожки для бабушки. Клюквенное болото представляет собой координатную прямую. Берег, на котором стоит Шапочка, имеет координату 0, а клюквенная поляна координату N+1. В точках с координатами 1, 2, ……, NN расположены кочки.

Первоначально у девочки E единиц энергии. Красная Шапочка может прыгнуть из точки xx в точку y (x<y), потратив на это (y−x) единиц энергии, то есть количество единиц затраченной энергии равно расстоянию между кочками. После того как девочка приземлится на кочке с координатой i, она получает aiai единиц энергии (при этом значение aiai может оказаться отрицательным, тогда энергия Красной Шапочки уменьшится при приземлении). Нельзя, чтобы энергия Красной Шапочки в какой‑либо момент оказалась меньше нуля. Например, Красная Шапочка не может прыгнуть с кочки 1 на кочку 3, имея одну единицу энергии, вне зависимости от того, сколько энергии она получит на 3-й кочке, так как для осуществления такого прыжка необходимо две единицы энергии.Так как Красной Шапочке ещё надо вернуться обратно, девочке интересно, какое максимальное количество энергии у неё может оказаться, когда она достигнет поляны (точки с координатой N+1).Формат входных данных Первая строка входных данных содержит целое число E первоначальный запас энергии Красной Шапочки, 1≤E≤109.Вторая строка входных данных содержит целое число N количество кочек на болоте, 1≤N≤5×105.Следующие N строк содержат по одному целому числу ai энергия, которую получает Красная Шапочка на i-й кочке, −2000≤ai≤2000.Формат выходных данныхПрограмма должна вывести одно число максимальное количество единиц энергии, которое останется у Красной Шапочки после достижения клюквенной поляны. Если девочка не сможет достигнуть цели, выведите одно число «−1» (без кавычек).Система оценкиРешения, правильно работающие при N≤15, будут оцениваться в 20 баллов.Решения, правильно работающие при N≤900, будут оцениваться в 70 баллов.Решения, правильно работающие, когда все ai≥0, будут набирать не менее 20 баллов.ЗамечаниеВ первом примере три кочки и первоначально 2 единицы энергии у Красной Шапочки. Она прыгает на кочку 1, что требует 1 единицу энергии, и у неё остаётся 1 единица энергии. На кочке 1 девочка получает 1 единицу энергии, и у неё становится 2 единицы энергии. Затем она прыгает с кочки 1 на кочку 3, потратив 2 единицы энергии, и у неё становится 0 энергии. Приземлившись на кочку 3, Красная Шапочка получает 1 единицу энергии, этого достаточно, чтобы перепрыгнуть с кочки 3 на поляну в точке 4, после чего у Красной Шапочки останется 0 единиц энергии.Во втором примере у Красной Шапочки первоначально только 1 единица энергии, поэтому она может прыгнуть только на кочку 1, но значение a1=−1, то есть после приземления на кочку 1 у Красной Шапочки энергия станет отрицательной и она не сможет продолжить свой путь.Ввод231-11Вывод0Ввод14-1100-1-1Вывод-1

Ответ:

Задание 4: Деление шоколадки. У Маши есть прямоугольная шоколадка, состоящая из m×nm×n квадратных долек. Маша хочет разделить эту шоколадку между своими друзьями, разломив шоколадку по линиям на k кусочков, то есть каждому другу достанется прямоугольный кусочек шоколадки.У Юры сегодня день рождения, поэтому Маша хочет разделить шоколадку так, чтобы Юре достался самый большой кусок (содержащий как можно больше долек). Определите число долек в этом куске.

Формат входных данных. Программа получает на вход три натуральных числа, каждое в отдельной строке: m, n и k. Все числа целые положительные, при этом mm и nn не превосходят 106, а k≤mn.Обратите внимание на то, что значение mnmn, а значит, и значение k в этой задаче может превышать возможное значение 32‑битной целочисленной переменной, поэтому необходимо использовать 64‑битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).Формат выходных данных Программа должна вывести одно целое число максимально возможное количество долек в том прямоугольном куске, который получит Юра. Система оценки Решения, правильно работающие при m≤1000 и n≤1000, будут оцениваться в 60 баллов. Замечание В примере из условия нужно разделить шоколадку 4×5 на 4 кусочка. Самый большой кусочек будет состоять из 16 долек, как показано на картинке.Ввод 454 Вывод 16

Ответ:

Задание 5: Кодовый замок. В разведывательное управление доставили сейф с секретной информацией, кодовый замок на котором открывается комбинацией из nn цифр, каждая цифра может принимать b различных значений от 0 до b−1. Код неизвестен, однако разведчики передали несколько донесений о том, что сумма цифр кода в некоторых заданных позициях равна какому‑то известному числу. Используя информацию из всех полученных донесений, определите, сколько существует возможных кодов, удовлетворяющих этим условиям.

Формат входных данных Первая строка входных данных содержит число b количество различных значений одной цифры кода, 2≤b≤10.Вторая строка содержит число n количество цифр в коде, n≥1, bn≤60000.Третья строка содержит число t количество имеющихся донесений о сумме каких‑то цифр кода, t≥1.Следующие 2t строк содержат информацию об имеющихся донесениях. Каждое донесение состоит из двух строк. Первая из этих строк («маска цифр») содержит nn символов, записанных слитно и равных «0» или «1», где цифра «1» обозначает, что в донесении говорится об этой цифре кода. Например, маска цифр «01011» означает сумму цифр, стоящих коде на 2-й, 4-й и 5-й позициях. Во второй строке донесения записано число s, равное сумме цифр кода, стоящих на данных позициях.Гарантируется, что каждая маска цифр содержит хотя бы одну единицу и что все маски цифр различаются. Общее число донесений может быть любым, удовлетворяющим этим условиям.Формат выходных данных Программа должна вывести одно целое число количество различных кодов, которые удовлетворяют всем донесениям.Система оценки Решения, правильно работающие, когда n≤4 и каждая маска цифр содержит ровно один символ «1», будут оцениваться в 28 баллов.Решения, правильно работающие, когда n≤4, будут оцениваться в 64 балла. Замечание В примере из условия каждая цифра кода может принимать 8 различных значений от 0 до 7; код состоит из 3 цифр. Получено 2 донесения, из первого донесения известно, что сумма первой и второй цифр кода равна 7, из второго донесения известно, что сумма второй и третьей цифр кода равна 12. Существуют 3 кода, удовлетворяющие этим условиям: «075», «166», «257».Ввод 832110701112 Вывод 3

Ответ:

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

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