题面

Flip Game
Time Limit: 1000MS Memory Limit: 65536K

Description

Flip game is played on a rectangular 4x4 field with two-sided pieces placed on each of its 16 squares. One side of each piece is white and the other one is black and each piece is lying either it's black or white side up. Each round you flip 3 to 5 pieces, thus changing the color of their upper side from black to white and vice versa. The pieces to be flipped are chosen every round according to the following rules:

1. Choose any one of the 16 pieces.
2. Flip the chosen piece and also all adjacent pieces to the left, to the right, to the top, and to the bottom of the chosen piece (if there are any).

Consider the following position as an example:

bwbw
wwww
bbwb
bwwb
Here "b" denotes pieces lying their black side up and "w" denotes pieces lying their white side up. If we choose to flip the 1st piece from the 3rd row (this choice is shown at the picture), then the field will become:

bwbw
bwww
wwwb
wwwb
The goal of the game is to flip either all pieces white side up or all pieces black side up. You are to write a program that will search for the minimum number of rounds needed to achieve this goal.

Input

The input consists of 4 lines with 4 characters "w" or "b" each that denote game field position.

Output

Write to the output file a single integer number - the minimum number of rounds needed to achieve the goal of the game from the given position. If the goal is initially achieved, then write 0. If it's impossible to achieve the goal, then write the word "Impossible" (without quotes).

Sample Input

bwwb
bbwb
bwwb
bwww

Sample Output

4

Source

Northeastern Europe 2000

题面

装备合成
Time Limit: 1000MS Memory limit: 65536K

题目描述
小白很喜欢玩儿LOL，但是无奈自己是个坑货，特别是在装备的选择和合成上，总是站在泉水里为选装备而浪费时间。现在小白试图解决这个问题，为了使问题简单化，我们把游戏中的装备合成规则简化如下：
（1）装备的合成关系构成一棵合成关系树，如图(a)所示，装备的下级装备叫合成小件，直接连接的叫直接合成小件；上级装备叫合成件，直接连接的叫直接合成件。合成树上的每件装备都可以直接购买，如果钱不够也可以先购买这个装备的合成小件。
（2）每个装备都有一个合成价格和一个总价格，装备的总价格=该装备的合成价格+该装备所有直接合成小件的总价格之和（图(a)关系树上面显示的数字就是对应装备的总价格）。
（3）初始的时候（未拥有装备的任何部分），装备的当前价格等于总价格，当前价格会随着购买的小件而发生相应的变化。
（4）如果购买了某个装备，那么它所有上级可合成装备的当前价格都会相应地减少，减少的量等于这个装备的当前价格。
（5）如果购买了某个装备，那么它下级所有合成小件都会被购买，也就是说，这些小件都变成已拥有的状态，但是物品栏里只有最终合成的装备，因为是小件合成了这件装备。
（6）我们认为关系树上的每个装备的直接合成小件都不超过2件，关系树上同一件物品只会出现一次，我们也不考虑物品的出售问题，我们假设物品栏容量无限，金钱无限。

现在问题来了，按照格式给定一棵合成关系树，再给定一系列操作，完成相应的查询，具体格式见输入。

输入
多组输入，对于每组数据：
第一行有两个整数n m，分别代表关系树中物品的数量和后续的操作数。（1 <= n,m <= 10^4）
接下来的n行，每行对应一件物品的描述，格式为equipment p k，分别代表装备的名称，合成价格，直接合成小件的个数，然后有k个合成小件的名称synthesis1 synthesis2 ... synthesisk。（1 <= p <=10^4 , k <= 2 , 所有物品名称只包含小写英文字母，长度不超过20）
接下来的m行，每行对应一个操作，格式如下：
（1）B equipment ，表示物品equipment被购买。
（2）Q equipment ，表示要查询物品equipment的当前价格。
其中equipment代表物品的名称，保证合法且存在于合成关系树中。
注意：如果B指令购买的装备是当前已经拥有的装备（包括小件），那么忽略该条B购买指令。特别地，如果你已经拥有某件装备，那么查询该物品的当前价格时应该输出这件物品的总价格而不是0

