问题 1: TwoFour [罗马尼亚奥林匹克, via Stroe, 2002]

Bessie 有一个新的两人游戏: TwoFour. 她有 N (3 <= N <= 30)
堆球, 每堆有 nballs (0 <= nballs <= 4) 个.  球的总数为 2*N.

玩这个游戏时, 游戏者轮流执行一个有效移动. 一个有效移动由下列动作组成:

  * 第一, 游戏者选择不同的两堆球.

  * 第二, 把一个球从一堆拿到另一堆. 她可以这样做的前提是运完球后第二堆
    的球数 (包括新放上的球) 不大于第一堆剩下的球的数目.

当没有移动可做时, 游戏结束. 实际上, 在游戏的末尾, 每堆将包含恰好两个球.

游戏的胜者 '拥有' 多数球堆.  平局是可能的. 当某堆有两个球并且是由于
某游戏者最近对它的的一次移动 (不管移走还是放入) 使其变为两个球的,
我们就说她 '拥有' 这堆球.

看看这些例子:

    * 如果一个游戏者从有四个球的某球堆中移走一个球,
      放到有一个球的某球堆中, 那么它拥有了第二堆 (有两个球).

    * 如果一个游戏者从有三个球的某球堆中移走一个球,
      放到有零个球的某球堆中, 那么它拥有了第一堆, 现在这堆有两个球.

    * 如果一个游戏者从有三个球的某球堆中移走一个球,
      放到有一个球的某球堆中, 那么它拥有了这两堆 (他们都有两个球).

拥有权能够变化. 设想一个游戏者拥有两个球的一个球堆, 如果另一个
游戏者选了一个有四个球的堆并把一个球移到此两个球的堆中,
那么这堆球谁也不属于了.

如果, 在游戏的开头, 存在有两个球的一些球堆, 那么这些堆被平分给两个
游戏者, 剩余的堆则分给游戏者 2.

游戏者 1 先移动.

你的程序必须判断, 对一个初始的游戏状态, 谁将获胜或者会否出现平局.
你的程序将处理 G (1 <= G <= 1000) 个游戏状态.

该问题要求使用不超过 1.00 MB 的内存.

问题名: twofour

输入格式:

* 行 1: 用空格隔开的两个整数: N 和 G.

* 行 2..G+1: 每行包含空格隔开的 N 个整数用于描述该游戏. 
        第一个整数是堆 1 的球数,
        第二个整数是堆 2 的球数,
        ...
        行 2 描述了游戏 1, 行 3 描述了游戏 2,
        ...
        你的程序应该计算每个特定游戏的胜者.

输入样例 (文件 twofour.in):

5 4
0 3 4 1 2
2 2 2 2 2
1 1 2 2 4
4 3 2 1 0

输出格式:

* 行 1..G: 每个游戏的结果.
        行 1 给出游戏 1 的结果, ... 
        结果是一个整数: 1 代表第一个游戏者获胜, 2 代表第二个获胜,
        以及 0 代表平局.

输出样例 (文件 twofour.out):

1
2
1
1

**********************************************************************

问题 2: 最佳牛栏 [Brian Dean, 2003]

农场主 John (简称 FJ) 的农场有一长排的 N (1 <= N <= 100,000)
块地组成.  每块地有一定数量 (ncows) 的牛, 1 <= ncows <=
2000.

FJ 想修建环绕邻接的一组地块的栅栏,
以最大化这组地块中平均每块地中牛的个数.
这组地块必须包含至少 F (1 <= F <= N) 块地, F 作为输入给出.

给定约束, 计算出栅栏的布置情况以最大化平均数. 

问题名: cowfnc

输入格式:

* 行 1: 空格分隔的两个整数, N 和 F.

* 行 2..N+1: 每行包含一个整数, 一块地中的牛数.
        行 2 给出地块 1 中的牛数,
        行 3 给出地块 2 中的牛数,
        ...

