Информатика 7-8 класс, школьный (I) этап, г. Москва, 2016 год

Задание 1. «Из Петербурга в Москву»

Из Москвы в Санкт-Петербург выезжает пассажирский поезд, который движется со скоростью v км/ч. Одновременно из Санкт-Петербурга в Москву отправляется скоростной поезд «Сапсан», который движется со скоростью w км/ч. Расстояние от Москвы до Санкт-Петербурга равно s км. Определите, какое расстояние проедет «Сапсан» до встречи с пассажирским поездом. Считайте, что скорости движения поездов постоянные, временем остановок следует пренебречь.

Ответом на эту задачу является некоторое выражение, которое может содержать целые числа, переменные v, w и s (записываемые английскими буквами), операции сложения (обозначается «+»), вычитания (обозначается «−»), умножения (обозначается «*»), деления (обозначается «/») и круглые скобки для изменения порядка действий. Запись вида «2s» для обозначения произведения числа 2 и переменной s неверная, нужно писать «2 * s».

Пример правильного (по форме записи) выражения: v + (s − w) * 2.

Решение

Поезда сближаются со скоростью v + w и встретятся через время s / (v + w). «Сапсан» за это время пройдёт расстояние w * s / (v + w).

Ответ: w * s / (v + w).

Задание 2. «Упорядочите список»

Дан список чисел: 3, 7, 1, 6, 2, 4, 8, 5.

Разрешается за одну операцию поменять местами два любых числа в этом списке.

Например, если поменять местами числа 6 и 8, то получится список 3, 7, 1, 8, 2, 4, 6, 5.

Упорядочите этот список по возрастанию, то есть получите из него список 1, 2, 3, 4, 5, 6, 7, 8, используя минимальное число обменов.

Решение этой задачи нужно записать в виде последовательности обменов, каждый обмен записывается в одной строке. Один обмен записывается в виде двух различных чисел от 1 до 8, которые нужно поменять местами, записанных через пробел (пример: 6 8).

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

Решение

Наилучшее решение содержит пять обменов:

Задание 3. «Ремонт моста»

Мост через реку стоит на 15 опорах, обозначим их буквами латинского алфавита от A до O. Необходимо произвести ремонт опор моста, при разработке проекта ремонта была определена стоимость ремонта каждой опоры.

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

1. Крайние опоры (A и O) должны быть отремонтированы.
2. Не должно остаться двух стоящих рядом неотремонтированных опор.

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

Решение этой задачи нужно записать в виде перечисления букв, соответствующих опорам моста, которые нужно отремонтировать. Буквы нужно записывать в алфавитном порядке, каждая буква в ответе может встречаться не более одного раза. Например, ответ ABCDEFGHIJKLMNO будет обозначать, что все опоры моста будут отремонтированы, но этот ответ, очевидно, не будет наилучшим. Чем меньше будет стоимость предложенного вами ремонта, тем больше баллов вы получите (при условии, что предложенный план ремонта является надёжным).

Решение

Наилучшее решение: ABDFHJLNO. Стоимость такого решения 170.

Задание 4. «Строительство»

Три мальчика – Боря, Коля и Слава – хотят помочь малышам построить замок из кубиков трёх цветов: белого, красного и синего. Замок имеет три башни, каждая башня будет состоять из пяти кубиков и должна иметь следующий вид (Б – белый кубик, К – красный, С – синий).

За одну секунду каждый мальчик может поставить кубик наверх одной из башни (в самом начале башни не содержат кубиков). При этом Боря использует кубики белого цвета,

Коля – красного цвета, а Слава – синего. Два мальчика не могут одновременно ставить кубики в одну и ту же башню.

Составьте алгоритм действий мальчиков, при котором они построят замок за наименьшее время.

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

Бори, второй символ – действие Коли, третий символ – действие Славы. Действие может быть одним из трёх чисел «1», «2», «3», что означает, что мальчик ставит свой кубик в башню с соответствующим номером, если же мальчик в эту секунду ничего не делает, то вместо числа нужно написать символ «−». Например, строка «3−2» означает, что Боря ставит белый кубик в башню 3, Коля ничего не делает, а Слава ставит синий кубик в башню 2.

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

Решение

Наилучшее решение возможно за 6 секунд.

312

2-3

132

132

12-

-31

Задание 5. «Покупка»

Ручка стоила K рублей. Первого сентября стоимость ручки увеличилась ровно на P процентов. Определите, сколько ручек можно купить на S рублей после подорожания.

Программа получает на вход три целых положительных числа. Первое число K – стоимость ручки в рублях до подорожания. Второе число P – величина подорожания ручки в процентах. Третье число S – имеющаяся сумма денег. Числа K и S не превосходят 107, число P не превосходит 100.

Пример входных и выходных данных

Система оценивания

Решение, правильно работающее только для случаев, когда числа K и S не превосходят 100, будет оцениваться в 6 баллов.

