Найдите число способов представить число в виде суммы четырех натуральных чисел

@sepul · Регистрация: 12.02.2021

Студворк — интернет-сервис помощи студентам

Сумма - 2

Задано натуральное число x. Найдите число способов представить его в виде суммы четырех натуральных чисел: x = a + b + c + d, где a ≤ b ≤ c ≤ d.

Входные данные
Входной файл INPUT.TXT содержит целое число x (1 ≤ x ≤ 1500).

Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.

№ INPUT OUTPUT
1 3 0
2 5 1

Python
1
2
3
4
5
6
7
8
9
x = int(input())
re = 0
for a in range(1, x - 3):
    for b in range(a, x - 3):
        for c in range(b, x - 3):
            d = x - a - b
            if d >= c:
                re += 1
                print(re)

Не проходит проверку на "https://********/" ЗАДАЧА №398

@Arsegg · 12.02.2021, 22:02

sepul, это задача на комбинаторику. Никакой брутфорс здесь не зайдет, т. к. нужно будет проверить 1500 ^ 4 = 5_062_500_000_000 способов. Как и его оптимизации.

P. S. Предположу, что задача связяна с понятием сочетаний с повторениями...

@codcw · 13.02.2021, 06:54

sepul, нашел два решения на одном запрещённом форуме, попытался адаптировать с какого-то си-подобного языка
первое вроде как рабочее, второе у меня ума не хватает довести до ума

Python
1
2
n=int(input())
print(int((((n+3)*n-9*(n%2))*n+72)/144))

Python
1
2
3
4
5
6
7
8
9
10
11
12
def count(n, k = 4, m = 1):
    if n < m*k:
        return 0
    if k == 1:
        return 1
    s = 0
    i = m
    while i <= n/k:
        i += 1
        s += count(n-i,k-1,i)
    return s
print(count(14))

@Gdez · 13.02.2021, 07:24

sepul, Простым перебором решается

Python
1
2
3
4
5
6
7
8
9
10
x = int(input())
res = 0
a = 1
while 4 * a <= x :
    b = a 
    while 3 * b <= x - a :
        res += (x - a - 3*b + 1) // 2 + (x - a - 3*b + 1) % 2
        b += 1
    a += 1
print(res)

Добавлено через 2 минуты
До х=10000 за 3 сек

@sepul · 13.02.2021, 11:13 **[ТС]**

Спасибо за помощь.

@Catstail · 13.02.2021, 11:59

sepul, тебя print не на месте. Поэтому и не проходит. Попробуй так:

Python
1
2
3
4
5
6
7
8
9
x = int(input())
re = 0
for a in range(1, x):
    for b in range(a, x-1):
        for c in range(b, x-2):
            d = x - a - b
            if d >= c:
                re += 1
print(re)

Новые блоги и статьи Все статьи Все блоги /
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .

@Arsegg 3582 / 2182 / 571 Регистрация: 02.09.2015 Сообщений: 5,510
	12.02.2021, 22:02
	sepul, это задача на комбинаторику. Никакой брутфорс здесь не зайдет, т. к. нужно будет проверить 1500 ^ 4 = 5_062_500_000_000 способов. Как и его оптимизации. P. S. Предположу, что задача связяна с понятием сочетаний с повторениями... 0

@sepul 0 / 0 / 0 Регистрация: 12.02.2021 Сообщений: 20
	13.02.2021, 11:13 [ТС]
	Спасибо за помощь. 0