输入样例 (文件 cowfnc.in):

10 6
6
4
2
10
3
8
5
9
4
1

输出格式:

* 行 1: 一个整数, 它是最大平均数的 1000 倍.
不要用舍入求整, 仅仅输出整数 1000*ncows/nfields.

输出样例 (文件 cowfnc.out):

6500

**********************************************************************

问题 3: 玉米地 [Brian Dean, 2003]

FJ 已经决定培育他自己的玉米杂交品种以帮助他的牛产出可能最好的奶. 
为此, 他希望在他能找到的最平的一块地上建立其玉米田.

FJ 已经, 以很大的代价, 测量了其 N x N 公顷的正方形农场,
1 <= N <= 250. 每公顷由与之关联的一个整数海拔数 elevation,
0 <= elevation <= 250.

FJ 将提交给你的程序这些海拔数和一组 K (1<= K <= 100,000) 个这种形式的询问:
"在这个 B x B 的子阵列中, 最大和最小海拔是什么?". 
整数 B (1 <= B <= N) 是正方形玉米田的一条边的长度并且对每次询问
都是个常数.

请帮助 FJ 找到最好的地方来安置他的玉米田.

问题名: cornfld

输入格式:

* 行 1: 空格分开的三个整数: N, B, 和 K.

* 行 2..N+1: 每行包括空格分开的 N 各整数. 
        行 2 表示阵列行 1; 行 3 代表阵列行 2, ... 
        每个输入行的第一个整数表示列 1; 第二个表示列 2; ...

* 行 N+2..N+K+1: 每行包含空格分开的两个整数,
        代表一次询问. 第一个整数是所询问阵列的顶行;
        第二个整数是所询问的最左列.
        这些整数在 1..N-B+1 内.

输入样例 (文件 cornfld.in):

5 3 1
5 1 2 6 3
1 3 5 2 7
7 2 4 6 1
9 9 8 6 5
0 6 9 3 9
1 2

输出格式:

* 行 1..K: 每行只有一个整数, 表示每次询问所得的最大数与最小数的差.

输出样例 (文件 cornfld.out):

5

**********************************************************************
FT Institute (FTGroup@21cn.com)

**********************************************************************
                           GREEN PROBLEMS
**********************************************************************
                  Three problems numbered 1 through 3
**********************************************************************

PROBLEM 1: TwoFour [Romanian Olympiad, via Stroe, 2002]

Bessie has a new two-person game: TwoFour. She has N (3 <= N <= 30)
piles, each with a number of balls (0 <= nballs <= 4).  The total
number of balls is 2*N.

To play, the players alternate taking turns, each of which comprises
a single valid move.  A valid move consists of the following actions:

  * First, the player chooses two different piles.

  * Second, she takes a single ball from one pile and moves it to the
    other pile. She can do this only if the number of balls in the
    second pile (including the new ball) is not greater than the
    number of balls remaining in the first pile after the ball is
    removed.

The game ends when no more moves can be made. In fact, at the end of
the game, every pile will contain exactly two balls.

The winner of the game is the player who 'owns' most piles.  Ties are
possible.  A player 'owns' a pile if the pile has two balls and this
resulted from the player's most recent move to or form that pile.
Consider these examples:

    * If a player moves a ball from a pile of four balls to a pile of
      one ball, then she owns the second pile (with two balls).

    * If a player moves a ball from a pile of three balls to a pile
      of zero balls, then she owns the first pile, now with two balls.

    * If a player moves a ball from a pile of three balls to a pile
      of one ball, then she owns both piles (both with two balls).

Ownership can change.  Consider that a player owns a pile with two
balls. If the other chooses a pile with four balls and moves a ball
to the pile with two, then the pile is no longer owned by anyone.

If, at the beginning of the game, some piles have two balls, then the
piles are equally distributed among the two players with any extra
pile being owned by player two.

Player 1 is the one who makes the first move.

