1 Востаннє редагувалося Eff1c (01.05.2020 15:58:56)

Тема: завдання 1250 e-olymp

https://www.e-olymp.com/uk/problems/1250
Код працює з тестовими даними, але при компіляції сайтом видає "Помилка виконання" до всіх тестів (тобто помилка в компіляції, а не в відповіді).

def main():
    max_n = max(arr_2)  # максимальний індекс
    arr_f = [1, 1]  # масив чисел Фібоначчі
    a = 1
    b = 1
    for _ in range(max_n+1):  # заповнюємо масив, до максимального індексу
        a, b = b, a + b
        arr_f.append(b)

    for el in arr:  # перебираєм пари вхідних даних
        out = arr_f[el[0]:el[1]+1]  # вибираєм потрібні елементи (від першого індекса з пари до другого)
        print(str(sum(out))[-9:])  # сумуєм вибраний відрізок масиву і обрізаємо до 9ти останніх елементів

def add_to_arr(n):
    try:
        arr_2.append(n[1])  # вибираєм тільки з другого індексу пари
        # якщо вхідні дані не будуть введені - перейде до except завершить цикл while 
        arr.append(n)
        return True
    except:
        return False

arr = []  # масив для вхідних даних (пар з значенням початкового і кінцевого індексу)
arr_2 = []  # масив для вибору найбільшого індексу
while add_to_arr(list(map(int, input().split()))):
    pass

main()

2

Re: завдання 1250 e-olymp

Перед програмуванням треба зробити математику. Знайдіть формулу для суми перших N чисел Фібоначчі. Це не так складно - просто виведіть перші 10 сум, ви маєте побачити, в чому тут справа. Якщо ні - виведіть числа Фібоначчі з відповідними номерами поруч. Сума від a-го до b-го легко знаходиться як різниця сум перших b і перших a-1 чисел Фібоначчі.
Залишок знаходиться оператором %, а не цими фокусами з останніми символами стрічки.

Ну і підозрюю, що вони примудрилися додати код з якоюсь функцією, мабуть, main, до вашого, звідки й помилка. Перейменуюйте main на щось інше.

Подякували: Eff1c1

3

Re: завдання 1250 e-olymp

Хоча не виключено, що ви вичерпуєте пам'ять. Знову ж таки, зробіть математику.

Подякували: Eff1c1

4

Re: завдання 1250 e-olymp

Гм. У мене те саме - помилки виконання. Схоже, проблема на їхньому боці.

Подякували: Eff1c1

5

Re: завдання 1250 e-olymp

koala написав:

Хоча не виключено, що ви вичерпуєте пам'ять

Там є окремий лічильник на пам'ять. Показує, що використав тільки 5 з 128 MiB.
Я зрозумів про яку ви формулу, але не зрозумів як її застосувати, якщо a не перший елемент послідовності.

koala написав:

Сума від a-го до b-го легко знаходиться як різниця сум перших b і перших a-1 чисел Фібоначчі

Не зрозумів що ви мали на увазі. Можна в вигляді формули?

6 Востаннє редагувалося koala (02.05.2020 12:49:31)

Re: завдання 1250 e-olymp

Це загальний метод. Нехай ми маємо послідовність A(n), для якої відомо формулу суми S(n)=A(0)+A(1)+...+A(n). Як знайти суму членів послідовності від A(a) до A(b)? Подивимося:
S(b)=A(0)+A(1)+...+A(a-1)+A(a)+A(a+1)...+A(b)
S(a)=A(0)+A(1)+...+A(a-1)+A(a)
Бачите? S(b) на початку складається з елементів S(a). Тільки A(a) має входити в результат, тому візьмемо знизу A(a-1) і віднімемо:

 S(b)       = A(0)+A(1)+...+A(a-1)+A(a)+A(a+1)...+A(b)
-
 S(a-1)     = A(0)+A(1)+...+A(a-1)
------------------------------------------------
S(b)-S(a-1) =                      A(a)+A(a+1)...+A(b)

Ось і вся формула.

Подякували: Eff1c, leofun012

7

Re: завдання 1250 e-olymp

koala написав:

Це загальний метод. Нехай ми маємо послідовність A(n), для якої відомо формулу суми S(n)=A(0)+A(1)+...+A(n). Як знайти суму членів послідовності від A(a) до A(b)? Подивимося:
S(b)=A(0)+A(1)+...+A(a-1)+A(a)+A(a+1)...+A(b)
S(a)=A(0)+A(1)+...+A(a-1)+A(a)
Бачите? S(b) на початку складається з елементів S(a). Тільки A(a) має входити в результат, тому візьмемо знизу A(a-1) і віднімемо:

 S(b)       = A(0)+A(1)+...+A(a-1)+A(a)+A(a+1)...+A(b)
-
 S(a-1)     = A(0)+A(1)+...+A(a-1)
------------------------------------------------
S(b)-S(a-1) =                      A(a)+A(a+1)...+A(b)

Ось і вся формула.

Ну ок
Але хіба це не та ж реалізація

sum(arr[a:b])

?

Прихований текст

В моєму випадку

sum(arr_f[el[0]:el[1]+1])

8

Re: завдання 1250 e-olymp

Ні, звісно. Бо нам відомо формулу суми S(n) - а отже, можна знайти і S(b)-S(a-1).
Може, ви не зрозуміли, про яку я формулу казав?

Подякували: Eff1c1