Вопросы по олимпиаде

[FsGaCh]

Назовем число "зеркально простым", если само число является простым, и простым является число, записанное теми же цифрами в обратном порядке.
Найти количество "зеркально простых" чисел на промежутке от a до b.

Входные данные:
Два числа a и b (1 ≤ a, b ≤ 10000).

Выходные данные:
Вывести количество "зеркально простых" чисел на промежутке от a до b включительно.

Мой вариант, если возможно, скажите как можно упростить:

ab = input().split()
a = int(ab[0])
b = int(ab[1])
t = 0
am = 0
count = 0
if a <= 10000 and a >= 1 and b <= 10000 and b >= 1 and a < b:
    for i in range(a, b):
        a = int(str(i)[::-1])
        t = 0
        d1 = []
        d2 = []
        for k in range(1, i + 1):
            if i % k == 0:
                d1.append(k)
        if len(d1) == 2:
            t += 1
        for k in range(1, a + 1):
            if a % k == 0:
                d2.append(k)
        if len(d2) == 2:
            t += 1
        if t == 2:
            count += 1
print(count)

[FsGaCh]

Разрежьте отрезок длинной L на наибольшее количество частей, длины которых - натуральные числа, чтобы из них невозможно было сложить ни одного треугольника.

Входные данные:
Длина отрезка L (4 ≤ L ≤ 2∙10^9).

Выходные данные:
Искомое количество частей.

Я не понял что тут от меня нужно. Если я правильно понимаю, ВСЕГДА у треугольника 3 стороны, то и отрезков максимум будет 3. Поэтому и сделал вот так :

#Длины одной строноы треугольника всегда должна быть меньше суммы других сторон
L = input()
if L >= 4 and L <= 2*(10**9):
    print(3)

[evg_m]

берем отрезок длины 4. его можно...
1. ... разрезать на 4 части (1+1+1+1) взять из них 3 и сложить равносторонний треугольник.
2. ... разрезать на 3 части (2+1+1) и попробуйте сложить треугольник теперь.

надо разрезать на как можно большее число частей НО так чтобы не нашлось трех деталей из которых получился бы треугольник.
в первом примере максимально возможное число частей, но увы... из них получился треугольник.

[BDA]

Про бутылки воды. Во-первых, лучше оставаться в целых числах (то есть домножить N на 10, делить на 12). Во-вторых, в цикле нет компенсации за продажу бутылок. В-третьих, можно вывести формулу:

print((10 * int(input()) - 2) // 10)

[ViktorR]

Назовем число "зеркально простым"

Пишем функцию для проверки числа на простоту и прогоняем все числа из диапазона.
Проверка на простоту - отсутствие делителей.
В цикле проверяем остаток. Если ноль - break.

PS: для проверки числа на простоту достаточно искать делители от 2 до sqrt(N)
Это существенно ускоряет вычисления.

[FsGaCh]

Сообщение от BDA

Про бутылки воды. Во-первых, лучше оставаться в целых числах (то есть домножить N на 10, делить на 12). Во-вторых, в цикле нет компенсации за продажу бутылок. В-третьих, можно вывести формулу:

print((10 * int(input()) - 2) // 10)

Если коротко, то просто надо вычитать 1 из вводных данных? Какие данные не вводил, выводит именно так. Ввожу 0, выводит -1.
Если так, то думаю формулу можно изменить так:

print(int(input()) - 1)

[BDA]

Да, пожалуй, для натуральных N можно и так считать.

[FsGaCh]

Сообщение от FsGaCh

Тогда если правильной понимаю, всгда будет выводить 3? Я думал что если разрезать на 4 частей, тогда не получится создать треугольник, потому что тогда это будет 4 стороны, а это не треугольник. И на 2 части разрезать не получится, потому что получится фигура с двумя сторонами, а это уже точно не треугольник....

Сообщение от evg_m

берем отрезок длины 4. его можно...
1. ... разрезать на 4 части (1+1+1+1) взять из них 3 и сложить равносторонний треугольник.
2. ... разрезать на 3 части (2+1+1) и попробуйте сложить треугольник теперь.

надо разрезать на как можно большее число частей НО так чтобы не нашлось трех деталей из которых получился бы треугольник.
в первом примере максимально возможное число частей, но увы... из них получился треугольник.

Тогда если правильно понимаю, всгда будет выводить 3? Я думал что если разрезать на 4 части, тогда не получится создать треугольник, потому что будут 4 стороны, а это не треугольник. И на 2 части разрезать не получится, потому что получится фигура с двумя сторонами, а это уже точно не треугольник....

[BDA]

Нет. Вот есть отрезок. Его порезали на какие-то кусочки. Потом берутся любые 3 кусочка, и из них пытаются сложить треугольник. Если получилось сложить, то такая нарезка не подходит. Если разрезать только на 2 кусочка, то не из чего будет в принципе сложить треугольник. Но требуется нарезать на максимально возможное количество кусочков. Пример уважаемого evg_m навел меня на мысль, что ответом является количество элементов последовательности Фибоначчи, сумма которых не превосходит требуемой длины отрезка.

[FsGaCh]

Сообщение от BDA

Нет. Вот есть отрезок. Его порезали на какие-то кусочки. Потом берутся любые 3 кусочка, и из них пытаются сложить треугольник. Если получилось сложить, то такая нарезка не подходит. Если разрезать только на 2 кусочка, то не из чего будет в принципе сложить треугольник. Но требуется нарезать на максимально возможное количество кусочков. Пример уважаемого evg_m навел меня на мысль, что ответом является количество элементов последовательности Фибоначчи, сумма которых не превосходит требуемой длины отрезка.

Как-то так?

n = int(input())
a = 1
b = 1
c = 2
count = 0
while c <= n:
    c = a + b
    a = b
    b = c
    count += 1
print(count)