Подразделы

Другие разделы

Дата и время

09/04/2025 07:20:57

Авторизация

Зарегистрироваться
Восстановить пароль

Разбор задачи I. Ксилофон

Тема: вывод формулы
Сложность: средняя

Пусть

$N=1$ . Рассмотрим треугольники с длиной наибольшей стороны равной

$i$ . Длина второй по величине стороны

$j$ может принимать значения от

$|__\ {i+3}/2\ __|$ до

$i-1$ , т.е.

$|__\ {i-2}/2\ __|$ различных значений. Длина самой маленькой стороны может принимать значения от

$i-j+1$ до

$j-1$ , т.е.

$2*j-i-1$ различных значений. Количество возможных треугольников в зависимости от

$j$ является арифметической прогрессией. Чтобы найти сумму, можно воспользоваться формулой из задачи A. Сумма первого и последнего элемента прогрессии равна

$2*|__\ {i-1}/2\ __|$ (в правильности этого результата можно убедиться, взяв для

$i$ какое-то четное и нечетное значение, например, 9 и 10). Таким образом, количество возможных треугольников с длиной наибольшей стороны

$i$ равно

$|__\ {i-2}/2\ __|*|__\ {i-1}/2\ __|$ .

Если

$N>1$ , то часть треугольников исчезает, при этом либо число исчезающих треугольников (для

$N\ ≤\ i/2$ ), либо число оставшихся треугольников (для

$N\ >\ i/2$ ) также является арифметической прогрессией. Например, при

$N\ ≤\ i/2$ из подсчитанного ранее количества треугольников нужно вычесть

${(N-2)*(N-1)}/2$ . Количество возможных треугольников при

$N\ >\ i/2$ определите самостоятельно.

Результат получаем суммированием количеств треугольников по всем

$i$ от

$N+2$ до

$M$ . Результат не превышает

$M^3$ , т.е.

$(10^6)^3=10^18$ , значит для вычислений необходимо использовать тип int64 (long long в C/С++).

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

Разбор задачи I. Ксилофон