P1675 [USACO05FEB] Jersey Politics G

In the newest census of Jersey Cows and Holstein Cows, Wisconsincows have earned three stalls in the Barn of Representatives. The Jersey Cows currently control the state's redistricting committee. They want to partition the state into three equally sized voting districts such that the Jersey Cows are guaranteed to win elections in at least two of the districts. Wisconsin has $3K (1 \leq K \leq 60)$ cities of $1,000$ cows, numbered $1\dots 3K$, each with a known number (range: $0\dots 1,000$) of Jersey Cows. Find a way to partition the state into three districts, each with $K$ cities, such that the Jersey Cows have the majority percentage in at least two of districts. All supplied input datasets are solvable.

- Line $1$: A single integer, $K$ - Lines $2\dots 3K+1$: One integer per line, the number of cows in each city that are Jersey Cows. Line $i+1$ contains city $i$'s cow census.

- Lines $1\dots K$: $K$ lines that are the city numbers in district one, one per line - Lines $K+1\dots 2K$: $K$ lines that are the city numbers in district two,one per line - Lines $2K+1\dots 3K$: $K$ lines that are the city numbers in district three, one per line

Other solutions might be possible. Note that `2 3` would NOT be a district won by the Jerseys, as they would be exactly half of the cows.