Как ускорить данный код?

[andr2004]

Я новичок в питоне, изучаю его по курсам. Проходим вложенные циклы. Решение не проходит по времени по 3 тестам(не знаю каким, но с какими-то большими числами). Помогите пожалуйста минимизировать количество вариантов и условий.
Для заданного натурального числа n найти все тройки натуральных чисел a, b, c таких, что a + b + c = n и a ≤ b ≤ c. Минимизируйте количество условий, которые используются в программе.
Входные данные
На вход программе подается натуральное число n <= 100 000.
Выходные данные
Выведите количество искомых троек.

n = int(input())
s = 0
for a in range(1, n - 1):
    for b in range(a, n - a):
        if b <= n - a - b:
            s += 1
print(s)

OC: Windows
Python 3.7

 

[stud_55]

n = int(input())
s = 0
for a in range(1, n // 3 + 1):
    for b in range(a, (n - a) // 2 + 1):
        s += 1
print(s)

На данный момент это.
В вопросах к задаче нашёл такое пояснение:
Формулу решения можно найти аналитически и свести задачу к вычислению арифметического выражения.
По условию нужно минимизировать число условий в программе. В формуле их не будет совсем.
Думаю

Вот так немного быстрее:

n = int(input())
s = 0
for a in range(1, n // 3 + 1):
    s += len([b for b in range(a, (n - a) // 2 + 1)])
print(s)

А вот так гораздо быстрее:

n = int(input())
s = 0
for a in range(1, n // 3 + 1):
    s += ((n - a) // 2 + 1 - a)

print(s)

 

[stud_55]

К сожалению Ваш код проходит ещё меньше тестов и выдаёт неправильный ответ.Скорее в сего это происходит из-за того, что в Вашем коде не проверяется с >= b.

Я забыл про условие a ≤ b ≤ c. Насчет ускорения - можно срезать лишние итерации цикла, которые не проходят по условию
if b <= n - a - b:

n = int(input())
s = 0
for a in range(1, n - 1):
    for b in range(a, n - a):
        if b <= n - a - b:
            s += 1
        else:
            break
print(s)

 

[stud_55]

Возможно не проходит тесты потому что находит не все комбинации. Вот такой вариант находит больше комбинаций:

n = int(input())
s = 0
for a in range(n - 1, 0, -1):
    for b in range(n - a, a, -1):
        if a + b < n:
            s += 1
print(s)

 

[andr2004]

Возможно не проходит тесты потому что находит не все комбинации. Вот такой вариант находит больше комбинаций:

n = int(input())
s = 0
for a in range(n - 1, 0, -1):
    for b in range(n - a, a, -1):
        if a + b < n:
            s += 1
print(s)

К сожалению Ваш код проходит ещё меньше тестов и выдаёт неправильный ответ.Скорее в сего это происходит из-за того, что в Вашем коде не проверяется с >= b.

 

[andr2004]

Я забыл про условие a ≤ b ≤ c. Насчет ускорения - можно срезать лишние итерации цикла, которые не проходят по условию
if b <= n - a - b:

n = int(input())
s = 0
for a in range(1, n - 1):
    for b in range(a, n - a):
        if b <= n - a - b:
            s += 1
        else:
            break
print(s)

Тесты по времени всё равно не проходятся, но программа работает быстрее чем моя.

 

[Rud356]

Какой в принципе лимит по времени исполнения стоит, вот в чем вопрос?

 

[andr2004]

Какой в принципе лимит по времени исполнения стоит, вот в чем вопрос?

Как я понял, максимальное время работы 0.099 сек

 

[Rud356]

Вообще в лоб мы тут подумали и с такими значениями не решится задачка, но может оно и не надо? Возможно тут надо смотреть в сторону комбинаторики и посмотреть то, какие варианты вообще есть для решения скажем для первого числа c, поскольку оно должно быть наибольшим. Так же C может быть числом n целиком, а остальные два нулями. Так же можно вычитать из числа C числа и раскидывать по разному их на оставшиеся два, опять же включая ноль и исключая варианты где a>b. Может если собрать какие-то формулы получится, то отпишись.

 

[andr2004]

Вообще в лоб мы тут подумали и с такими значениями не решится задачка, но может оно и не надо? Возможно тут надо смотреть в сторону комбинаторики и посмотреть то, какие варианты вообще есть для решения скажем для первого числа c, поскольку оно должно быть наибольшим. Так же C может быть числом n целиком, а остальные два нулями. Так же можно вычитать из числа C числа и раскидывать по разному их на оставшиеся два, опять же включая ноль и исключая варианты где a>b. Может если собрать какие-то формулы получится, то отпишись.

Ну варианты, что несколько из чисел равны нулю сразу можно отмести,т.к. числа натуральные.Спасибо Вам за советы попробую "добить" задачку)

 

[andr2004]

n = int(input())
s = 0
for a in range(1, n // 3 + 1):
    for b in range(a, (n - a) // 2 + 1):
        s += 1
print(s)

На данный момент это.
В вопросах к задаче нашёл такое пояснение:
Формулу решения можно найти аналитически и свести задачу к вычислению арифметического выражения.
По условию нужно минимизировать число условий в программе. В формуле их не будет совсем.
Думаю

 

[andr2004]

Вот так немного быстрее:

n = int(input())
s = 0
for a in range(1, n // 3 + 1):
    s += len([b for b in range(a, (n - a) // 2 + 1)])
print(s)

А вот так гораздо быстрее:

n = int(input())
s = 0
for a in range(1, n // 3 + 1):
    s += ((n - a) // 2 + 1 - a)

print(s)

Огромное спасибо!!!!Сидел,думал над ней целую неделю. Я думаю,пока просто мне не хватает практики.Ещё раз спасибо!!

 

[andr2004]

Вот так немного быстрее:

n = int(input())
s = 0
for a in range(1, n // 3 + 1):
    s += len([b for b in range(a, (n - a) // 2 + 1)])
print(s)

А вот так гораздо быстрее:

n = int(input())
s = 0
for a in range(1, n // 3 + 1):
    s += ((n - a) // 2 + 1 - a)

print(s)

В последней строчке (n - a) // 2 + 1 - это количество вариантов b,далле вычитаем а для того,чтобы исключить из подсчёта варианты где а>b.Правильно ли я разобрался?

 

[stud_55]

В последней строчке (n - a) // 2 + 1 - это количество вариантов b,далле вычитаем а для того,чтобы исключить из подсчёта варианты где а>b.Правильно ли я разобрался?

Правильно

 

[andr2004]

Правильно

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