Have you heard about Megamind? Megamind and Metro Man are two aliens who came to earth. Megamind wanted to destroy the earth, while Metro Man wanted to stop him and protect mankind. After a lot of fighting, Megamind finally threw Metro Man up into the sky. Metro Man was defeated and was never seen again. Megamind wanted to be a super villain. He believed that the difference between a villain and a super villain is nothing but presentation. Megamind became bored, as he had nobody or nothing to fight against since Metro Man was gone. So, he wanted to create another hero against whom he would fight for recreation. But accidentally, another villain named Hal Stewart was created in the process, who also wanted to destroy the earth. Also, at some point Megamind had fallen in love with a pretty girl named Roxanne Ritchi. This changed him into a new man. Now he wants to stop Hal Stewart for the sake of his love. So, the ultimate fight starts now.

* Megamind has unlimited supply of guns named Magic-48. Each of these guns has `shots` rounds of magic spells.
* Megamind has perfect aim. If he shoots a magic spell it will definitely hit Hal Stewart. Once hit, it decreases the energy level of Hal Stewart by `dps` units.
* However, since there are exactly `shots` rounds of magic spells in each of these guns, he may need to swap an old gun with a fully loaded one. This takes some time. Let’s call it swapping period. 
* Since Hal Stewart is a mutant, he has regeneration power. His energy level increases by `regen` unit during a swapping period. 
* Hal Stewart will be defeated immediately once his energy level becomes zero or negative. 
* Hal Stewart initially has the energy level of `hp` and Megamind has a fully loaded gun in his hand.
* Given the values of `hp`, `dps`, `shots` and `regen`, find the minimum number of times Megamind needs to shoot to defeat Hal Stewart. If it is not possible to defeat him,  return `-1` instead.

# Example
Suppose, `hp` = 13, `dps` = 4, `shots` = 3 and `regen` = 1. There are 3 rounds of spells in the gun. Megamind shoots all of them. Hal Stewart’s energy level decreases by 12 units, and thus his energy level becomes 1. Since Megamind’s gun is now empty, he will get a new gun and thus it’s a swapping period. At this time, Hal Stewart’s energy level will increase by 1 unit and will become 2. However, when Megamind shoots the next spell, Hal’s energy level will drop by 4 units and will become −2, thus defeating him. So it takes 4 shoots in total to defeat Hal Stewart. However, in this same example if Hal’s regeneration power was 50 instead of 1, it would have been impossible to defeat Hal.

Difficulty: EASY
Tags: Fundamentals

Game theory

Starter code:
def mega_mind(hp, dps, shots, regen):
	

Solutions:
from math import ceil

def mega_mind(hp, dps, shots, regen):
	if dps * shots >= hp:
		return ceil(hp / dps)
	if dps * shots <= regen:
		return -1
	number_of_regenerations = ceil((hp - dps * shots) / (dps * shots - regen))
	return ceil((hp + regen * number_of_regenerations) / dps)


from math import ceil

def mega_mind(hp, dps, shots, regen):
	if hp > dps * shots <= regen:
		return -1
	n = 0
	while True:
		s = min(int(ceil(hp / dps)), shots)
		n += s
		hp -= dps * s
		if hp <= 0:
			break
		hp += regen
	return n


def mega_mind(hp, dps, shots, regen):
	chp = hp
	ans = 0
	while True:
		r = (chp + dps - 1) // dps
		if r <= shots:
			return ans + r
		chp -= dps * shots - regen
		ans += shots
		if chp >= hp:
			return -1


from math import ceil

def mega_mind(hp, dps, shots, regen):
	damage = dps * shots
	if hp > damage <= regen:
		return -1
	if hp <= damage:
		return ceil(hp / dps)
	full = (hp - regen) // (damage - regen)
	if damage * full == hp + (full - 1) * regen:
		return full * shots
	left = hp + full * (regen - damage)
	return full * shots + ceil(left / dps)


from math import ceil

def mega_mind(hp, dps, shots, regen):
	print(hp, dps, shots, regen)
	if hp > dps * shots and regen >= dps * shots:
		return -1
	if hp <= dps * shots:
		return ceil(hp / dps)
	a = ceil((hp - dps * shots) / (-regen + dps * shots))
	return a * shots + ceil((hp + a * regen - a * dps * shots) / dps)


def mega_mind(hp, dps, shots, regen):
	if hp > dps * shots and dps * shots <= regen:
		return -1
	res = 0
	num_shots = 0
	if hp > dps * shots:
		num_rounds = (hp - dps * shots) // (dps * shots - regen)
		res = num_rounds * shots
		hp -= num_rounds * (dps * shots - regen)
	while hp > 0:
		hp -= dps
		res += 1
		num_shots += 1
		if hp > 0 and num_shots == shots:
			hp += regen
			num_shots = 0
	return res


import math

def mega_mind(hp, dps, shots, regen):
	if regen - dps * shots >= 0 and hp - dps * shots > 0:
		return -1
	if hp - dps * shots <= 0:
		return math.ceil(hp / dps)
	n = 0
	while hp - dps * shots > 0:
		hp -= dps * shots - regen
		n += 1
	return math.ceil(hp / dps) + n * shots


def mega_mind(hp, dps, shots, regen):
	if hp > dps * shots and dps * shots <= regen:
		return -1
	total_shot = 0
	barell = shots
	while hp > 0:
		if hp > dps * shots:
			if barell == 0:
				barell += shots
				hp += regen
			else:
				barell -= shots
				hp -= dps * shots
				total_shot += shots
		elif barell == 0:
			barell += shots
			hp += regen
		else:
			barell -= 1
			hp -= dps
			total_shot += 1
	return total_shot


def mega_mind(hp, dps, shots, regen):
	print((hp, dps, shots, regen))
	if dps * shots < hp and dps * shots <= regen:
		return -1
	dps_round = dps * shots
	if hp - dps_round <= 0:
		return hp // dps + (0 if hp % dps == 0 else 1)
	hp -= dps_round
	round = hp // (dps_round - regen)
	hp -= round * (dps_round - regen)
	if hp == 0:
		return (round + 1) * shots
	hp += regen
	print((round, hp))
	return shots * (round + 1) + hp // dps + (0 if hp % dps == 0 else 1)


def mega_mind(hp, dps, shots, regen):
	if regen < dps * shots or hp <= shots * dps:
		cnt = 0
		while hp > shots * dps:
			hp = hp - shots * dps + regen
			cnt += shots
		for i in range(hp):
			hp = hp - dps
			cnt += 1
			if hp <= 0:
				return cnt
	return -1