问题 1: Cowvin Bacon 的六度 (分离) [Tom Widland, 2003]

牛们最近一直在拍电影, 因此她们准备好来玩著名游戏 "Kevin Bacon 的
六度 (分离)" 的一个变化版本.

游戏是这样的: 每个牛被认为与她自己是零度分离. 如果两个不同的牛曾同在
某个电影里, 每个就被认为与另一个是一 '度' 远.  如果某对牛从未共同合作
过但都曾与第三头牛合作过, 她们将被认为彼此是二 '度' 远 (这样数: 一度到
她们曾与之合作的牛那里, 再一度才到另一个牛那里). 这种度量方法适用于一
般情况.

N (2 <= N <= 300) 头牛有兴趣找出他们哪头与所有其他牛有最小的平均分离度, 当
然不算她自己. 牛们已经拍了 M (1 <= M <= 10000) 部电影, 并保证每对牛之
间都存在一些关系路径.

问题名: bacon

输入格式:

* 行 1: 空格分开的两个整数: N 和 M

* 行 2..M+1: 每个输入行包括一组空格分开的两个或更多个整数, 描述了在一
        个电影中露面的牛们. 第一个整数是参与该部电影的牛的个数,
        (即, Mi); 其后的 Mi 个整数告诉我们都是哪些牛.

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

4 2
3 1 2 3
2 3 4

输出格式:

* 行 1: 唯一的整数: (任何牛的平均分离度中最小的)*100.

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

100

[牛 3 曾与所有其他的牛合作过因此有分离度: 1, 1, 和 1 -- 平均 1.00 .]

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

问题 2: 牧群总数 [Don Piele, 2003]

农场主 John 的牧群中的牛被以连续整数从 1 到 N (1 <= N <= 10000) 编号挂
牌.  当这些牛来棚舍挤奶时, 总是连续有序地从 1 到 N 排队来.

John, 在读大学时主修数学并非常喜欢数字, 他经常寻找数字模板.  他注意到
当他的牧群有正好 15 头牛时, 有正好四种方式可以在一个或多个连续的牛上加
出 15 (和牛的总数一样) 来.  他们是: 15, 7+8, 4+5+6, 和 1+2+3+4+5.

当牧群中牛的数目为 10 时, 他能在连续的牛上加出 10 的办法降低到 2 种,
即 1+2+3+4 和 10.

写一个程序来计算 John 有几种办法能在连续的牛上加出等于 N 的数,
N <= 10,000,000.
不要用预先计算来答这道题.

问题名: hsums

输入格式:

* 行 1: 一个整数: N

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

15

输出格式:

* 行 1: 一个整数: 在连续的牛的标号上可以加出 N 这个数的办法个数.

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

4

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

问题 3: 消息解牛 (不是解码或解马) [传统类型, 2003]

牛们激动得发抖, 因为他们刚刚学习到了如何加密消息. 他们想他们将能用密信
密谋与其他农场上的牛们相汇.

牛们的智利不为大家所周知. 他们的加密法可比不上 DES 或者 BlowFish 或任
何那些真正好的加密方法. 比不上, 他们正使用一种简单的置换密码.

牛们有一个密钥和一个密信. 请帮他们解密. 密钥就像这样:

        yrwhsoujgcxqbativndfezmlpk

意思是密信中的一个 'a' 实际是 'y'; 一个输入消息里的 'b' 实际是 'r'; 一个
'c' 解释成 'w'; ...
空格不被加密, 他们简单地呆在原来的位置.

输入文本是大写或小写的, 都以同样的密钥来解密, 当然也保持原来的大小写.

问题名: decode

输入格式:

* 行 1: 26 个小写字符代表密钥

* 行 2: 最多 80 个字符作为要被解密的消息

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

eydbkmiqugjxlvtzpnwohracsf
Kifq oua zarxa suar bti yaagrj fa xtfgrj

输出格式:

* 行 1: 简单的一行解密后的消息. 它应该与输入的第二行有同样的长度.

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

Jump the fence when you seeing me coming

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

**********************************************************************
                           ORANGE PROBLEMS
**********************************************************************
                 Three problems numbered 6 through 8
**********************************************************************

