Задача Бой со змеем

@semen1984 · Регистрация: 07.05.2024

Прошу помощи в оптимизации цикла в функции:

Python
1
2
3
4
5
6
7
8
9
10
11
12
def check(x, hdr, ddr, hpo, dpo):
    summa_hpo = hpo*x
    while x>0:
        hdr = hdr - x*dpo
        if hdr <= 0:
            break
        summa_hpo = summa_hpo - ddr
        if summa_hpo % hpo > 0:
            x = summa_hpo//hpo+1
        else:
            x = summa_hpo//hpo
    return hdr<=0

возможно, это прогрессия, которую можно свернуть формулой суммы
сложность для меня заключается в том, что есть "плавающая" единица при целочисленном делении

hdr = hdr - x*dpo - (x - (ddr//hpo+1 или ddr//hpo))*dpo - ...

@semen1984 · 17.07.2024, 14:38 **[ТС]**

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

def check(hd, dd, hp ,dp) -> int:
for n in range(1, int(hd/dd)):
a1 = (hd/n)-((dd*(n-1))/2)
# print(a1)
if a1>0 and a1<dd:
break
coun = (a1 + dd * (n-1)) / dp
return int(coun)
if __name__ == "__main__":
hd, dd, hp, dp = map(int,input().split(' '))
print(check(hd, dd, hp, dp))

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

интересно, что навскидку hp (здоровье помощника) не участвует в вычислениях
возможно, вы очень близки к решению, но найти ошибку я пока не смог

@vokon01 · 17.07.2024, 16:24

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
def check(hd, dd, hp ,dp) -> int:
    for n in range(1, int(hd/dd)):
        a1 = (hd/n)-((dd*(n-1))/2)
        # print(a1)
        if a1>0 and a1<dd:
            break
    coun = (a1 + dd * (n-1)) / hp
    return int(coun)
 
 
if __name__ == "__main__":
    hd, dd, hp, dp = map(int,input().split(' '))
    print(check(hd, dd, hp, dp))

Добавлено через 1 минуту
В действительности здоровье защитников должно участвовать. Поправил код. Еще возможно ошибка может появиться, если урон змея не кратен здоровью защитника.

@semen1984 · 17.07.2024, 17:32 **[ТС]**

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

1
def check(hd, dd, hp ,dp) -> int:
for n in range(1, int(hd/dd)):
a1 = (hd/n)-((dd*(n-1))/2)
# print(a1)
if a1>0 and a1<dd:
break
coun = (a1 + dd * (n-1)) / hp
return int(coun)
if __name__ == "__main__":
hd, dd, hp, dp = map(int,input().split(' '))
print(check(hd, dd, hp, dp))

снова ошибка на том же тесте
посмотреть тест возможности нет

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

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

да, в этом тоже есть загвоздка, раненые помощники бьют как здоровые, но их здоровье не восстанавливается

@vokon01 · 17.07.2024, 17:40

в это строке
if a1>0 and a1<dd:
можно попробовать >= и <= в разных комбинациях

А много тестов не проходит?

@semen1984 · 17.07.2024, 17:46 **[ТС]**

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

в это строке
if a1>0 and a1<dd:
можно попробовать >= и <= в разных комбинациях

<= - валится на 3м тесте
>= - валится на 1м тесте
>= и <= - валится на 1м тесте

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

А много тестов не проходит?

система так настроена, что при первом не пройденном тесте, не запускает следующие
а также нельзя посмотреть сами тестовые сценарии

моё решение с бинарным поиском с циклом отваливается на 11м тесте по пределу машинного времени

@Aael · 15.09.2024, 03:53

semen1984, получилось решить?

Вряд ли там есть закрытая формула для суммы, но могу предложить вариант вычислять её по скорости за корень от значения самой суммы. Т.е. если воины наносят большой урон за раз или дракон ест их очень быстро, то количество слагаемых в сумме не велико, и сумма хорошо считается. Но при близких к нулю уронах число слагаемых увеличивается и становится сравнимым с числом жизней дракона (которое ограничено 10^9 по условию).

В терминах "закрашенных клеток" или "целых точек", которые являются одним ударом одного воина по дракону, ситуацию можно изобразить "пирамидой"/"треугольником", где номер столбца означает номер итерации, а высота столбца - число живых воинов на итерации. Искомая сумма - это площадь пирамиды. Так вот, Ваш алгоритм вычисляет площадь, суммируя высоты столбцов слева направо, и быстро это делает если пирамида "высокая и узкая". Но когда она "широкая" - получаем TL, здесь быстрее складывать не высоты столбцов, а длины строк. Т.о. если перед суммированием определять форму пирамиды и выбирать соотв. алгоритм, то среди всех пирамид площади S, в сумме всегда будет не более √S слагаемых. И т.к. площадь сравнима с Hits=HP(дракона)/DMG(воина) < 10^9/1, мы получим (с учетом двоичного поиска) примерно Log(Hits)√Hits < 10 * 10^5 = 10^6 "сложений", что ятд выглядит приемлемо.

"Развернуть" суммирование можно так: для фиксированного номера строки s, подобрать такой наибольший номер итерации (столбца) k, что на k-ой итерации еще присутствует s человек, а на (k+1)-ой уже нет. Это выражается простым неравенством. Число k(s) и есть искомая ширина s-ой строки.

Т.к. в двоичном поиске иногда берем избыточное число человек, а ищем число ударов пока всех не съедят, то после каждого суммирования необходимо проверять - достаточно ли этого числа чтобы уже убить дракона, и если да - не вычислять остаток.

Пример. n=6 - число воинов, dd=7 - урон дракона, wh=5 - число жизней воина.

@Whabablca · 15.09.2024, 19:55

Aael, А как вам такой вариант решения?

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
from  math import gcd
 
def check(x, hdr, ddr, hpo, dpo):
    def sum_simplyfy(n, p, q):
        t = gcd(p, q)
        p = p // t
        q = q // t
        s = 0
        z = 1
        while (q > 0) and (n > 0):
            t = p // q
            s = s + z * t * n * (n + 1) // 2
            p = p - q * t
            t = n // q
            s = s + z * p * t * (n + 1) - z * t * (p * q * t + p + q - 1) // 2
            n = n - q * t
            t = n * p // q
            s = s + z * t * n
            n = t
            p, q = q, p
            z = -z
        return s
        
    summa_hpo = hpo * x // ddr
    return hdr - dpo * ((summa_hpo + 1) * x - sum_simplyfy(summa_hpo, ddr, hpo)) <= 0
 
hd, dd, hp, dp = map(int,input().split(' '))
 
left = 0
right = hd // dp + 1
while right - left > 1:
    mid = (left + right) // 2
    if check(mid, hd, dd, hp, dp):
        right = mid
    else:
        left = mid
print(right)

@semen1984 · 15.09.2024, 21:01 **[ТС]**

Aael,
спасибо за Ваш ответ
решить на тот момент не удалось, по времени на больших значениях решение "не пролезало"
сейчас уже возможности отправить новое решение нет

возможно, кто-то воспользуется этим решением и даст обратную связь

Новые блоги и статьи Все статьи Все блоги /
23. что сделано за последнее время. anaschu 17.06.2026 • Эталон: Клиника НИИ питания РАМН, Москва — централизованный пищеблок, 225 коек, 180 пациентов • Git: репозиторий med2, ветка абсентеизм. Рабочий файл: СРесурсами1_v4. alp • Смежный проект:. . .	22. Подключение слоя системной динамики (потоковые диффуры): экономические метрики модели anaschu 17.06.2026 Апдейт модели: финансовый контур, разделение затрат Продолжаю развивать модель рабочего коллектива на AnyLogic. В этот раз работа шла над агентом Экономика — финансовым SD-слоем модели. Задача:. . .	[golang] Insert Delete GetRandom O(1) (Leetcode: 380) alhaos 16.06.2026 Insert Delete GetRandom O(1) Сложность: Medium Источник: LeetCode 380 Задача Реализовать структуру данных RandomizedSet, которая поддерживает следующие операции за O(1) в среднем:	Свет в конце тоннеля kumehtar 16.06.2026 Поймал себя на одной мысли. Раньше мне всегда казалось неправильным жить без чёткого понимания, куда всё идёт. Будто я иду по дороге судьбы, но не знаю, куда она ведёт. А раз не знаю — значит,. . .
[golang] Реализация стека с поддержкой получения минимального элемента за O(1) alhaos 16.06.2026 Min Stack Сложность: Medium Источник: LeetCode 155 Задача: Реализовать стек который поддерживает push, pop, top и получение минимального элемента за O(1). Методы:	[golang] Конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. alhaos 10.06.2026 Задача Реализовать конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. Сигнатура func Fetch(urls string, maxConcurrent int) Result Пример urls :=. . .	[golang] Состояние гонки (race condition) alhaos 10.06.2026 Состояние гонки (race condition) Состояние гонки (Race Condition) — это ошибка, возникающая при одновременном доступе нескольких горутин к одним и тем же данным без должной синхронизации. При этом. . .	Взрослые отношения, и почему они не получаются kumehtar 09.06.2026 Когда в детстве ребёнок не получает от родителей чего-то важного, он лишается не просто приятных переживаний, а основы для формирования определённых внутренних качеств и навыков. Если ребёнок не. . .

@vokon01 2 / 2 / 0 Регистрация: 10.06.2024 Сообщений: 9
	17.07.2024, 17:40
	в это строке if a1>0 and a1<dd: можно попробовать >= и <= в разных комбинациях А много тестов не проходит? 0

@Aael 964 / 485 / 241 Регистрация: 02.06.2016 Сообщений: 760
	15.09.2024, 03:53
	semen1984, получилось решить? Вряд ли там есть закрытая формула для суммы, но могу предложить вариант вычислять её по скорости за корень от значения самой суммы. Т.е. если воины наносят большой урон за раз или дракон ест их очень быстро, то количество слагаемых в сумме не велико, и сумма хорошо считается. Но при близких к нулю уронах число слагаемых увеличивается и становится сравнимым с числом жизней дракона (которое ограничено 10^9 по условию). В терминах "закрашенных клеток" или "целых точек", которые являются одним ударом одного воина по дракону, ситуацию можно изобразить "пирамидой"/"треугольником", где номер столбца означает номер итерации, а высота столбца - число живых воинов на итерации. Искомая сумма - это площадь пирамиды. Так вот, Ваш алгоритм вычисляет площадь, суммируя высоты столбцов слева направо, и быстро это делает если пирамида "высокая и узкая". Но когда она "широкая" - получаем TL, здесь быстрее складывать не высоты столбцов, а длины строк. Т.о. если перед суммированием определять форму пирамиды и выбирать соотв. алгоритм, то среди всех пирамид площади S, в сумме всегда будет не более √S слагаемых. И т.к. площадь сравнима с Hits=HP(дракона)/DMG(воина) < 10^9/1, мы получим (с учетом двоичного поиска) примерно Log(Hits)√Hits < 10 * 10^5 = 10^6 "сложений", что ятд выглядит приемлемо. "Развернуть" суммирование можно так: для фиксированного номера строки s, подобрать такой наибольший номер итерации (столбца) k, что на k-ой итерации еще присутствует s человек, а на (k+1)-ой уже нет. Это выражается простым неравенством. Число k(s) и есть искомая ширина s-ой строки. Т.к. в двоичном поиске иногда берем избыточное число человек, а ищем число ударов пока всех не съедят, то после каждого суммирования необходимо проверять - достаточно ли этого числа чтобы уже убить дракона, и если да - не вычислять остаток. Пример. n=6 - число воинов, dd=7 - урон дракона, wh=5 - число жизней воина. 0

@semen1984 9 / 7 / 2 Регистрация: 07.05.2024 Сообщений: 75
	15.09.2024, 21:01 [ТС]
	Aael, спасибо за Ваш ответ решить на тот момент не удалось, по времени на больших значениях решение "не пролезало" сейчас уже возможности отправить новое решение нет возможно, кто-то воспользуется этим решением и даст обратную связь 0