2018-1A Problem C

Final solution

// package, import, etc...

func start() {
  // read T, repeat test() T times...
}

type Cookie struct {
	w              int
	h              int
	pAdditionalMin float64
	pAdditionalMax float64
}

const eplison float64 = 0.000001

type Interval struct {
	min float64
	max float64
}

func test() {
	var N, P int
	mustReadLineOfInts(&N, &P)
	cookies := make([]Cookie, 0, N)
	for i := 0; i < N; i++ {
		var w, h int
		mustReadLineOfInts(&w, &h)
		cookies = append(cookies, Cookie{
			w: w, h: h,
		})
	}
	var baseP float64
	for i := 0; i < len(cookies); i++ {
		cookie := &cookies[i]
		if cookie.w < cookie.h {
			cookie.w, cookie.h = cookie.h, cookie.w
		}
		cookieP := 2 * (cookie.w + cookie.h)
		cookie.pAdditionalMin = float64(2*(cookie.w+2*cookie.h) - cookieP)
		cookie.pAdditionalMax = 2*(float64(cookie.w+cookie.h)+float64(math.Sqrt(float64(cookie.w*cookie.w+cookie.h*cookie.h)))) - float64(cookieP)
		baseP += float64(cookieP)
	}
	addIntervals := make(IntervalArray, 0)
	addIntervals = append(addIntervals, Interval{0, 0}) // In the loop below, each cookie would have a chance for its addMin, addMax to be added to this 0, 0 interval, representing the case where only that cookie is cutted.
	maxMin := float64(P) - baseP
	if maxMin < eplison {
		fmt.Fprintf(stdout, "%.15f\n", float64(P))
		return
	}
	for i := 0; i < len(cookies); i++ {
		cookie := &cookies[i]
		// Either don't cut this cookie, in which case intervals are untouched, or...
		for _, interval := range addIntervals {
			addIntervals = append(addIntervals, Interval{interval.min + cookie.pAdditionalMin, interval.max + cookie.pAdditionalMax})
		}
		mergeIntervals(&addIntervals, maxMin)
	}
	lastInterval := addIntervals[len(addIntervals)-1]
	maxP := lastInterval.max + baseP
	if maxP > float64(P) {
		fmt.Fprintf(stdout, "%.15f\n", float64(P))
	} else {
		fmt.Fprintf(stdout, "%.15f\n", maxP)
	}
}

type IntervalArray []Interval

func (its IntervalArray) Len() int {
	return len(its)
}

func (its IntervalArray) Less(i int, j int) bool {
	return its[i].min < its[j].min
}

func (its IntervalArray) Swap(i int, j int) {
	its[i], its[j] = its[j], its[i]
}

func mergeIntervals(its *IntervalArray, maxMin float64) {
	if len(*its) == 0 {
		return
	}
	sort.Sort(*its)
	if (*its)[0].min > maxMin {
		*its = make(IntervalArray, 0)
		return
	}
	newArr := make(IntervalArray, 0)
	currentStarting := (*its)[0]
	for i := 1; i < len(*its); i++ {
		it := (*its)[i]
		if it.min-eplison > currentStarting.max {
			if it.min > maxMin {
				break
			}
			newArr = append(newArr, currentStarting)
			currentStarting = it
		} else if it.max > currentStarting.max {
			currentStarting.max = it.max
		}
	}
	newArr = append(newArr, currentStarting)
	*its = newArr
}

// boilerplate omitted...

Sample test cases given in question

4
1 7
1 1
2 920
50 120
50 120
1 32
7 4
3 240
10 20
20 30
30 10

Other files

1
4 3551
229 225
240 187
27 67
212 184

Case #1: 3551.000000000000000

16
3 240
20 10
30 20
30 10
3 250
20 10
30 20
30 10
3 260
20 10
30 20
30 10
3 270
20 10
30 20
30 10
3 280
20 10
30 20
30 10
3 290
20 10
30 20
30 10
3 300
20 10
30 20
30 10
3 240
20 10
20 10
20 10
3 250
20 10
20 10
20 10
3 260
20 10
20 10
20 10
3 270
20 10
20 10
20 10
3 280
20 10
20 10
20 10
3 300
20 10
20 10
20 10
3 400
20 10
20 10
20 10
3 430
20 10
30 20
30 10
4 1000
20 10
30 20
30 10
100 50

Case #1: 240.000000000000000
Case #2: 240.000000000000000
Case #3: 260.000000000000000
Case #4: 270.000000000000000
Case #5: 280.000000000000000
Case #6: 290.000000000000000
Case #7: 300.000000000000000
Case #8: 240.000000000000000
Case #9: 250.000000000000000
Case #10: 260.000000000000000
Case #11: 270.000000000000000
Case #12: 280.000000000000000
Case #13: 300.000000000000000
Case #14: 314.164078649987403
Case #15: 420.077938262643158
Case #16: 943.684736012622125

// package, import, etc...

func main() {
	fin, err := os.OpenFile("generated.in", os.O_WRONLY|os.O_CREATE, 0666)
	finHelp, err := os.OpenFile("generated.in.wcomment", os.O_WRONLY|os.O_CREATE, 0666)
	if err != nil {
		panic(err)
	}
	in := bufio.NewWriter(fin)
	inHelp := bufio.NewWriter(finHelp)
	t := 10000
	fmt.Fprintf(in, "%d\n", t)
	fmt.Fprintf(inHelp, "%d\n", t)
	type Cookie struct {
		w int
		h int
	}
	for i := 0; i < t; i++ {
		var P int = 0
		var maxP float64 = 0
		N := rand.Intn(10) + 1
		cookies := make([]Cookie, 0, N)
		for c := 0; c < N; c++ {
			cookie := Cookie{
				w: rand.Intn(249) + 1,
				h: rand.Intn(249) + 1,
			}
			cookies = append(cookies, cookie)
			P += 2 * (cookie.w + cookie.h)
			maxP += 2 * (float64(cookie.w) + float64(cookie.h) + math.Sqrt(float64(cookie.w*cookie.w)+float64(cookie.h*cookie.h)))
		}
		if rand.Intn(2) == 1 {
			P += rand.Intn(int(maxP-float64(P)) * 2)
		}
		fmt.Fprintf(in, "%d %d\n", N, P)
		fmt.Fprintf(inHelp, "%d %d // Start case %d\n", N, P, i+1)
		for _, cookie := range cookies {
			fmt.Fprintf(in, "%d %d\n", cookie.w, cookie.h)
			fmt.Fprintf(inHelp, "%d %d\n", cookie.w, cookie.h)
		}
	}
	in.Flush()
	inHelp.Flush()
}