Ежедневные награды

@maksim-mshp · Регистрация: 22.03.2019

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

Ежедневные награды

Миша установил на свой телефон новую игру «Мемтест 2к17». В ней предусмотрены ежедневные награды за посещение. Награды бывают n уровней.
Тип награды зависит от награды за предыдущий день, а именно:

если игрок в предыдущий день не посещал игру, то за сегодняшнее посещение он получит награду уровня 1;
если игрок в предыдущий день зашёл в игру и получил награду уровня k (k≠n), то за сегодняшнее посещение он получит награду уровня k + 1;
если игрок в предыдущий день зашёл в игру и получил награду уровня n, то за сегодняшнее посещение он получит награду уровня 1.

На Форуме для Крутых Программистов Миша выяснил, что награды каждого из уровней составляют соответственно a₁,a₂, ...,a_n золотых монет. Через m дней состоится турнир по «Мемтест 2к17», к которому Миша хочет собрать как можно больше золотых монет. Помогите ему спланировать посещения игры на протяжении m дней, оставшихся до турнира. Найдите наибольшее количество золотых монет, которое он сможет получить за счёт ежедневных наград в этот период. Можно считать, что игра установлена в первый из этих m дней, то есть до этого Миша в неё ни разу не заходил.

Входные данные

Первая строка входных данных содержит натуральные числа n и m (1 ≤n,m≤ 1000) — количества уровней наград и дней до турнира.
Вторая строка входных данных содержит n целых чисел a₁,a₂, ...,a_n (1 ≤ aⁱ ≤ 1000), где aⁱ — величина награды i−го уровня в золотых монетах.

Выходные данные

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

Примечание

В первом тесте из примера Мише выгодно заходить в игру каждый день. Тогда он получит 1 + 2 + 4 = 7 золотых монет.
Во втором тесте из примера Мише выгодно заходить в игру в первый и третий день, получив в каждый из них по 4 монеты, тогда в сумме он получит 8 монет.

Примеры

Ввод
3 3
4 2 1
Вывод
8

Ввод
3 3
1 2 4
Вывод
7

Вот мои наработки, но не работает

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
n, m = map(int, input().split())
a = list(map(int, input().split()))
summa = 0 # a[0]
i = 0
for j in range(m - 1):
    if a[i + 1] >= a[i]:
        if i == 0:
            summa = a[0]
        summa += a[i + 1]
        i += 1
    else:
        if a[i + 1] >= a[0]:
            if i == 0:
                summa = a[0]
            summa += a[i + 1]
            i += 1
        else:
            # Эта часть кода наверно неправильная
            if a[0] * 2 >= a[i] + a[i + 1] + a[i + 2]:
                summa += a[0]
                i = 0
            else:
                if i == 0:
                    summa = a[0]
                summa += a[i + 1]
                i += 1
print(summa)

@ILIA IQ · 27.03.2020, 05:58

Сообщение от maksim-mshp

# Эта часть кода наверно неправильная

попробуй запустить программу в интерпретаторе питона там вроде он должен показывать в каком месте ошибка

Добавлено через 2 часа 23 минуты

Сообщение от maksim-mshp

Вот мои наработки, но не работает

Да кстати на каких числах ты тестировал программу?

@Cactoo · 27.03.2020, 19:55

Сижу над этой задачей, нифига не получается!

@TheRedl1ub · 28.03.2020, 13:00

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n, m = map(int, input().split())
A = list(map(int, input().split()))
c = 0
a = [(0, 0, 0)]
while a:
    y, b, x = a.pop(0)
    x += 1
    if x > m:
        c = max(c, y)
    else:
        a.append((y, 0, x))
        b += 1
        y += A[(b - 1) % n]
        a.append((y, b, x))
print(c)

Но она не проходит повремени!
можете ускорить?

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

@Cactoo 0 / 0 / 0 Регистрация: 23.03.2020 Сообщений: 14
	27.03.2020, 19:55
	Сижу над этой задачей, нифига не получается! 0