Задача: Как много
Дано два числа S(1 < S < 100) и X(1 < > < 100000).
Необходимо найти число троек неотрицательных чисел (a, b, c), таких что a + b + c < S и одновременно abc < Х.
Формат входных данных
В первой строке записано одно целое число Т(1 < T < 10) — количество тестов.
В следующих Т строках даны по два целых числа S(1 < S < 100) и X(1 < > < 100000).
Формат выходных данных
Выведите Т строк — в і-й строке ответ на і-й тест.
1 Ответ
Проверка на примере:
Для S=3, X=10:
a=0, b=0: +4
a=0, b=1: +3
a=0, b=2: +2
a=0, b=3: +1
a=1, b=0: +3
a=1, b=1: +2 (так как 1*1=1<=10, max_c=min(1,10)=1 -> 2 значения)
a=1, b=2: здесь a*b=2<=10, max_c=min(0,5)=0 -> +1 (только c=0)
a=2, b=0: +2 (S-a-b=1, so 2 values? wait: для a=2, b=0: сумма a+b=2, so c от 0 до 1 -> 2 значения)
a=2, b=1: a*b=2<=10, max_c=min(0,5)=0 -> +1
a=3, b=0: +1
Итого: 4+3+2+1+3+2+1+2+1+1 = 20. Совпадает.
Краткое объяснение:
Читаем все входные данные
Для каждого теста перебираем возможные значения a и b
Для каждой пары (a, b) вычисляем сколько допустимых значений c:
Если a или b равно 0 — все значения c подходят
Если произведение a*b превышает X — только c=0
Иначе считаем допустимые c до минимума из оставшейся суммы и максимального значения по произведению
