дайте идею как решать алгоритмическую задачу. по возможности, помогите найти ошибку в моем решении
данна задача: Вы играете в интересную стратегию. У вашего соперника остались всего одна казарма — здание, в котором постоянно появляются новые солдаты. Перед атакой у вас есть x солдат. За один раунд каждый солдат может убить одного из солдат противника или нанести 1 очко урона казарме (вычесть единицу здоровья у казармы). Изначально у вашего оппонента нет солдат. Тем не менее, его казарма имеет y единиц здоровья и производит p солдат за раунд.
Ход одного раунда:
1.Каждый солдат из вашей армии либо убивает одного из солдат вашего противника, либо наносит 1 очко урона казарме. Каждый солдат может выбрать своё действие. Когда казарма теряет все свои единицы здоровья, она разрушается. 2.Ваш противник атакует. Он убьет k ваших солдат, где k — количество оставшихся у противника солдат. 3.Если казармы еще не разрушены, ваш противник производит p новых солдат. Ваша задача — разрушить казарму и убить всех солдат противника. Если это возможно, посчитайте минимальное количество раундов, которое вам нужно для этого. В противном случае выведите -1.
Формат ввода На вход подаётся три целых числа x, y, p (1 ≤ x, y, p ≤ 5000) — количество ваших солдат на старте игры, количество очков здоровья казармы и количество производимых за раунд казармой солдат, соответственно. Каждое число расположено в новой строке.
Формат вывода Если возможно убить всех вражеских солдат и разрушить казарму, выведите минимальное количество раундов, необходимых для этого. В противном случае выведите -1.
Пример 1
Ввод
10
11
15
Вывод
4
|
Пример 2
Ввод
1
2
1
Вывод
-1
|
Пример 3
Ввод
1
1
1
Вывод
1
|
Пример 4
Ввод
25
200
10
Вывод
13
меня хватило только на самое тривиальное решение, которое не прошло по всем тестам. и методом тыка я так и не смог найти ошибочные входные данные. подскажите правильный алгоритм решения, или может хотя бы общую идею, чтобы переписать код.
мое не проходящее по всем тестам решение:
def f(x, y, p):
if x > p:
overhit = x - p
return (y + overhit - 1 - x) // overhit + 1
army = 0
move_num = 0
while x < y and x > 0:
move_num += 1
y -= x
x -= army
army += p
if y > 0:
move_num += 1
overhit = x - y
army -= overhit
x -= army
while x > 0 and army > 0:
move_num += 1
army -= x
x -= army
return move_num if army <= 0 else -1
x, y, p = map(int, input().split()) print(f(x, y, p))
Ответы (1 шт):
Как вариант, такое решение
def f(x, y, p):
c = 0
#print("x,y,p,c")
while True:
c += 1
x -= p
y -= 1
p += 1
#print(x, y, p, c)
if x <= 0:
print("-1 (Enemy win!)")
print(f"Number of step {c}")
break
if y <= 0:
x = x
p = p
y = 0
c = c
#print("1.2")
break
while x > 0:
c += 1
x -= p
p -= 1
#print(x, y, p, c)
if x <= 0:
print("-1 (Enemy win!)")
print(f"Number of step {c}")
break
if p <= 0:
print("1 (You WIN!!!)")
print(f"Number of step {c}")
break
f(122, 10, 1)
# You should know that for win: x = (y + p)^2 + 1