puzzle - 圆求和(30 分)InterviewStree Puzzle

Question

以下是来自Interviewstreet的问题我没有从他们的网站上得到任何帮助，所以在这里提问。我对算法/解决方案不感兴趣，但我不理解他们作为第二个输入示例给出的解决方案。任何人都可以帮助我理解问题陈述中指定的第二个输入和输出。

圆求和(30 分)

有N children 围成一圈，编号1,2,...,N顺时针。 ith child 有一张纸，上面写着 ai写在上面。他们玩以下游戏:

第一轮， child 编号x将他的邻居人数的总和加到他的人数上。

在第二轮中，接下来的 child 按顺时针顺序将他的邻居的数字之和加到他的数字上，依此类推。

游戏结束后M已经打了几轮。

输入:
第一行包含 T ，测试用例的数量。 T案例如下。测试用例的第一行包含两个空格分隔的整数 N和 M .下一行包含 N整数，ith号码是 ai .

输出:
对于每个测试用例，输出 N 行，每行有 N 个整数。 jth ith 上的整数line 包含如果游戏以 child i 开始，则第 j 个 child 结束的数字。打第一轮。除最后一个测试用异常(exception)，每个测试用例后输出一个空行。由于数字可能非常大，输出它们模1000000007 .

约束:

1 <= T <= 15
3 <= N <= 50
1 <= M <= 10^9
1 <= ai <= 10^9

样本输入:

2
5 1
10 20 30 40 50
3 4
1 2 1

示例输出:

80 20 30 40 50
10 60 30 40 50
10 20 90 40 50
10 20 30 120 50
10 20 30 40 100



23 7 12
11 21 6
7 13 24 

Answer 1

下面是对第二个测试用例的解释。我将使用符号 (a, b, c) 表示 child 一有数字 a， child 二有数字 b， child 三有数字 c。一开始，位置总是 (1,2,1)。

如果第一个 child 是第一个对其邻居求和的，则该表会经历以下情况(我将在刚刚将其两个相邻数字相加的 child 前面加一个星号):

(1,2,1)->(*4,2,1)->(4,*7,1)->(4,7,*12)->(*23,7,12)

如果第二个 child 是第一个移动的:

(1,2,1)->(1,*4,1)->(1,4,*6)->(*11,4,6)->(11,*21,6)

最后，如果第三个 child 首先移动:

(1,2,1)->(1,2,*4)->(*7,2,4)->(7,*13,4)->(7,13,*24)

正如您注意到的那样，第二种情况的输出正是以这种方式计算的三个三元组。

希望有帮助。