Your program must decide, for an initial game state, who will be the
winner or if the game ends in a tie when both players play as well as
they can.  Your program will be presented with G (1 <= G <= 1000) game
states.

Use no more than 1.00 Megabytes of memory for this problem.

PROBLEM NAME: twofour

INPUT FORMAT:

* Line 1: Two space-separated integers: N and G.

* Lines 2..G+1: Each line contains N space-separated integers
        describing a game.  The first integer is the number of  balls
        in pile 1, the second integer is the number of balls in pile
        2, and so on. Line 2 describes game 1, line 3 describes game
        2, and so on.  Your program should compute the winner for this
        particular game.

SAMPLE INPUT (file twofour.in):

5 4
0 3 4 1 2
2 2 2 2 2
1 1 2 2 4
4 3 2 1 0

OUTPUT FORMAT:

* Lines 1..G: The outcome of each game.  Line 1 gives the outcome of
 game 1, and so on.  The outcome is a single integer: 1 if the
 first player wins, 2 if the second player wins, and 0 if the
 game is a tie.

SAMPLE OUTPUT (file twofour.out):

1
2
1
1

**********************************************************************

PROBLEM 2: Best Cow Fences [Brian Dean, 2003]

Farmer John's farm consists of a long row of N (1 <= N <= 100,000)
fields.  Each field contains a certain number of cows, 1 <= ncows <=
2000.

FJ wants to build a fence around a contiguous group of these fields
in order to maximize the average number of cows per field within that
block. The block must contain at least F (1 <= F <= N) fields, where
F given as input.

Calculate the fence placement that maximizes the average, given the
constraint. 

PROBLEM NAME: cowfnc

INPUT FORMAT:

* Line 1: Two space-separated integers, N and F.

* Lines 2..N+1: Each line contains a single integer, the number of
        cows in a field. Line 2 gives the number of cows in field 1,
        line 3 gives the number in field 2, and so on.

SAMPLE INPUT (file cowfnc.in):

10 6
6
4
2
10
3
8
5
9
4
1

OUTPUT FORMAT:

* Line 1: A single integer that is 1000 times the maximal average.
 Do not perform rounding, just print the integer that is
 1000*ncows/nfields.

SAMPLE OUTPUT (file cowfnc.out):

6500

**********************************************************************

PROBLEM 3: Cornfields [Brian Dean, 2003]

FJ has decided to grow his own corn hybrid in order to help the cows
make the best possible milk.  To that end, he's looking to build the
cornfield on the flattest piece of land he can find.

FJ has, at great expense, surveyed his square farm of N x N hectares
(1 <= N <= 250). Each hectare has an integer elevation (0 <= elevation
<= 250) associated with it.

FJ will present your program with the elevations and a set of K (1
<= K <= 100,000) queries of the form "in this B x B submatrix, what
is the maximum and minimum elevation?".  The integer B (1 <= B <= N)
is the size of one edge of the square cornfield and is a constant for
every inquiry. Help FJ find the best place to put his cornfield.

PROBLEM NAME: cornfld

INPUT FORMAT:

* Line 1: Three space-separated integers: N, B, and K.

* Lines 2..N+1: Each line contains N space-separated integers.  Line 2
        represents row 1; line 3 represents row 2, etc.  The first
        integer on each line represents column 1; the second integer
        represents column 2; etc.

* Lines N+2..N+K+1: Each line contains two space-separated integers
        representing a query. The first integer is the top row of the
        query; the second integer is the left column of the query.
        The integers are in the range 1..N-B+1.

SAMPLE INPUT (file cornfld.in):

5 3 1
5 1 2 6 3
1 3 5 2 7
7 2 4 6 1
9 9 8 6 5
0 6 9 3 9
1 2

OUTPUT FORMAT:

* Lines 1..K: A single integer per line representing the difference
        between the max and the min in each query.

SAMPLE OUTPUT (file cornfld.out):

5

**********************************************************************