GCJ/2008/2/A/main.go

package main

import (
	"fmt"
)

// IMPOSSIBLE is a really large number that means impossible
const IMPOSSIBLE int = 100000

func main() {
	var N int
	fmt.Scan(&N)
	for cid := 0; cid < N; cid++ {
		var M, V int
		fmt.Scan(&M, &V)
		n := (M + 1) / 2
		gate := make([]Pair, n)
		for i := 1; i < n; i++ {
			fmt.Scan(&gate[i]._1, &gate[i]._2)
		}
		dp := make([][]int, M+1)
		for i := range dp {
			dp[i] = make([]int, 2)
			if n <= i {
				var leaf int
				fmt.Scan(&leaf)
				if leaf == 0 {
					dp[i][1] = IMPOSSIBLE
				} else {
					dp[i][0] = IMPOSSIBLE
				}
			}
		}
		for i := n - 1; 0 < i; i-- {
			lc, rc := 2*i, 2*i+1
			change := []int{IMPOSSIBLE, IMPOSSIBLE} // The step to take when current gate changes
			if gate[i]._1 == 1 {                    // AND gate
				if gate[i]._2 == 1 {
					change[0], change[1] = maxInt(dp[lc][0], dp[rc][0], dp[lc][0]+dp[rc][0])+1, minInt(dp[lc][1], dp[rc][1])+1
				}
				dp[i][0] = minInt(change[0], minInt(dp[lc][0], dp[rc][0]))
				dp[i][1] = minInt(change[1], maxInt(dp[lc][1], dp[rc][1], dp[lc][1]+dp[rc][1]))
			} else { // OR gate
				if gate[i]._2 == 1 {
					change[0], change[1] = minInt(dp[lc][0], dp[rc][0])+1, maxInt(dp[lc][1], dp[rc][1], dp[lc][1]+dp[rc][1])+1
				}
				dp[i][0] = minInt(change[0], maxInt(dp[lc][0], dp[rc][0], dp[lc][0]+dp[rc][0]))
				dp[i][1] = minInt(change[1], minInt(dp[lc][1], dp[rc][1]))
			}
		}
		if dp[1][V] >= IMPOSSIBLE { // Note: int maybe int64 in 64bit platform, or int32
			fmt.Printf("Case #%d: IMPOSSIBLE\n", cid+1)
		} else {
			fmt.Printf("Case #%d: %d\n", cid+1, dp[1][V])
		}
	}
}