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

package main

import (
	"container/heap"
	"fmt"
	"math"
	"sort"
)

// Tuple3 ...
type Tuple3 struct {
	_1 int
	_2 int
	_3 int
}

// Tuple3PQ ...
type Tuple3PQ struct {
	queue  []Tuple3
	length int
}

func (pq Tuple3PQ) Len() int           { return pq.length }
func (pq Tuple3PQ) Less(i, j int) bool { return pq.queue[i]._1 < pq.queue[j]._1 }
func (pq Tuple3PQ) Swap(i, j int)      { pq.queue[i], pq.queue[j] = pq.queue[j], pq.queue[i] }

// Peek ...
func (pq Tuple3PQ) Peek() Tuple3 { return pq.queue[0] }

// Push ...
func (pq *Tuple3PQ) Push(x interface{}) {
	pq.queue = append(pq.queue, x.(Tuple3))
	pq.length++
}

// Pop ...
func (pq *Tuple3PQ) Pop() interface{} {
	pq.length--
	top := pq.queue[pq.length]
	pq.queue = pq.queue[:pq.length]
	return top
}

func main() {
	var T int
	fmt.Scan(&T)
	for tc := 1; tc <= T; tc++ {
		var N, P int
		fmt.Scan(&N, &P)
		R := make([]int, N)
		for i := 0; i < N; i++ {
			fmt.Scan(&R[i])
		}
		Q := make([][]int, N)
		for i := 0; i < N; i++ {
			Q[i] = make([]int, P)
			for j := 0; j < P; j++ {
				fmt.Scan(&Q[i][j])
			}
			sort.Ints(Q[i])
		}
		lower := make([]float64, N)
		for i := 0; i < N; i++ {
			lower[i] = float64(9 * R[i]) // Avoid the inaccurate of floating point computation!
		}
		upper := make([]float64, N)
		for i := 0; i < N; i++ {
			upper[i] = float64(11 * R[i])
		}
		var minPQ Tuple3PQ
		ptr := make([]int, N)
		kits := 0
	loop:
		for {
			maxMin, maxMax := 0, 0
			for i := 0; i < N; i++ {
				if ptr[i] == P {
					break loop
				}
				gram := float64(Q[i][ptr[i]] * 10)
				min := int(math.Ceil(gram / upper[i]))
				max := int(math.Floor(gram / lower[i]))
				if max == 0 || max < min {
					ptr[i]++
					i--
					continue
				}
				heap.Push(&minPQ, Tuple3{min, max, i})
				maxMin = maxInt(maxMin, min)
				maxMax = maxInt(maxMax, max)
			}
			for minPQ.Peek()._2 < maxMin { // If minMax < maxMin, then no solution for a new kit.
				top := heap.Pop(&minPQ).(Tuple3)
			moveptr:
				ptr[top._3]++
				if ptr[top._3] == P {
					break loop
				}
				gram := float64(Q[top._3][ptr[top._3]] * 10)
				min := int(math.Ceil(gram / upper[top._3]))
				max := int(math.Floor(gram / lower[top._3]))
				if max < min {
					goto moveptr
				}
				heap.Push(&minPQ, Tuple3{min, max, top._3})
				maxMin = maxInt(maxMin, min)
				maxMax = maxInt(maxMax, max)
			}
			kits++
			for minPQ.Len() != 0 {
				top := heap.Pop(&minPQ).(Tuple3)
				ptr[top._3]++
			}
		}
		fmt.Printf("Case #%d: %d\n", tc, kits)
	}
}

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