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

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

Ручка стоила 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))

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

Посередине озера плавает плот, имеющий форму прямоугольника. Стороны плота направлены вдоль параллелей и меридианов. Введём систему координат, в которой ось 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)

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

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

Первая строка входных данных содержит число 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)

Задание 4. «Туристический налог»

Найдите на данной карте гор Авалона туристический маршрут минимальной длины, удовлетворяющий условию наличия подъёма и спуска.

Первая строка входных данных содержит число N – количество точек на карте гор Авалона. Следующие N строк содержат информацию о высоте гор в данных N точках при движении с запада на восток. Все числа натуральные, не превосходящие 105.

Программа должна вывести два числа – номер точки начала маршрута и номер точки окончания маршрута. Точки нумеруются от 1 до N. Если маршрута, удовлетворяющего условиям, не существует, программа должна вывести одно число 0.

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

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

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

Решение

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

Затем найдём максимальное значение высоты на этом участке, для чего понадобится ещё один цикл (в приведённом ниже решении вместо третьего цикла используется функция max для среза списка, то есть для рассматриваемого фрагмента). Если значение максимума на маршруте строго больше значений крайних элементов, то этот маршрут удовлетворяет условию задачи. Осталось только выбрать самый короткий маршрут из таких (то есть маршрут, для которого минимальная разница для индексов конца и начала маршрута). Такое решение имеет алгоритмическую сложность O(N³), то есть время работы такой программы растёт пропорционально N³  и набирает 40 баллов.

Пример решения на языке Python (40 баллов)

n = int(input())
a = [int(input()) for i in range(n)]
ans1 = 0
ans2 = 10 ** 9
for i in range(0, n):
   for j in range(i + 2, n):
       m = max(a[i:j + 1])
       if a[i] < m > a[j] and j - i <= ans2 - ans1:
           ans2 = j
           ans1 = i
if ans2 != 10 ** 9:
   print(ans1 + 1, ans2 + 1)
else:
   print(0)

Для того, чтобы придумать правильное и эффективное решение заметим, что ответ (высоты наилучшего маршрута) всегда имеет вид, как в примере (15, 20, 20, 10) — все значения кроме двух крайних равны, а два крайних меньше их. Иначе можно сократить маршрут, оставив только два крайних значения, меньших наибольшего значения на маршруте. Поэтому можно изучать только последовательности равных идущих подряд элементов массива, среди всех таких последовательностей нужно выбрать последовательность наименьшей длины, причём перед и после этой последовательности должны быть меньшие значения. При этом алгоритм должен иметь сложность O(N), иначе программа также не сможет уложиться в ограничение по времени в 1 секунду.

Решение можно реализовать и без использования массива для хранения всех даннях чисел. Будем считывать числа по одному, при этом будем использовать следущие переменные:

• last_height — значение последнего считанного элемента.
• last_len — количество последних считанных элементов, равных last_height.
• prev_height — значение элемента, который был перед последовательностью последних элементов равных last_height.

Пусть значение нового считанного элемента равно h. Если h = last_height, то новый элемент продолжает последовательность элементов равных last_height, потому увеличим значение last_len на 1. Если же новый элемент неравен last_height, то этот элемент начинает новуй последовательность равных элементов, поэтому запишем его значение в переменную last_height, переменной last_len присвоим значение 1, а старое значение last_height переместится в переменную prev_height. Но сначала проверим, является ли последовательность элементов равных last_height, удовлетворяющей условию задачи, что означает выполнение неравенств prev_height < last_height > h. Если эти неравенства верны, а также если длина последовательности last_len наименьшая (для этого будем также хранить наименьшую известную длину последовательности, удовлетворяющую условию задачи в переменной best_len), то запомним ответ и обновим значение переменной best_len.

Пример решения на языке Python (100 баллов)

n = int(input())
ans1 = 0
ans2 = 0
last_height = 10 ** 9
prev_height = 10 ** 9
last_len = 0
best_len = 10 ** 9
for i in range(1, n + 1):
   h = int(input())
   if h == last_height:
       last_len += 1
   else:
       if prev_height < last_height > h and last_len < best_len:
           best_len = last_len
           ans1 = i - last_len - 1
           ans2 = i
       prev_height = last_height
       last_height = h
       last_len = 1
if ans1 == 0:
   print(0)
else:
   print(ans1, ans2)

Задание 5. Делимость

Сегодня в школе на уроке математики проходят делимость. Чтобы продемонстрировать свойства делимости, учитель выписал на доске все целые числа от 1 до N в несколько групп, при этом если одно число делится на другое, то они обязательно оказались в разных группах. Например, если взять N = 10, то получится 4 группы.

• Первая группа: 1.
• Вторая группа: 2, 7, 9.
• Третья группа: 3, 4, 10.
• Четвёртая группа: 5, 6, 8.

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

Программа получает на вход одно натуральное число N, не превосходящее 109 , и должна вывести одно число – искомое минимальное количество групп.

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

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

• Решение, правильно работающее только для случаев, когда N не превосходит 20, будет оцениваться в 20 баллов.
• Решение, правильно работающее только для случаев, когда N не превосходит 10³, будет оцениваться в 40 баллов.
• Решение, правильно работающее только для случаев, когда N не превосходит 10⁴, будет оцениваться в 60 баллов.

Решение

Решение на 20 баллов можно получить, если разобрать случаи маленьких значений N и для каждого из них посчитать ответ.

Пример решения на языке Python (20 баллов)

n = int(input())
if n == 1:
   print(1)
elif n <= 3:
   print(2)
elif n <= 7:
   print(3)
elif n <= 15:
   print(4)
else:
   print(5)

Для полного решения достаточно заметить, что ответ увеличивается на 1, когда N равно степени двойки: 2, 4, 8, 16 и т. д. Действительно, пусть максимальная степень двойки, не превосходящая числа N, равна 2^k. Тогда ответ будет как минимум равен k + 1, поскольку среди рассматриваемых N чисел есть k + 1 степень двойки, включая 1 = 2⁰, все эти степени двойки делятся друг на друга, поэтому они должны оказаться в разных группах, то есть ответ будет не меньше, чем k + 1. Покажем, что k + 1 группы достаточно, то есть все числа от 1 до N можно разбить на k + 1 группу. Для этого пронумеруем группы от 0 до k и в группу с номером i отнесём числа от 2ⁱ  до 2ⁱ⁺¹-1 (в последнюю группу попадут число от 2^k  до N).

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

Пример решения на языке Python (100 баллов)

n = int(input())
ans = 1
p = 1
while 2 * p <= n:
   p *= 2
   ans += 1
print(ans)

Пример решения на языке С++ (60 баллов)

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<vector<int> > nums;
vector<int> used;
void check(int d)
{
   for (int i = 0; i < nums.size(); ++i)
       if (!used[i] && find(nums[i].begin(),
                            nums[i].end(), d) != nums[i].end())
       {
           used[i] = 1;
           return;
       }
}
int main()
{
   int n;
   cin >> n;
   nums.resize(1);
   nums[0].push_back(1);
   used.resize(1);
   for (int i = 2; i <= n; ++i)
   {
       fill(used.begin(), used.end(), 0);
       for (int d = 1; d * d <= n; ++d)
           if (i % d == 0)
           {
               check(d);
               check(i / d);
           }
       if (find(used.begin(), used.end(), 0) == used.end())
       {
           nums.push_back(vector<int>(1, i));
           used.push_back(0);
       }
   }
   cout << nums.size() << endl;
}

Архив с тестами и решениями жюри