Problem: subtlesabotage (2017 round2)

Wilson has had quite enough of his job driving trucks for a moving company,
and is now interested in carrying out different sorts of deliveries — namely,
pizza pie deliveries! Unfortunately, his local pizzeria already has a full-
time driver, Mario Crosta, but Wilson has devised a devious plan to sabotage
Mario, hopefully resulting in him getting fired and Wilson taking over.

The pizzeria is located in a town which can be modeled as a grid of cells with
**N** rows and **M** columns, with each cell representing an intersection.
There are at least two intersections (in other words, **N** * **M** ≥ 2). It's
possible to drive from a given intersection to any adjacent intersection
(directly up, down, left, or right) in 1 minute. It's not possible to leave
the grid.

The pizzeria is located at the top-left intersection, and Wilson is planning
on placing an order for pizza to be delivered to the bottom-right
intersection. Due to the paramount importance of pizza arriving while it's
still hot, this pizzeria guarantees that their deliveries will always arrive
within at most **N** \+ **M** \- 2 minutes (or the customer will get their
money back and also the driver will be immediately fired). Ordinarily, this is
just enough time to reach even the bottom-right corner of the town, but Wilson
intends to make this not an ordinary delivery.

Before placing his order, Wilson will pull some strings and arrange to have
some of the intersections blocked off. In particular, he can shut down an
entire axis-aligned **K**x**K** square of intersections all at once. He can
even choose multiple such squares, as long as all of them lie entirely within
the grid, none of them overlap with one another, and none of them include the
top-left or bottom-right intersections. When he's done, Mario will be unable
to pass through any intersection which is part of any of the squares.

Wilson doesn't want to block off so many intersections that Mario will be
unable to complete his delivery at all, as that would likely be too obvious.
Instead, he wants to make sure that the delivery is still possible but is
forced to take longer than **N** \+ **M** \- 2 minutes, resulting in Mario
losing his job.

Despite his vast network of connections with corrupt government officials,
shutting down each square of intersections will still cost Wilson a fair sum
of money, so he'd like to successfully complete his sabotage by blocking off
as few squares as possible. Unfortunately, it also might be the case that no
possible set of squares can result in Mario's delivery taking too long without
making the delivery impossible.

On the 8x8 grid below, for example, if Wilson blocks off six 2x2 squares of
intersections as shown (in black), the shortest possible delivery route from
the pizzeria to the bottom-right intersection (in red) will take 22 minutes,
which is longer than 8 + 8 - 2 = 14 minutes. However, note that this solution
is not optimal.

![]({{PHOTO_ID:261299628624564}})

### Input

Input begins with an integer **T**, the number of different pizzerias Wilson
wants to work for. For each pizzeria, there is a single line containing the
three space-separated integers, **N**, **M**, and **K**.

### Output

For the _i_th truck, print a line containing "Case #**i**: " followed by the
minimum number of blocked-off squares required for Wilson to successfully
sabotage Mario (or -1 if it can't be done).

### Constraints

1 ≤ **T** ≤ 10,000  
1 ≤ **N**, **M**, **K** ≤ 800,000  

### Explanation of Sample

In the first case, if both the top-right and bottom-left intersections are
blocked off, then the bottom-right corner will be unreachable from the
pizzeria, which is no good. If only one of those cells is blocked off, then
Mario can proceed through the other one, managing to still complete his
delivery in 2 + 2 - 2 = 2 minutes. Therefore Wilson has no way to sabotage him
successfully.



Sample input:
5
2 2 1
4 5 1
6 6 1
6 6 2
773632 635271 223841


Sample output:
Case #1: -1
Case #2: 4
Case #3: 5
Case #4: -1
Case #5: 3



Code: // Hacker Cup 2017
// Round 2
// Subtle Sabotage
// Jacob Plachta

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }

const int INF = (int)1e9;
const LD EPS = 1e-9;
const LD PI = acos(-1.0);

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=getchar();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

int main()
{
	int T,t;
	int N,M,K;
	int ans;
	Read(T);
		Fox1(t,T)
		{
			Read(N),Read(M),Read(K);
				if (N>M)
					swap(N,M);
			ans=INF;
				if ((K+1<=N) && (K*2+3<=M))
					Min(ans,(N-1)/K+1);
				if ((K*2+1<=N) && (K*2+3<=M))
					Min(ans,K==1 ? 5 : 4);
				if (ans==INF)
					ans=-1;
			printf("Case #%d: %d\n",t,ans);
		}
	return(0);
}