Ограничение по времени: 0.5 секунды Ограничение по памяти: 256 мегабайт Михаил Жорданов - тренер школьной секции по стритболу (отличается от классического баскетбола тем, что в…
Ограничение по времени: 0.5 секунды Ограничение по памяти: 256 мегабайт Михаил Жорданов - тренер школьной секции по стритболу (отличается от классического баскетбола тем, что в команде играют 3 человека). На носу городские соревнования, пора составлять команду. У каждого игрока в городе есть свой рейтинг (целое положительное число), и оргкомитет решил ввести для команд одинаковое ограничение - суммарный рейтинг всех игроков должен составить ровно 3. Однако в команде не должно быть трёх игроков с одинаковым рейтингом - иначе комментаторы запутаются во время трансляции. Михаил - гуру тактики. Он всё лето анализировал чемпионские составы за последние годы и сделал ряд наблюдений: в команде должно быть 2 игрока с одинаковым рейтингом, чтобы не было дисбаланса между правым и левым флангами; ни один из игроков команды не должен играть так же или лучше, чем двое других вместе взятых, иначе противник будет атаковать слабых игроков, игнорируя явного лидера. К Жорданову ходит много спортсменов, поэтому он может себе взять любых игроков с любым рейтингом. Но вот проблема - - в таких условиях можно составить не одну, а сразу несколько подходящих команд, и нужно будет выбирать из них оптимальную. Помогите Михаилу разобраться, сколько именно команд можно составить, выполнив регламент соревнований и учитывая его наблюдения. Формат входных данных На вход программе подаётся целое число 8 (1 < s < 1018) — ограничение на суммарный рейтинг игроков в команде. Обратите внимание, что значение з может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#). Формат выходных данных В качестве ответа выведите одно число — количество команд, которые может составить Жорданов, следуя регламенту соревнований и своим тактическим наблюдениям. Система оценки Решения, правильно работающие при 8 ≤ 105 , получат не менее 40 баллов. Замечание Две подходящие команды в тестовом примере - 4, 4, 2 и 3, 3, 4. В качестве неподходящих команд можно привести такие примеры — [1, 1, 8), (2, 2, 6), [4, 5, 1), но на самом деле их гораздо больше. Ввод10 Вывод2
Краткая идея:
- По регламенту команда состоит из трех игроков и должна иметь две равные рейтинги: формируем тройку вида (a, a, b), где a и b — положительные целые, b ≠ a, и сумма 2a + b равна S.
- Дополнительное условие тактики Михаила: ни один игрок не должен играть так же или лучше, чем двое других вместе взятых. Для нашего треугольника это означает, что рейтинг игрока с рейтингом b должен быть меньше суммы рейтингов двух остальных: b < 2a.
- Отсюда:
- b = S - 2a > 0, значит a <= floor((S-1)/2).
- b < 2a => S - 2a < 2a => a > S/4.
- Исключаем случай_ALL равных: b ≠ a, т.е. S ≠ 3a.
- Таким образом, искомые a лежат в диапазоне: a_min = floor(S/4) + 1, a_max = floor((S-1)/2), и исключаем те a, для которых S = 3a (то есть a = S/3, если S делится на 3).
Число таких команд равно:
- N = max(0, a_max - a_min + 1)
- если S % 3 == 0 и a_min <= S/3 <= a_max, то N -= 1
Такой подход работает за константное время и использует 64-битные целые.
Пример:
- S = 10: a_min = floor(10/4)+1 = 2+1 = 3, a_max = floor(9/2) = 4. N = 4-3+1 = 2. S не делится на 3, ответ 2. Совпадает с примером: (3,3,4) и (4,4,2).
Код (C++17, использует long long):
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long s;
if (!(cin >> s)) return 0;
long long amax = (s - 1) / 2; // floor((S-1)/2)
long long amin = s / 4 + 1; // floor(S/4) + 1
long long ans = 0;
if (amax >= amin) {
ans = amax - amin + 1;
if (s % 3 == 0) {
long long t = s / 3;
if (t >= amin && t <= amax) ans--;
}
}
cout << ans << "\n";
return 0;
}
Этот алгоритм корректен для любых S в рамках указанных ограничений и работает за константное время.
