停课集训Day2

题目是上海市NOI2008选拔赛的原题。我把它发在下面，同时您还能在我的网络硬盘里找到Word版本。不清楚此试题的版权情况，如版权所有者不希望试题被公布，请尽快联系我，我会在第一时间内删除。

循环的债务 Debt
【问题描述】
Alice、Bob和Cynthia总是为他们之间混乱的债务而烦恼，终于有一天，他们决定坐下来一起解决这个问题。不过，鉴别钞票的真伪是一件很麻烦的事情，于是他们决定要在清还债务的时候尽可能少的交换现金。
比如说，Alice欠Bob 10元，而Cynthia和他俩互不相欠。现在假设Alice只有一张50元，Bob有3张10元和10张1元，Cynthia有3张20元。一种比较直接的做法是：Alice将50元交给Bob，而Bob将他身上的钱找给Alice，这样一共就会有14张钞票被交换。但这不是最好的做法，最好的做法是：Alice把50块给Cynthia，Cynthia再把两张20给Alice，另一张20给Bob，而Bob把一张10块给C，此时只有5张钞票被交换过。
没过多久他们就发现这是一个很棘手的问题，于是他们找到了精通数学的你为他们解决这个难题。
【输入文件】
输入的第一行包括三个整数：x1、x2、x3（-1,000≤x1，x2，x3≤1,000），其中
x1代表Alice欠Bob的钱（如果x1是负数，说明Bob欠了Alice的钱）
x2代表Bob欠Cynthia的钱（如果x2是负数，说明Cynthia欠了Bob的钱）
x3代表Cynthia欠Alice的钱（如果x3是负数，说明Alice欠了Cynthia的钱）
接下来有三行，每行包括6个自然数：
a100，a50，a20，a10，a5，a1
b100，b50，b20，b10，b5，b1
c100，c50，c20，c10，c5，c1
a100表示Alice拥有的100元钞票张数，b50表示Bob拥有的50元钞票张数，以此类推。另外，我们保证有a10+a5+a1≤30，b10+b5+b1≤30，c10+c5+c1≤30，而且三人总共拥有的钞票面值总额不会超过1,000。
【输出文件】
如果债务可以还清，则输出需要交换钞票的最少张数；如果不能还清，则输出“impossible”（注意单词全部小写，输出到文件时不要加引号）。
【样例】
10 0 0
0 1 0 0 0 0
0 0 0 3 0 10
0 0 3 0 0 0
输出 5
-10 -10 -10
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
输出 0
【数据规模】
对于30%的数据，x1、x2、x3 ≤ |50|。
对于100%的数据，x1、x2、x3 ≤ |1,000|。

小约翰的游戏 John
【问题描述】
小约翰经常和他的哥哥玩一个非常有趣的游戏：桌子上有n堆石子，小约翰和他的哥哥轮流取石子，每个人取的时候，可以随意选择一堆石子，在这堆石子中取走任意多的石子，但不能一粒石子也不取，我们规定取到最后一粒石子的人算输。
小约翰相当固执，他坚持认为先取的人有很大的优势，所以他总是先取石子，而他的哥哥就聪明多了，他从来没有在游戏中犯过错误。小约翰一怒之前请你来做他的参谋。自然，你应该先写一个程序，预测一下谁将获得游戏的胜利。
【输入文件】
本题的输入由多组数据组成，第一行包括一个整数T，表示输入总共有T组数据（T≤500）。
每组数据的第一行包括一个整数N（N≤50），表示共有N堆石子，接下来有N个不超过5000的整数，分别表示每堆石子的数目。
【输出文件】
每组数据的输出占一行，每行输出一个单词。如果约翰能赢得比赛，则输出“John”，否则输出“Brother”，请注意单词的大小写。
【样例】
2
3
3 5 1
1
1
输出
John
Brother
【数据规模】
对于40%的数据，T ≤ 250。
对于100%的数据，T ≤ 500。

仙人图(II) Cactus
【问题描述】
如果某个无向连通图的任意一条边至多只出现在一条简单回路（simple cycle）里，我们就称这张图为仙人图（cactus）。所谓简单回路就是指在图上不重复经过任何一个顶点的回路。
举例来说，上面的第一个例子是一张仙人图，而第二个不是——注意到它有三条简单回路：（4，3，2，1，6，5，4）、（7，8，9，10，2，3，7）以及（4，3，7，8，9，10，2，1，6，5，4），而（2，3）同时出现在前两个的简单回路里。另外，第三张图也不是仙人图，因为它并不是连通图。
显然，仙人图上的每条边，或者是这张仙人图的桥（bridge），或者在且仅在一个简单回路里，两者必居其一。定义在图上两点之间的距离为这两点之间最短路径的距离。定义一个图的直径为这张图相距最远的两个点的距离。现在我们假定仙人图的每条边的权值都是1，你的任务是求出给定的仙人图的直径。
【输入文件】
输入的第一行包括两个整数n和m（1≤n≤50,000以及0≤m≤10,000）。其中n代表顶点个数，我们约定图中的顶点将从1到n编号。
接下来一共有m行。代表m条路径。每行的开始有一个整数k（2≤k≤1000），代表在这条路径上的顶点个数。接下来是k个1到n之间的整数，分别对应了一个顶点，相邻的顶点表示存在一条连接这两个顶点的边。一条路径上可能通过一个顶点好几次，比如对于第一个样例，第一条路径从3经过8，又从8返回到了3，但是我们保证所有的边都会出现在某条路径上，而且不会重复出现在两条路径上，或者在一条路径上出现两次。
【输出文件】
只需输出一个数，这个数表示仙人图的直径长度。
【样例】
15 3
9 1 2 3 4 5 6 7 8 3
7 2 9 10 11 12 13 10
5 2 14 9 15 10
输出 8
10 1
10 1 2 3 4 5 6 7 8 9 10
输出 9
对第一个样例的说明：
如图，6号点和12号点的最短路径长度为8，所以这张图的直径为8。
使用Pascal语言的选手请注意：
你的程序在处理大数据的时候可能会出现栈溢出。如果需要调整栈空间的大小，可以在程序的开头填加一句：{$M 5,000,000}，其中5,000,000即指代栈空间的大小，请根据自己的程序选择适当的数值。
【数据规模】
对于30%的数据，m ≤ 50。
对于100%的数据，m ≤ 1,000。

今天的题目有点难，我还没有全部写过。下面的题解仅用来备忘，希望大牛能提供更好的题解。

循环的债务：听同学说是一个动态规划，用f[i][j]表示Alice有现金i，Bob有现金j需要的代价，然后转移，也有人用BFS过了。我只过了两个点:(

小约翰的游戏：Nim游戏的改编。我当时是画出了[3,3]为起始状态的有向图，根据ICG的定义，手算答案。与经典的Nim游戏答案比较发现，只有在所有状态都为0或1的时候出现不一向。大胆猜测，特判这种情况，居然AC了！后来有同学证明了这是正确的算法。

仙人图(II)：我写的只是裸的枚举根BFS，居然只有10分！数据不厚道，一个小一点的点都没有！这题应该是一个树形动归或者类似的题目，下午大家讨论了大半天，好像是DFS下来，根据是不是环的起点什么的采取不同的操作。求强连通分支然后缩点应该也是可以的吧，只是还是很麻烦？听说太复杂了，我也就顿时失去了写的欲望。另外，这题是欧洲某ACM比赛的原题。

题目和相关数据在这里。