Python динамическое программирование (list assignment index out of range). Что делать?

@Maxim1704g · Регистрация: 25.08.2018

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

Добрый день! Решаю следующую задачу:
Миша, Маша и Филипп очень любят пить чай. Они решили устроить чайный марафон, и пить только его.

В нулевой день Миша выпил a0 кружек чая, Маша выпила b0 кружек чая, а Филипп — c0 кружек чая. В каждый следующих каждый из них пил столько чая, сколько выпили другие в предыдущий день. То есть Миша в первый день выпил a1=b0+c0 кружек чая, Маша выпила b1=a0+c0 кружек чая, а Филипп выпил c1=a0+b0 кружек чая. Так же проходило в следующие дни, и если обозначить за ai, bi и ci число выпитого чая в день i Мишей, Машей и Филиппом, то ai=bi−1+ci−1, bi=ai−1+ci−1 и ci=ai−1+bi−1.

От такого числа выпитого чая все совсем посчитали счет числа кружек. Теперь Мише и Маше интересно, чему равна разность выпитого чая в n-й день между ними, то есть значение разности an−bn.

Формат входных данных
Единственная строка содержит четыре целых числа a0, b0, c0 и n (0⩽a0,b0,c0,n⩽1018) — число выпитого чая в нулевой день Мишей, Машей и Филиппом, а так же день, про который надо узнать ответ.

Формат выходных данных
В единственной строке выведите одно число — разность числа выпитых кружек чая у Миши и Маши в n-й день. Обратите внимание, что дни нумеруются с нуля.

Пояснение к примерам
В первом примере в первый день Миша выпил 1+0=1 кружку чая, Маша выпила 2+0=2 кружки чая, а Филипп выпил 1+2=3 кружки чая. Во второй день Миша выпил 2+3=5 кружек чая, Маша выпила 1+3=4 кружки чая, а Филипп выпил 1+2=3 кружки чая. Итого разность равна 1.

Во втором примере в первый день Миша выпил 6 кружек чая, Маша выпила 8 кружек чая, а Филипп выпил 4 кружки чая. Итого разность равна −2.

Ввод 2 1 0 2
Вывод 1
________________________________________ _______
Ввод 3 1 5 1
Вывод -2

Мой код выдаёт ошибку:
**list assignment index out of range**
что делать?

Python
1
2
3
4
5
6
7
8
9
10
a, b, c, n = map(int, input().split())
Misha=[a]
Masha=[b]
Philipp=[c]
for i in range(1, n+1):
    Misha[i]=Masha[i-1]+Philipp[i-1]
    Masha[i]=Misha[i-1]+Philipp[i-1]
    Philipp[i]=Misha[i-1]+Masha[i-1]
    i+=1
print(B[n]-A[n])

@eaa · 16.10.2022, 15:31

Python
1
2
3
4
5
6
7
8
9
10
11
a0, b0, c0, n = map(int, input().split())
a = [a0] * (n + 1)
b = [b0] * (n + 1)
c = [c0] * (n + 1)
 
for i in range(1, n + 1):
    a[i] = b[i - 1] + c[i - 1]
    b[i] = a[i - 1] + c[i - 1]
    c[i] = a[i - 1] + b[i - 1]
 
print(a[n] - b[n])

Добавлено через 37 секунд

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

n⩽1018

это 10¹⁸ ?

@Maxim1704g · 16.10.2022, 15:41 **[ТС]**

eaa, да, а как-то без линейного алгоритма можно решить? Ассимтотика О(1)?

@eaa · 16.10.2022, 15:44

без списков, но тоже O(n).

Python
1
2
3
4
a, b, c, n = map(int, input().split())
for i in range(n):
    a, b, c = b + c, a + c, a + b
print(a - b)

формулу попробуй выведи.

@Maxim1704g · 16.10.2022, 15:50 **[ТС]**

eaa, Программа выполнялась слишком долго и была прервана на 5 тесте

Добавлено через 1 минуту
eaa, а тут формулу можно вывести?

@eaa · 16.10.2022, 15:52

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

выполнялась слишком долго

это и так понятно.

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

а тут формулу можно вывести?

похоже можно, но мне лень.

@Maxim1704g · 16.10.2022, 15:55 **[ТС]**

eaa, поможете хотя бы начать, а дальше я и сам добью, пожалуйста?

@eaa · 16.10.2022, 16:05

тут за логарифм можно посчитать, но за О(1) мне кажется тоже.

@Maxim1704g · 16.10.2022, 16:07 **[ТС]**

eaa, мне бы идею

@eaa · 16.10.2022, 16:11

блин, классная задача.
ответ a-b или b-a, в зависимости от четности n

Добавлено через 1 минуту

Python
1
2
3
4
5
a, b, c, n = map(int, input().split())
if n%2:
    print(b-a)
else:
    print(a-b)

@Maxim1704g · 16.10.2022, 16:20 **[ТС]**

eaa, спасибище!!!
Можете с этой помочь, пожалуйста?

Добавлено через 1 минуту
eaa, Задача для третьеклассника

@eaa · 16.10.2022, 16:29

Не по теме:

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

спасибище!!!

там есть кнопка сказать спасибо.

@Maxim1704g · 16.10.2022, 16:31 **[ТС]**

eaa, спасибо, нашёл

Новые блоги и статьи Все статьи Все блоги /
Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@Maxim1704g 2 / 2 / 0 Регистрация: 25.08.2018 Сообщений: 78
	16.10.2022, 15:41 [ТС]
	eaa, да, а как-то без линейного алгоритма можно решить? Ассимтотика О(1)? 0

@Maxim1704g 2 / 2 / 0 Регистрация: 25.08.2018 Сообщений: 78
	16.10.2022, 15:50 [ТС]
	eaa, Программа выполнялась слишком долго и была прервана на 5 тесте Добавлено через 1 минуту eaa, а тут формулу можно вывести? 0

@Maxim1704g 2 / 2 / 0 Регистрация: 25.08.2018 Сообщений: 78
	16.10.2022, 15:55 [ТС]
	eaa, поможете хотя бы начать, а дальше я и сам добью, пожалуйста? 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	16.10.2022, 16:05
	тут за логарифм можно посчитать, но за О(1) мне кажется тоже. 0

@Maxim1704g 2 / 2 / 0 Регистрация: 25.08.2018 Сообщений: 78
	16.10.2022, 16:07 [ТС]
	eaa, мне бы идею 0

@Maxim1704g 2 / 2 / 0 Регистрация: 25.08.2018 Сообщений: 78
	16.10.2022, 16:20 [ТС]
	eaa, спасибище!!! Можете с этой помочь, пожалуйста? Добавлено через 1 минуту eaa, Задача для третьеклассника 0

@Maxim1704g 2 / 2 / 0 Регистрация: 25.08.2018 Сообщений: 78
	16.10.2022, 16:31 [ТС]
	eaa, спасибо, нашёл 0

Python динамическое программирование (list assignment index out of range). Что делать?

Решение