Задача "Очередная задача про победу над монстрами". ОЧЕНЬ нужна помощь с кодом

@Veunder · Регистрация: 07.06.2023

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

Здравствуйте. Вот сама задача:
Очередная задача про победу над монстрами
ограничение по времени на тест 1 секунда
ограничение по памяти на тест 256 мегабайт
ввод стандартный ввод
вывод стандартный вывод
Недавно Миша увлекся разработкой игр и уже выпустил свою первую игру в жанре RPG «Надземелья и Дарконы». Вы играете за рыцаря, который побеждает дарконов в надземельях. Все надземелья сгенерированы процедурно, драки с дарконами детально проработаны, а умопомрачительной 3D-графике позавидует даже «Суперпанк»!

Даня уже давно занимается прохождением игр на скорость, за что он и получил свою известность в сети Интернет. Миша обратился к Дане за помощью: он хочет, чтобы Даня во время прямой трансляции прошел игру «Надземелья и Дарконы» как можно быстрее, так как думает, что это привлечет новых игроков. Даня не смог отказаться от очередного испытания, однако быстрое прохождение требует глубоких знаний об игре, а времени на изучение у него нет, так что Миша вкратце объяснил, в чем заключается суть игры.

Ваш персонаж начинает свой путь с уровнем силы x. Он может пойти в любое из n надземелий, пронумерованных целыми числами от 1 до n, и попытаться победить там даркона, за счет чего повысить свой уровень. А именно, в надземелье с номером i живет даркон с уровнем силы ai, и его можно победить только в том случае, если уровень силы вашего персонажа больше уровня силы даркона. В противном случае вы гарантировано проиграете. После победы над дарконом уровень персонажа повысится на ai, а само надземелье станет зачищенным, то есть там больше не будут появляться дарконы. Целью игры является победить самого большого и страшного даркона, живущего в надземелье под номером n, поэтому вы должны сражаться с дарконами, пока не получите достаточный уровень силы и не победите финального босса.

Зная все это, Дане осталось только выбрать стратегию прохождения, то есть какие надземелья и в каком порядке ему нужно зачищать, чтобы пройти игру. Естественно, ему в первую очередь важна скорость, так что стратегия должна быть выбрана таким образом, чтобы в каждом сражении Даня гарантировано выходил победителем, а сражений было как можно меньше.

Найдите оптимальную стратегию или скажите, что игру пройти невозможно.
Входные данные
Первая строка содержит два целых числа n и x (1≤n≤100000, 1≤x≤109) — количество надземелий и изначальный уровень силы персонажа, соответственно.

Вторая строка содержит n целых чисел a1,a2,…,an (1≤ai≤109), где ai — уровень силы даркона, живущего в надземелье с номером i.

Выходные данные
Если игру пройти невозможно, выведите в единственной строке число 0.

В противном случае в первой строке выведите целое число m (1≤m≤n) — количество зачищенных надземелий в оптимальной стратегии.

Во второй строке выведите m различных целых чисел b1,…,bm (1≤bi≤n) — порядок, в котором Даня должен посещать надземелья в оптимальной стратегии. Обратите внимание, что последним надземельем должно быть надземелье с номером n, в которой обитает босс (иными словами, bm=n).

В случае, если существует несколько оптимальных ответов, выведите любой из них.

Примеры
входные данные
10 2
4 1 5 6 8 3 2 7 9 10
выходные данные
2 7 6 1 10

входные данные
5 1
1 1 1 1 1
выходные данные
0

Примечание
В первом примере оптимальная стратегия выглядит следующим образом.

Победить даркона в надземелье с номером 2, после этого сила героя будет равна 2+1=3.
Победить даркона в надземелье с номером 7, после этого сила героя будет равна 3+2=5.
Победить даркона в надземелье с номером 6, после этого сила героя будет равна 5+3=8.
Победить даркона в надземелье с номером 1, после этого сила героя будет равна 8+4=12.
Наконец, победить босса в надземелье с номером 10, так как его сила равна 10, а сила героя равна 12.
Во втором примере сила всех дарконов равна исходной силе героя, поэтому победить их невозможно.

