GCJ/2017/1A/C/main.go

package main

import (
	"fmt"
	"math"
)

var hd, ad, hk, ak, b, d int
var hp int

type state struct {
	hd int
	ad int
	hk int
	ak int
	t  int
	c  bool
}

func getBuffCnt() int {
	if b == 0 {
		return 0
	}
	bAddA := int(math.Ceil(float64(hk) / float64(ad)))
	for cnt := 1; ; cnt++ {
		nextBAA := cnt + int(math.Ceil(float64(hk)/float64(ad+cnt*b)))
		if bAddA < nextBAA {
			return cnt - 1
		}
		bAddA = nextBAA
	}
}

func nextDebuffCnt() int {
	if d == 0 || ak == 0 {
		return 0
	} else if ak <= d {
		return 1
	}
	killed := int(math.Ceil(float64(hd) / float64(ak)))
	minAk := int(math.Ceil(float64(hd)/float64(killed))) - 1
	return int(math.Ceil(float64(ak-minAk) / float64(d)))
}

func getAttackCnt(st state) int {
	if st.ak == 0 {
		return maxInt(1, st.hk/st.ad)
	}
	return maxInt(1, minInt(st.hd/st.ak-1, st.hk/st.ad))
}

func main() {
	var T int
	fmt.Scan(&T)
	for tc := 1; tc <= T; tc++ {
		fmt.Scan(&hd, &ad, &hk, &ak, &b, &d)
		hp = hd

		println("Case", tc)

		buff := getBuffCnt()
		st := state{hp, ad, hk, ak, 0, false}
		for buffCnt := buff; 0 < st.hk; { // !Kill
			if st.hd <= st.ak && st.ad < st.hk { // Need cure
				if st.c { // Cured?
					st.t = 0
					break // Die
				}
				st = state{hd - st.ak, st.ad, st.hk, st.ak, st.t + 1, true} // Cure
				continue
			}
			if buffCnt != 0 {
				buffCnt--
				st = state{st.hd - st.ak, st.ad + b, st.hk, st.ak, st.t + 1, false} // Buff
				continue
			}
			t := getAttackCnt(st)
			st = state{st.hd - st.ak*t, st.ad, st.hk - st.ad*t, st.ak, st.t + t, false} // Attack
		}
		turn := st.t
		debuff, dt := nextDebuffCnt(), 0
	sim:
		for debuff != 0 {
			c := false
			for debuff != 0 {
				if hp <= ak-d { // Need cure
					if c { // Cured?
						break sim // Die
					}
					hp, dt, c = hd-ak, dt+1, true
					continue // Cure
				}
				ak = maxInt(0, ak-d)
				debuff, hp, dt, c = debuff-1, hp-ak, dt+1, false // Debuff
			} // Simulate debuff
			println("sim debuff", dt)
			st = state{hp, ad, hk, ak, dt, false}
			for buffCnt := buff; 0 < st.hk; { // !Kill
				if st.hd <= st.ak && st.ad < st.hk { // Need cure
					if st.c { // Cured?
						st.t = 0
						break // Die
					}
					st = state{hd - st.ak, st.ad, st.hk, st.ak, st.t + 1, true} // Cure
					continue
				}
				if buffCnt != 0 {
					buffCnt--
					st = state{st.hd - st.ak, st.ad + b, st.hk, st.ak, st.t + 1, false} // Buff
					continue
				}
				t := getAttackCnt(st)
				st = state{st.hd - st.ak*t, st.ad, st.hk - st.ad*t, st.ak, st.t + t, false} // Attack
			} // Simulate buff and attack
			if turn == 0 || st.t < turn {
				turn = st.t
			}
			debuff = nextDebuffCnt()
		}
		fmt.Printf("Case #%d: ", tc)
		if turn == 0 {
			fmt.Println("IMPOSSIBLE")
		} else {
			fmt.Println(turn)
		}
	}
}

func maxInt(x, y int) int {
	if x < y {
		return y
	}
	return x
}

func minInt(x, y int) int {
	if x < y {
		return x
	}
	return y
}