输出
对于每次Q查询指令，输出一个整数，代表查询的物品的当前价格。

示例输入
8 10
bannerofcommand 600 2 aegisofthelegion fiendishcodex
aegisofthelegion 400 2 nullmagicmantle crystallinebracer
fiendishcodex 465 1 amplifyingtome
nullmagicmantle 450 0
crystallinebracer 100 2 rubycrystal rejuvenationbead
amplifyingtome 435 0
rubycrystal 400 0
rejuvenationbead 150 0
B crystallinebracer
Q fiendishcodex
Q bannerofcommand
B nullmagicmantle
Q aegisofthelegion
B aegisofthelegion
Q bannerofcommand
Q crystallinebracer
B bannerofcommand
Q bannerofcommand

示例输出
900
2350
400
1500
650
3000

提示

来源
“师创杯”山东理工大学第八届ACM程序设计竞赛
*/

题面

数列求和2
Time Limit: 1000MS Memory limit: 65536K

题目描述
给出一个数列 S 1, S 2, S 3, S 4 ... S x, ... S n (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ S x ≤ 32767). 我们定义 sum(i, j) = S i +S i+1+ ... + S j (1 ≤ i ≤ j ≤ n).
现在给你一个整数 m (n>=m > 0), 你的任务是找出m对 i，j 使 sum(i 1, j 1) + sum(i 2, j 2) + sum(i 3, j 3) + ... + sum(i m, j m) 最大化 (i x ≤ i y ≤ j x 或 i x ≤ j y ≤ j x 是不允许的).
结果仅输出sum(i x, j x)的最大累加和(1 ≤ x ≤ m) 就行了.

输入
包含多组数据，每组数据占一行，前两个整数是m和n，后面紧跟着是n个整数S 1, S 2, S 3 ... S n.

输出
输出所描述的结果，每一组的结果占一行

示例输入
1 3 1 2 3
2 6 -1 4 -2 3 -2 3

示例输出
6
8

提示

来源
“师创杯”山东理工大学第八届ACM程序设计竞赛

题面

疯狂的小金
Time Limit: 1000MS Memory limit: 65536K

题目描述
自从听说小白和小黑的友谊的小船翻了以后，小金很是开心，就和小白建立了小船，但是现在小金看到天上的n只小鸟，就萌生了一个疯狂的想法，他决定带着小白去打鸟，所以小金去商店买装备--->箭，现在他知道每只鸟的防御力，和每一只箭的攻击力和价值。如果箭的攻击力小于鸟的防御了，小鸟是不会被打下来的。最为奇葩的是每种箭只有一只，小金想将小鸟都打下来，如果不能那么小金和小白的小船又要翻啦。当然小金的资金最近比较的紧张，所以他想花费最小的钱。

输入
多组输入，每组第一行输入两个数n,m(1<=n,m<=50000)，表示小鸟的数量和箭的数量。接下来的一行的n个数表示每一个小鸟的防御力，接下来的m行，每行两个数，表示箭的攻击力v价值w,(1<=v,w<=100000).

输出
如果小金不能将所有的小鸟射下来，输出"No Solution"。否则输出最小的花费。

示例输入
3 3
1 2 3
2 1
3 2
4 3

示例输出
6

提示

来源
“师创杯”山东理工大学第八届ACM程序设计竞赛

题面

硬币问题
Time Limit: 1000ms Memory limit: 65536K

题目描述
芳芳有N（1<=N<=1000)个硬币，这些硬币排成一列，有正有反。我们定义这样一种操作，把[l,r]区间上的硬币都翻过来(1<=l<=r<=N).
芳芳想知道经过一次这样的操作后，最多有多少正面朝上的。
1代表正面，0代表反面。
比如：0 1 0 三个数，把区间1-3进行操作，数字就会变成1 0 1 正面向上的个数为2.

输入
本题有多组测试数据，每组数据有两行.
第一行包含一个数字N. 第二行有N个数字，1表示正面，0表示反面.

输出
每组数据输出一行.

示例输入
4
1 0 0 1

示例输出
4

提示

来源
第六届山东理工ACM网络编程擂台赛决赛