PROBLEM 6: Six Degrees of Cowvin Bacon [Tom Widland, 2003]

The cows have been making movies lately, so they are ready to play a
variant of the famous game "Six Degrees of Kevin Bacon".

The game works like this: each cow is considered to be zero degrees
of separation (degrees) away from herself. If two distinct cows have
been in a movie together, each is considered to be one 'degree' away
from the other.  If a two cows have never worked together but have
both worked with a third cow, they are considered to be two 'degrees'
away from each other (counted as: one degree to the cow they've worked
with and one more to the other cow).  This scales to the general case.

The N (2 <= N <= 300) cows are interested in figuring out which cow
has the smallest average degree of separation from all the other cows.
excluding herself of course. The cows have made M (1 <= M <= 10000)
movies and it is guaranteed that some relationship path exists between
every pair of cows.

PROBLEM NAME: bacon

INPUT FORMAT:

* Line 1: Two space-separated integers: N and M

* Lines 2..M+1: Each input line contains a set of two or more
        space-separated integers that describes the cows appearing in
        a single movie.  The first integer is the number of cows
        participating in the described movie, (e.g., Mi); the
        subsequent Mi integers tell which cows were.

SAMPLE INPUT (file bacon.in):

4 2
3 1 2 3
2 3 4

OUTPUT FORMAT:

* Line 1: A single integer that is 100 times the shortest mean degree
        of separation of any of the cows.

SAMPLE OUTPUT (file bacon.out):

100

[Cow 3 has worked with all the other cows and thus has degrees of
separation: 1, 1, and 1 -- a mean of 1.00 .]

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

PROBLEM 7: Herd Sums [Don Piele, 2003]

The cows in farmer John's herd are numbered and branded with
consecutive integers from 1 to N (1 <= N <= 10,000,000).  When the
cows come to the barn for milking, they always come in sequential
order from 1 to N.

Farmer John, who majored in mathematics in college and loves numbers,
often looks for patterns.  He has noticed that when he has exactly 15
cows in his herd, there are precisely four ways that the numbers on
any set of one or more consecutive cows can add up to 15 (the same as
the total number of cows).  They are: 15, 7+8, 4+5+6, and 1+2+3+4+5.

When the number of cows in the herd is 10, the number of ways he can
sum consecutive cows and get 10 drops to 2: namely 1+2+3+4 and 10.

Write a program that will compute the number of ways farmer John can
sum the numbers on consecutive cows to equal N.  Do not use
precomputation to solve this problem.

PROBLEM NAME: hsums

INPUT FORMAT:

* Line 1: A single integer: N

SAMPLE INPUT (file hsums.in):

15

OUTPUT FORMAT:

* Line 1: A single integer that is the number of ways consecutive cow
        brands can sum to N.

SAMPLE OUTPUT (file hsums.out):

4

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

PROBLEM 8: Message Decowding [Traditional, 2003]

The cows are thrilled because they've just learned about encrypting
messages.  They think they will be able to use secret messages to
plot meetings with cows on other farms.

Cows are not known for their intelligence.  Their encryption method
is nothing like DES or BlowFish or any of those really good secret
coding methods.  No, they are using a simple substitution cipher.

The cows have a decryption key and a secret message.  Help them decode
it.  The key looks like this:

        yrwhsoujgcxqbativndfezmlpk

Which means that an 'a' in the secret message really means 'y'; a 'b'
in the secret message really means 'r'; a 'c' decrypts to 'w'; and so
on.  Blanks are not encrypted; they are simply kept in place.

Input text is in upper or lower case, both decrypt using the same
decryption key, keeping the appropriate case, of course.

PROBLEM NAME: decode

INPUT FORMAT:

* Line 1: 26 lower case characters representing the decryption key

* Line 2: As many as 80 characters that are the message to be decoded

SAMPLE INPUT (file decode.in):

eydbkmiqugjxlvtzpnwohracsf
Kifq oua zarxa suar bti yaagrj fa xtfgrj

OUTPUT FORMAT:

* Line 1: A single line that is the decoded message.  It should have
        the same length as the second line of input.

SAMPLE OUTPUT (file decode.out):

Jump the fence when you seeing me coming

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