Canadian Computing Competition: 2007 Stage 2, Day 2, Problem 1
Politicians like to get elected. They will do just about anything to get elected. Including changing the rules of the voting: who can vote, where you can vote, when you can vote, etc. One very common practice is called gerrymandering, where the boundaries of "ridings" are redrawn to favour a particular candidate (the one doing the redrawing, of course).
Your task is to help determine how to do some simple, linear gerrymandering.
You will be given the information about ridings where there are candidates from different parties. These ridings are linear, in the sense that they are side-by-side; there are two ridings (on the ends) that have only one adjacent riding, with the rest of the ridings having two adjacent ridings. A picture is shown below for and (which is also the sample data):
|Riding 1||Riding 2||Riding 3||Riding 4|
|Votes for Party 1||1||4||1||6|
|Votes for Party 2||5||3||2||1|
Note that Riding 1 and Riding 2 are adjacent, Riding 2 and 3 are adjacent, Riding 3 and 4 are adjacent. No other ridings are adjacent.
You have some financial backing that will let you bribe the people in charge of setting the boundaries of ridings: in particular, there is a fixed rate to merge two adjacent boundaries. When you merge two ridings, the votes of the ridings merge together, in the sense that the number of votes of party 1 is the sum of the votes of party 1 in each riding, and likewise for all other parties.
Your task is to merge the minimum number of regions such that the first party (your party!) has a majority of the ridings. Note that to win a riding, the party must have more votes than any other party in that riding. Also note that to have a majority of ridings, if there are ridings (where ), then your party has won at least of the ridings.
The first line of input will consist of the integer . The second line of input will consist of the integer . The next lines will each contain non-negative integers (where each integer is at most ), separated by one space character. Specifically, the integers on each line are where is the number of votes that party will receive in this riding, is the number of votes that party will receive in this riding, etc.
You may also assume that the total number of voters is less than 2 billion.
One line, consisting of an integer, which gives the minimum number of ridings that need to be merged in order for the first party to win a majority of ridings. If the first party cannot win, even with any number of mergers, output
Sample Input 1
4 2 1 5 4 3 1 2 6 1
Sample Output 1
Sample Input 2
3 3 2 0 1 1 3 0 0 0 1
Sample Output 2