2-й этап Республиканской олимпиады по информатике 2022-2023

Задача B. Сумма, произведение и четыре числа

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Вам даны два целых числа $s$ и $p$. Найдите количество целых положительных четверок, что их сумма не превышает $s$, а произведение не превышает $p$. Формально, в этой задаче вам нужно найти количество таких целых положительных четверок $a, b, c, d$ что выполняются два условия: 1. $a + b + c + d <= s$ 2. $a * b * c * d <= p$

Формат входного файла

В первой строке входных данных даны два целых числа $s$ и $p(1 <= s <= 500, 1 <= p <= 10^9)$.

Формат выходного файла

В единственной строке выведите ответ на задачу.

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

В этой задаче 10 тестов, каждая из них оценивается в 10 баллов:

• Тесты 1-2: Примеры из условия.
• Тесты 3-6: $s <= 100$.
• Тесты 7-10: без дополнительных ограничений.

Примеры:

Вход

5 10

Ответ

5

Вход

10 15

Ответ

125

Замечание

Все подходящие четверки в первом примере: ($1,1,1,1$), ($2,1,1,1$), ($1,2,1,1$), ($1,1,2,1$), ($1,1,1,2$). ( Parassat Kyzyrkanov )

Комментарий/решение

import sys

input=sys.stdin.readline

m=0

a,b=map(int,input().split())

for i in range(1,a+1):

for j in range(1,a+1):

for k in range(1,a+1):

for q in range(1,a+1):

if i+j+k+q<=a and i*j*k*q<=b:

m+=1

print(m)

n,m=map(int,input().split())

z=0;

for i in range(1,n+1):

for j in range(1,n+1):

for k in range(1,n+1):

for w in range(1,n+1):

if i+j+k+w<=n and i*j*k*w<=m:

z+=1;

print(z);

s,p= map(int, input().split())

res=0

for a in range(1,s):

for b in range(1,s):

if a+b>=s or a*b>p:

break

for c in range(1,s):

if a+b+c>=s or a*b*c>p:

break

d=min(s-a-b-c, p//(a*b*c))

res+=d

print(res)

s,p = map(int,input().split())

q = 0

for a in range(1,s+1):

for b in range(1,s+1):

for c in range(1,s+1):

for d in range(1,s+1):

if (a+b+c+d <= s) and (a*b*c*d <= p):

q += 1

print(q)

На 6 баллов:

s,p = map(int,input().split())

count = 0

for i in range(1, s-2):

for j in range(1, s-i-1):

for k in range(1, s-i-j):

for m in range(1, s-i-k):

if i+j+k+m <= s and i*j*k*m <= p:

count += 1

print(count)