Ответы на задания по Олимпиаде «Сириус» Информатика 9-11 класс 4 группа / 27 октября 2023 года

Задание 1: Прямые и окружности

Ограничение по времени: 1 секунда. Ограничение по памяти: 256 мегабайт.

Окончив чертёж и подписав все цифры,Александров со спокойной отчетливостью назвал все линии и все размеры, спрятал мелок в карман и по‑строевому вытянулся,глядя в холодные глаза полковника.Александр Куприн, «Юнкера».Дополнительное задание, полученное Алексеем от строгого учителя, было следующим: требовалось выбрать на плоскости точку и провести через неё n различных прямых. После этого нужно было построить m различных окружностей с центром в отмеченной точке. На сколько частей все линии делят плоскость?

Формат входных данных

Две строки входных данных содержат два неотрицательных целых числа n и m (0 ≤ n, m ≤108).

Формат выходных данных

Выведите одно натуральное число —— ответ на вопрос задачи.Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64‑битный тип данных, например, long в C++, int64 в Free Pascal, long в Java.

Система оценки

Решения, правильно работающие при n=0, будут оцениваться в 20 баллов.Решения, правильно работающие при m=0, будут оцениваться в 20 баллов.

Замечание

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

Ответ:

C++:
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
         long long n, m; cin >> n >> m;
         if (!n) cout << m + 1;
         else cout << max(1ll, 2 * n * (m + 1));
}

Python:
n = int(input())
m = int(input())
if n == 0:
print(m + 1)
else:
print(max(1, 2 * n * (m + 1)))

Задание 2: Братья и сёстры

Рославлев‑младший. Вот неожиданный гость! Это брат мой!Александр Грибоедов, «Кто брат, кто сестра,или Обман за обманом».У Ани братьев в a раз больше, чем сестёр, а у её брата Бори братьев в b раз больше, чем сестёр. Сколько мальчиков и девочек в этой семье?

Формат входных данных

Две строки входных данных содержат два натуральных числа a и b (1≤ a, b ≤109). В этой задаче —— никакого обмана, гарантируется непротиворечивость входных данных.

Формат выходных данных

Выведите в двух строках два натуральных числа —— ответ на вопрос задачи. Первое число —— количество мальчиков, второе —— девочек.Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64‑битный тип данных, например, long в C++, int64 в Free Pascal, long в Java.

Система оценки

Решения, верно работающие при a, b ≤ 100, получат не менее 50 баллов.

Замечание

В примере у Ани братьев в 5 раз больше, чем сестёр, а у её брата Бори братьев в 2 раза больше, чем сестёр. В семье 5 мальчиков и 2 девочки. Проверим: у Ани 1 сестра и 5 братьев (в 5 раз больше), а у Бори 2 сестры и 4 брата (в 2 раза больше).

Ответ:

C++:
#include <iostream>

using namespace std;

int main()
{
   int a, b; cin >> a >> b;
   int x = (a + 1) / (a — b);
   int y = a * (x — 1);
   cout << y << «\n» << x << «\n»;
   return 0;
}

Python:
a = int(input())
b = int(input())
x = (a + 1) // (a — b)
y = a * (x — 1)
print(y)
print(x)

Задание 3: Шестёрки

—— Скажи нам,Сколько шестью шесть?—— Вы погодите,Дайте сесть!Я сразу не соображу!Я посижу, тогда скажуЭмма Мошковская, «Таблица умножения».Шестиклассница Эмма в последнее время увлеклась восточной культурой. Дома она носит ханьфу, старательно выводит кисточкой иероглифы и очень любит цифру шесть, которая в Китае символизирует гармонию и баланс.Сегодня, сидя за обедом, Эмма задумалась о том, что получится, если число, состоящее из одних шестёрок, возвести в квадрат. Помогите ей перемножить эти числа. Поскольку результат может оказаться очень большим, выведите только одну цифру на интересующей девочку позиции.

Формат входных данных

Две строки входных данных содержат два натуральных числа: n —— длина числа, состоящего из одних шестёрок, и k —— интересующая Эмму позиция в квадрате числа (1 ≤ n ≤109, 1 ≤ k ≤ 2×n).

Формат выходных данных

Выведите одну десятичную цифру —— ответ на вопрос задачи.

Система оценки

Решения, верно работающие при n ≤9, получат не менее 50 баллов.

Замечание

В первом примере n=1, в квадрат возводится число, состоящее из одной шестёрки, то есть 6. k=1, девочка хочет узнать первую цифру квадрата этого числа. 62=36, на первой позиции цифра 3.Во втором примере n=2 и k=3. 662=4356, на третьей позиции результата цифра 5.

Ответ:

C++:
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
          int n, k;
          cin >> n;
          cin >> k;
          if (k <= n — 1) cout << 4;
          else if (k == n) cout << 3;
          else if (k < 2 * n) cout << 5;
          else cout << 6;
}

Python:
n = int(input())
k = int(input())
if k <= n — 1:
  print(4)
elif k == n:
  print(3)
elif k < 2 * n:
  print(5)
else:
  print(6)

Задание 4: Награждение участников олимпиады

—— Мы все третье место заняли: и я,и Мишка, и Толька, и Кимка, все‑все.Вовка —— первое, рыжий лягушонок ——второе, а мы, остальные восемнадцать человек, мы заняли третье.Так инструктор сказал!Виктор Драгунский, «Третье местов стиле баттерфляй».

