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

@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)

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .

@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