Вот мой код, но он проходит только первый 5 тестов(их у меня нет, кроме примеров выше):

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
n, x = map(int, input().split())
a = list(map(int, input().split()))
optimal = 0
defded = []
while True:
    if x > a[n - 1]:
        defded.append(n)
        print(len(defded))
        print(*defded)
        break
    mx = x + optimal
    optimal = min(a)
    c = 0
    for i in range(len(a)):
        if x > a[i] and i not in defded and x + a[i] > mx:
            optimal = a[i]
            c = i
    if optimal >= x:
        print(0)
        break
    x += optimal
    defded.append(c + 1)

Можете пожалуйста помочь, СРОЧНО!

@idealist · 03.02.2024, 06:07

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
28
29
30
31
32
33
34
35
from bisect import bisect_left
 
def get_res(n, pers_x, arr):
    def find_lt(a, x):
        'Находит крайнее правое значение, меньшее чем x'
        i = bisect_left(a, x)
        if i:
            return a[i-1]
        raise ValueError
 
    boss_x = arr[-1]
    n_of_x = dict((x,i) for i,x in enumerate(arr,1))
    arr = sorted(arr)
    res = []
    while True:
        if pers_x > boss_x:
            res.append(n)
            return res
        try:
            dar_x = find_lt(arr, pers_x)
        except:
            return 0
        pers_x += dar_x
        arr.remove(dar_x)
        dar_n = n_of_x[dar_x]
        res.append(dar_n)
 
n,x = map(int, input('n, x->').split())
*arr, = map(int, input('->').split())
res = get_res(n, x, arr)
if res == 0:
    print(res)
else:
    print(len(res))
    print(*res)

@iceblood · 03.02.2024, 10:10

1. Отсортируйте оверленды на основе уровня силы дарконов.
2. Пройдитесь по отсортированным оверленд и проверьте, достаточен ли уровень силы персонажа, чтобы победить каждого даркона.
3. Если персонаж может победить даркона, соответственно увеличьте уровень силы персонажа и добавьте сухопутье в оптимальную стратегию.
4. Если персонаж не может победить даркона, завершить игру невозможно.

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
28
29
30
31
32
33
34
35
36
37
def main():
    # Введите количество наложений и начальный уровень мощности персонажа
    n, x = map(int, input().split())
 
    # Введите уровни мощности дарконов в каждом списке сухопутных
    darkons = list(map(int, input().split()))
 
    # Создайте список кортежей (уровень мощности дарконов, номер сухопутного)
    overlands = [(darkon, i + 1) for i, darkon in enumerate(darkons)]
 
    # Отсортируйте оверленды на основе уровня силы дарконов
    overlands.sort()
 
    # Инициализируйте уровень силы персонажа и оптимальную стратегию
    power_level = x
    optimal_strategy = []
 
    # Пройдите по отсортированным оверлендам
    for darkon, overland in overlands:
        # Проверьте, может ли персонаж победить даркона
        if power_level >= darkon:
            # Увеличьте уровень силы персонажа
            power_level += darkon
            # Добавьте сухопутную часть к оптимальной стратегии
            optimal_strategy.append(overland)
        else:
            # Если персонаж не может победить даркона, завершить игру невозможно
            print(0)
            return
 
    # Выведите количество очищенных участков и оптимальную стратегию
    print(len(optimal_strategy))
    print(*optimal_strategy)
 
 
if __name__ == "__main__":
    main()

Этот код считывает входные данные, сортирует оверленды на основе уровней силы дарконов, перебирает оверленды и, по возможности, строит оптимальную стратегию. Если завершить игру невозможно, выводится значение 0. В противном случае выводится количество очищенных участков и оптимальная стратегия.

@idealist · 03.02.2024, 11:26

iceblood, пример работы вашей программы:

Python
1
2
3
4
n, x->7 3
->1 1 1 1 2 2 4
7
1 2 3 4 5 6 7

Моя программа это так обрабатывает:

Python
1
2
3
4
n, x->7 3
->1 1 1 1 2 2 4
2
6 7

@iceblood · 03.02.2024, 12:26

Отладчик лучший друг. Но я засиделся.

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