Жюри подводит итоги очередной олимпиады по информатике. В этот раз получилось так, что многие участники набрали одинаковое число баллов. Согласно окончательной таблице результатов, первое место заняли a1 участников, второе место —— a2 участников, …, заключительное n‑е место заняли an участников.Согласно регламенту соревнования, требуется каждого участника наградить призом. Суммарно на все призы в смете олимпиады заложена сумма в P денежных единиц. Жюри хочет, чтобы при покупке призов выполнялись следующие условия:1)1) Всем участникам, занявшим одно и то же место, достанутся одинаковые призы;2)2) Всем участникам, занявшим заключительное n‑е место, достанутся призы стоимостью в 1 денежную единицу;3)3) Разница d между призом участника на i‑м месте и призом участника на i+1‑м месте должна быть одинакова для всех i от 1 до n−1, в том числе может быть и так, что d=0, то есть все участники могут получить одинаковые призы независимо от занятого ими места.Необходимо определить, какую максимальную разницу d жюри может запланировать при этих условиях, не выходя за пределы заложенной в смету суммы P.

Формат входных данных

В первой строке входных данных содержится одно натуральное число n —— количество различных мест, которые заняли участники олимпиады (2≤n≤105). В следующих n строках, по одному в строке, находятся натуральные числа ai —— количество участников, занявших i‑е место (i от 1 до n). Общее количество участников a1+a2+…+an не превосходит 1018, любое ai не менее 1. В последней строке находится натуральное число P —— сумма, заложенная в смете на призы (P≤1018). Гарантируется, что P>a1+a2+…+an, то есть для каждого участника можно купить приз стоимостью как минимум в одну денежную единицу.

Формат выходных данных

Выведите одно неотрицательное целое число —— максимальную разницу d, которую можно запланировать, не выходя за пределы суммы P.Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64‑битный тип данных, например, long в C++, int64 в Free Pascal, long в Java.

Система оценки

Решения, правильно работающие для случаев, в которых P/n не превосходит 106, получат не менее 60 баллов.

Замечание

В примере участники распределились следующим образом:1 место —— 2 участника,2 место —— 1 участник,3 место —— 3 участника,4 место —— 4 участника,5 место —— 2 участника.Если заложить разницу между призами в 4 денежных единицы, то распределение стоимостей призов будет следующим:5 место —— 2 приза по 1 денежной единице,4 место —— 4 приза по 5 денежных единиц,3 место —— 3 приза по 9 денежных единиц,2 место —— 1 приз по 13 денежных единиц,1 место —— 2 приза по 17 денежных единиц.Суммарно на призы будет потрачено 2⋅1+4⋅5+3⋅9+1⋅13+2⋅17=96 денежных единиц, что укладывается в смету в 100100 денежных единиц.Если же заложить разницу между призами в 55 денежных единиц, то потребуется 2⋅1+4⋅6+3⋅11+1⋅16+2⋅21=117 денежных единиц, что превышает сумму, указанную в смете.

Ответ:

C++:
#include <iostream>
#include <vector>

using namespace std;

#define ll long long

int main()
{
ll n; cin >> n;
vector<ll> a(n);
ll sum1 = 0;
ll sum2 = 0;
for (ll i = 0; i < n; ++i) {
cin >> a[i];
sum1 += (n — i — 1) * a[i];
sum2 += a[i];
}
ll p; cin >> p;
p -= sum2;
cout << p / sum1 << «\n»;
return 0;
}

Python:
n = int(input())
a = [0] * n
sum1 = 0
sum2 = 0
for i in range(n):
a[i] = int(input())
sum1 += (n — i — 1) * a[i]
sum2 += a[i]
p = int(input())
p -= sum2
print(p // sum1)

Задание 5:Фермер Джон и древний камень

И редко кто бы мог увидеть Его ночной и тайный путь,Но берегись его обидеть,Случайно как‑нибудь толкнуть.Он скроет жгучую обиду,Глухое бешенство угроз,Он промолчит и будет с виду Недвижен, как простой утес.Николай Гумилёв, «Камень».Фермер Джон получил в наследство поле, на котором с незапамятных времен находится один большой и древний камень. По непонятной для самого себя причине Джон боится приближаться к камню, не говоря уже о том, чтобы сдвинуть или избавиться от него. Фермер разбил всё свое поле, которое представляет собой прямоугольник n×m метров, сеткой на квадраты со стороной один метр. Камень занимает ровно один такой единичный квадрат. Камень находится в строке номер x и столбце номер y.Техника Джона может обработать только прямоугольный участок земли, стороны которого имеют целочисленные значения в метрах и на котором не располагается этот камень. Теперь Джон хочет узнать, сколькими способами он может засеять прямоугольник с расположенными на сетке сторонами, такой, что внутри этого прямоугольника не содержится древний камень.

Формат входных данных

На вход подаются четыре натуральных числа n, m, x, y, каждое в отдельной строке. 1≤n, m≤31622, 1≤x≤n1, 1≤y≤m1.

Формат выходных данных

Выведите одно неотрицательное целое число —— количество способов выделить на поле один прямоугольный участок земли со сторонами, расположенными на сетке, и не содержащий внутри квадрат с камнем. Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64‑битный тип данных, например, long long в C++, int64 в Free Pascal, long в Java.

Система оценки

Решения, верно работающие при n, m≤30, получат не менее 20 баллов.Решения, верно работающие при n, m≤300, получат не менее 40 баллов.Решения, верно работающие при n, m≤3000, получат не менее 60 баллов.

Ответ: