Школьный этап Сириус по Информатике вопросы и ответы для 7-8 класса
Ответ
Задание 1. Чаепитие
Слон Семён каждое утро пьёт чай и ест бутерброды с яблочным вареньем. У него есть длинный стол, на котором в ряд слева направо выставлены чашки чая и банки с вареньем и выложен хлеб. Чтобы чаепитие удалось, нужно, чтобы при просмотре слева направо сначала шёл весь хлеб, затем всё варенье, и затем весь чай.
Слон использует хобот для перестановки предметов, поэтому за одну секунду он может поменять местами только два соседних предмета. Обозначим хлеб буквой «Х», варенье буквой «В», чай буквой «Ч». Тогда последовательность предметов на столе задаётся строкой из этих букв. Например, при расстановке предметов «ВЧXВ» на подготовку стола потребуется три секунды. Предметы, которые переставляются местами каждую секунду, подчёркнуты.
1. ВХЧХЧВ
2. ХВХВЧВ
3. ХВВЧВЧ
Слон торопится и поэтому хочет знать, при какой первоначальной расстановке предметов у него уйдёт наибольшее время на подготовку стола.
Запишите последовательность из букв «Х», «В», «Ч» для четырёх случаев. Количество предметов каждого вида вы можете выбрать самостоятельно, но общее число букв в ответе должно соответствовать заданному. Вы должны найти такую расстановку, при которой подготовка стола займёт наибольшее время для данного числа предметов.
Если вы не можете найти ответ для какого‑то случая, запишите любую строку из букв «Х», «В», «Ч» нужной длины.
Ответ:
3 предмета — ЧВХ
9 предметов — ЧЧЧВВВХХХ
11 предметов — ЧЧЧЧВВВВХХХ
13 предметов — ЧЧЧЧЧВВВВХХХХ
Задание 2: Набор на кружки
Учащиеся школы должны выбрать себе дополнительные занятия на год. Каждый из них выбрал как минимум один предмет из предложенных: биологии, музыки и шахмат. Известно, что 150 школьников выбрали биологию, 130 учеников музыку и 100 шахматы, но каждый учащийся мог выбрать и несколько предметов. Ответьте на вопросы. Если вы не можете дать ответ на какой‑то вопрос, запишите в ответе любое число.
1. Какое минимальное количество учащихся могло быть в школе? Ответ = 150
2. Какое максимальное количество учащихся могло быть в школе? Ответ =380
3. Считайте, что одновременно биологию и музыку выбрали 85 учащихся. Сколько школьников выбрало ровно один из этих двух предметов? Ответ = 195
4. Считайте, что ни один школьник не выбрал одновременно биологию и шахматы, одновременно биологию и музыку выбрали 6060 учеников, а всего в школе 250 учащихся. Сколько школьников выбрало и шахматы, и музыку? Ответ = 250
5. Считайте, что в ситуации из пункта 4 на кружки разрешили записываться учащимся других школ. Какое минимальное дополнительное количество школьников должно записаться на предложенные предметы, чтобы количество людей, посещающих только музыку, стало равняться количеству людей, не посещающих её? Ответ = 180
Задание 3. Кратчайший путь
Есть 7 городов, обозначенных буквами английского алфавита A, B, C, D, E, F, G. Вы хотите посетить эти все города ровно по одному разу каждый и вернуться в начальную точку своего путешествия. Для этого вы можете воспользоваться самолётами: между двумя любыми городами есть прямой авиарейс. Стоимость перелёта между парой городов приведена в следующей таблице.
Необходимо построить замкнутый маршрут, проходящий через все города по одному разу, стоимость перелёта по которому была бы минимально возможной.
Расположите города в том порядке, в котором вы будете их посещать. Чем короче будет найденный вами маршрут, тем больше баллов вы получите. Обратите внимание: при расчёте стоимости маршрута также учитывается перелёт из последнего города вашего ответа в первый город.
A
B
C
D
E
F
G
Ответ
А->В->D->E->F->C->G
Задание 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. Качели
Ограничение по времени: 0.5 секунды
Ограничение по памяти: 256 мегабайт
Трое друзей Аня, Боря и Саша пришли на детскую площадку, чтобы покачаться на качелях‑балансире. Качели представляют собой длинную балку, закреплённую в центре, на которую дети садятся с разных концов.
Массы детей равны A, B и C кг. Чтобы держать баланс на качелях, разница масс на двух концах качелей должна быть не более D кг. Друзьям повезло: рядом с площадкой оказалась груда достаточно тяжёлых камней. Один из детей может взять с собой любой камень, чтобы сделать разность масс на концах качелей допустимой. Помогите друзьям определить минимальную массу камня, благодаря которому они смогут покачаться на качелях.
Формат входных данных
Программа получает на вход три числа A, B, C, записанных в отдельных строках, массы друзей. В четвёртой строке записано число D наибольшая допустимая разница масс на концах качелей. Все числа целые, положительные и не превосходящие 109.
Формат выходных данных
Программа должна вывести одно целое число минимально необходимую массу камня, которую нужно добавить на одну из сторон качелей, чтобы друзья смогли покачаться на них, сев оптимально. Если камень им не понадобится, программа должна вывести число 0.
Система оценки
Решения, правильно работающие, когда все входные числа не превосходят 105, будут оцениваться в 40 баллов.
Замечание
В первом примере Аня и Саша сядут на одну сторону, их суммарная масса будет равна 65 кг. На другую сторону сядет Боря, взяв 15-килограммовый камень, тогда масса Бори с камнем составит 55 кг. Разница весов на концах качелей примет значение 10 кг.
Во втором примере Аня и Боря сядут на одну сторону (50 кг), Саша на другую сторону (45 кг). Разница весов будет равна 5 кг, поэтому камень не понадобится.
Ввод
30
40
35
10
Вывод
15
Ввод
30
Задание 6. Фонари
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Вдоль прямой улицы на равном расстоянии располагаются 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. В результате все дома освещены. Во втором примере фонарей недостаточно.
Ввод
10
3
1
1
2
Вывод
2 1
5 2
9 1
Вывод
10
1
1
1
2
Вывод
-1
Задание 7. Деление шоколадки
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
У Маши есть прямоугольная шоколадка, состоящая из 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 долек, как показано на картинке.
Ввод
4
5
4
Вывод
16