题面

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

最近几天听说有一些实训的小伙伴的项目是做一个黑白棋游戏，于是我也跟风去凑个热闹，权当练练手，锻炼一下写个小项目的能力。断断续续做了两天（因为还有比赛），只做好了基本功能，没有来得及学习 AI 方面的东西，所以实现只能人人对战。

概述

OpenMP 是一套支持跨平台共享内存方式的多线程并发的编程 API。目前，主流 C/C++ 编译器，如 gcc、Visual C++ 等都已内建支持 OpenMP，如果你使用的是目前主流且较新的 Linux 发行版，那么使用 gcc 即可编译 OpenMP 程序。但是对于未安装 Visual C++ 的 Windows 用户和使用 Apple LLVM Clang 编译环境的 OS X (macOS) 用户，OpenMP 就需要额外安装了。本文即介绍上述两种平台下 OpenMP 配置方法。

题面

装备合成
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程序设计竞赛