Решение

Посчитаем стоимость ручки в копейках после подорожания — она будет равна K * 100 + K * P (один процент стоимости ручки составляет K копеек). Затем переведем S рублей в копейки (умножив на 100) и поделим нацело на стоимость ручки после подорожания.

Пример решения на языке Python

k = int(input())

p = int(input())

s = int(input())

k = 100 * k + p * k

print(100 * s // k)

Пример решения с использованием действительных чисел (7 баллов)

k = float(input())

p = int(input())

s = int(input())

k = k + k * p / 100

print(int(s / k))

Задание 6. «Плот»

Посередине озера плавает плот, имеющий форму прямоугольника. Стороны плота направлены вдоль параллелей и меридианов. Введём систему координат, в которой ось OX направлена на восток, а ось ОY – на север. Пусть юго-западный угол плота имеет координаты (x₁, y₁), северо-восточный угол – координаты (x₂, y₂).

Пловец находится в точке с координатами (x, y). Определите, к какой стороне плота (северной, южной, западной или восточной) или к какому углу плота (северо-западному, северо-восточному, юго-западному, юго-восточному) пловцу нужно плыть, чтобы как можно скорее добраться до плота.

Программа получает на вход шесть чисел в следующем порядке: x₁, y₁ (координаты юго-западного угла плота), x₂, y₂ (координаты северо-восточного угла плота), x, y (координаты пловца). Все числа целые и по модулю не превосходят 100. Гарантируется, что

x₁ < x₂, y₁ < y₂, x ≠ x₁, x ≠ x₂, y ≠ y₁, y ≠ y₂,

координаты пловца находятся вне плота.

Если пловцу следует плыть к северной стороне плота, программа должна вывести символ «N», к южной – символ «S», к западной – символ «W», к восточной – символ «E». Если плову следует плыть к углу плота, нужно вывести одну из следующих строк: «NW», «NE», «SW», «SE».

Пример входных и выходных данных

Система оценивания

• Решение, правильно работающее для случаев, когда ответом является одна из сторон плота «N», «S», «W», «E», будет оцениваться в 6 баллов.
• Решение, правильно работающее для случаев, когда ответом является один из углов «NW», «NE», «SW», «SE», будет оцениваться в 4 балла.

Решение

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

Например, программа должна вывести NE при условиях x > x₂ и y > y₂, вывести N при условиях  y > y₂ и x₁ < x < x₂ и т. д. Необходимо аккуратно разобрать все случаи.

Пример решения на языке Python

x1 = int(input())
y1 = int(input())
x2 = int(input())
y2 = int(input())
x = int(input())
y = int(input())
if x > x2 and y > y2:
 print("NE")
elif x > x2 and y < y1:
 print("SE")
elif x < x1 and y < y1:
 print("SW")
elif x < x1 and y > y2:
 print("NW")
elif y > y2:
 print("N")
elif y < y1:
 print("S")
elif x > x2:
 print("E")
else:
 print("W")

Пример решения на языке Python

x1 = int(input())
y1 = int(input())
x2 = int(input())
y2 = int(input())
x = int(input())
y = int(input())
ans = ""
if y > y2:
 ans += "N"
if y < y1:
 ans += "S"
if x < x1:
 ans += "W"
if x > x2:
 ans += "E"
print(ans)

Задание 7. «Пакуем чемоданы!»

Определите вес рюкзака и чемодана после того, как Алёна сложит все вещи.

Первая строка входных данных содержит число S – максимально разрешённый вес рюкзака. Во второй строке входных данных записано число N – количество предметов.

В следующих N строках даны массы предметов, сами предметы перечислены в порядке убывания ценности (сначала указана масса самого ценного предмета, затем масса второго по ценности предмета и т. д.). Все числа натуральные, число S не превосходит  2×109, сумма весов всех предметов также не превосходит 2×109. Значение N не превосходит 105

Программа должна вывести два числа – вес рюкзака и вес чемодана (вес пустого рюкзака и чемодана не учитывается).

Пример входных и выходных данных

Система оценивания

Решение, правильно работающее только для случаев, когда все входные числа не превосходят 100, будет оцениваться в 4 балла.

Решение

Эта задача оказалась самой простой для большинства участников. Действительно, в этой задаче нет ни «подводных камней», как в первой задаче, ни объёмного разбора случаев, как во второй задаче. Необходимо просто реализовать тот алгоритм, который описан в условии: завести две переменные для хранения массы рюкзака и массы чемодана, считывать очередное число и прибавлять его либо к массе рюкзака, либо к массе чемодана, следя за тем, чтобы масса чемодана не превышала значения S.

Пример решения на языке Python

s = int(input())
n = int(input())
s1 = 0
s2 = 0
for i in range(n):
   a = int(input())
   if s1 + a <= s:
       s1 += a
   else:
       s2 += a
print(s1, s2)

Файлы с примерами