1. Код использует блок `try-except` для перехвата `ValueError`, который вызывается в функции `find_lt`, если заданное значение `x` не найдено в массиве `a`. Однако блок `except` не обрабатывает ошибку корректно. Он просто возвращает `0` без предоставления каких-либо указаний на то, что вызвало ошибку. Было бы лучше обработать исключение с помощью более информативного сообщения или предпринять соответствующие действия.
2. Определение области видимости переменной: Переменная `arr` переназначается в функции `get_res`, что может привести к путанице и непреднамеренному поведению. Хотя Python позволяет вам переназначать переменные разных типов, обычно считается хорошей практикой избегать повторного использования имен переменных для разных целей в пределах одной и той же области, чтобы улучшить читаемость и удобство сопровождения.
3. Логика функции `get_res` не совсем понятна. Похоже, что она выполняет итерацию по элементам списка `arr`, но цель цикла и условия завершения определены нечетко. Без четкого понимания предполагаемого поведения функции трудно определить, приведет ли она к желаемым результатам.
4. Функция `get_res` возвращает либо список целых чисел, либо целое число `0` на основе определенных условий. Однако вызов функции в основной части кода не обрабатывает случай, когда функция возвращает `0`. Он просто выводит результат без проверки его значения, что может привести к неожиданному поведению.

Чтобы улучшить код, вам следует рассмотреть возможность уточнения логики функции `get_res`, более изящной обработки исключений и обеспечения надлежащей обработки возвращаемого функцией значения в основной части кода. Кроме того, добавление комментариев и описательных имен переменных может помочь улучшить читаемость и удобство сопровождения кода.

@Red white socks · 04.02.2024, 08:47

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

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

Ну даже и малейшей мысли нет хоть что-то отредактировать. Только копипаста

@idealist · 04.02.2024, 09:29

Сделал программу чуть покрасивше:

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
28
29
30
31
32
from bisect import bisect_left
 
def get_res(n, pers_x, arr):
    def find_lt(a, x):
        'Находит крайнее правое значение, меньшее чем x'
        i = bisect_left(a, x)
        if i:
            return a[i-1]
        raise ValueError
 
    boss_x = arr.pop()
    n_of_x = dict((x, i) for i, x in enumerate(arr, 1))
    arr.sort()
    res = []
    while pers_x <= boss_x:
        try:
            dar_x = find_lt(arr, pers_x)
            pers_x += dar_x
            arr.remove(dar_x)
            res.append(n_of_x[dar_x])
        except:
            return 0
    return res + [n]
 
n, x = map(int, input('n, x->').split())
*arr, = map(int, input('->').split())
res = get_res(n, x, arr)
if res == 0:
    print(res)
else:
    print(len(res))
    print(*res)

Новые блоги и статьи Все статьи Все блоги /
Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .

@iceblood 0 / 0 / 0 Регистрация: 02.06.2020 Сообщений: 25
	03.02.2024, 12:26
	Отладчик лучший друг. Но я засиделся. В предоставленном коде, похоже, есть пара проблем. Вот разбивка потенциальных ошибок: 1. Код использует блок `try-except` для перехвата `ValueError`, который вызывается в функции `find_lt`, если заданное значение `x` не найдено в массиве `a`. Однако блок `except` не обрабатывает ошибку корректно. Он просто возвращает `0` без предоставления каких-либо указаний на то, что вызвало ошибку. Было бы лучше обработать исключение с помощью более информативного сообщения или предпринять соответствующие действия. 2. Определение области видимости переменной: Переменная `arr` переназначается в функции `get_res`, что может привести к путанице и непреднамеренному поведению. Хотя Python позволяет вам переназначать переменные разных типов, обычно считается хорошей практикой избегать повторного использования имен переменных для разных целей в пределах одной и той же области, чтобы улучшить читаемость и удобство сопровождения. 3. Логика функции `get_res` не совсем понятна. Похоже, что она выполняет итерацию по элементам списка `arr`, но цель цикла и условия завершения определены нечетко. Без четкого понимания предполагаемого поведения функции трудно определить, приведет ли она к желаемым результатам. 4. Функция `get_res` возвращает либо список целых чисел, либо целое число `0` на основе определенных условий. Однако вызов функции в основной части кода не обрабатывает случай, когда функция возвращает `0`. Он просто выводит результат без проверки его значения, что может привести к неожиданному поведению. Чтобы улучшить код, вам следует рассмотреть возможность уточнения логики функции `get_res`, более изящной обработки исключений и обеспечения надлежащей обработки возвращаемого функцией значения в основной части кода. Кроме того, добавление комментариев и описательных имен переменных может помочь улучшить читаемость и удобство сопровождения кода. 0