# I. Mancala

time limit per test：3 seconds

memory limit per test：256 megabytes

input：standard input

output：standard output

Mancala is a traditional board game played in Africa, Middle East and Asia. It is played by two players. This game board consists of two rows of holes, one row for each player. Each row has N holes, and each hole has some non-negative number of stones.

The two players will, in turn, make a move. One move is described as follows:

• the player chooses one of the holes in his row and takes all the stones from it.
• he starts to put these stones one in each hole, starting from the next hole and moving in counter-clockwise order, until there are no more stones left in his hands.

eg: given this board:

player1's row: 2 2 3

player2's row: 1 8 2

if player2 starts a move and chooses the middle hole in his row(the one with 8 stones). The board after the move will be like:

player1's row: 3 3 5

player2's row: 2 1 4

you were playing a very important game with your best friend, when suddenly you had a phone call and moved your eyes of the game. Now you lost track of the game and you need to make sure if your friend made a valid move.

You are given the final board configuration and the place where the last stone landed, Your task is to check is your friend's move is invalid, and in case of a valid move, find the state of the board before that move.

You are player1 while your friend is player2.

Input

The input consists of several test cases, each test case starts with three numbers n(1 ≤ n ≤ 10000) (the number of holes in each of the rows), r (1 ≤ r ≤ 2) and k (1 ≤ k ≤ n) (the row and hole number where the last stone was put, respectively). Then 2n numbers follow, ai :1  ≤  i  ≤  n, and bj :1  ≤  j  ≤  n, where ai is the number of stones in the i-th hole in your row. bj is the number of stones in the j-th hole in your friend's row. Initially given ai and bi satisfy that: (0 ≤ ai, bj ≤ 1000000000) while ai and bj are fit in 64 bits in the state of the board before the move (if there is a valid move).

The last test case is followed by three zeros.

Output

For each test case display the case number followed by the word "INVALID" without the quotes if the move is invalid, or 2n numbers representing the original board configuration otherwise.

Examples

Input

```3 1 3
3 3 5
2 1 4
4 2 2
1 2 3 4
5 4 3 2
4 2 2
1 2 3 4
1 2 3 4
5 2 3
2 2 2 2 2
2 2 2 2 2
0 0 0```

Output

```Case 1:
2 2 3
1 8 2
Case 2:
INVALID
Case 3:
0 1 2 3
9 0 2 3
Case 4:
0 0 0 0 0
0 0 20 0 0```

1.将石子堆化为一维 2.取其中最小的石子数为minnum,答案一定是在石子数为minnum的石子堆中。 3.判断哪一个最小值为答案，即，距离起点最近的那一个石子堆

```  1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
5 {
6     ll x=0,f=1;
7     char ch=getchar();
8     while(ch<'0'||ch>'9')
9     {
10         if(ch=='-')
11             f=-1;
12         ch=getchar();
13     }
14     while(ch>='0'&&ch<='9')
15     {
16         x=x*10+ch-'0';
17         ch=getchar();
18     }
19     return x*f;
20 }
21 inline void write(ll x)
22 {
23     if(x<0)
24     {
25         putchar('-');
26         x=-x;
27     }
28     if(x>9)
29         write(x/10);
30     putchar(x%10+'0');
31 }
32 const int N=100010;
33 ll num[N];
34 vector<int>v;
35 #define INF 0x3f3f3f3f3f;
36 int main()
37 {
38     int tcase=1;
39     int n,r,c;
40     while(scanf("%d%d%d",&n,&r,&c)!=EOF)
41     {
42         if(n==0&&r==0&&c==0)
43             break;
44         v.clear();
45         ll pos=0;
46         ll minnum=INF;
47         for(int i=1;i<=n;i++)
48         {
50             minnum=min(minnum,num[i]);
51         }
52         for(int i=2*n;i>n;i--)
53         {
55             minnum=min(minnum,num[i]);
56         }
57         for(int i=1;i<=2*n;i++)
58         {
59             if(num[i]==minnum)
60                 v.push_back(i);
61         }
62         if(r==1)
63             pos=c;
64         else pos=2*n-c+1;
65         ll ans=minnum*2*n;
66         ll len=v.size();
67         ll dis=INF;
68         for(int i=0;i<len;i++)
69         {
70             if(v[i]>=pos)
71                 dis=min(dis,v[i]-pos);
72             else dis=min(dis,2*n-pos+v[i]);
73         }
74         int ed=(dis+pos)%(2*n);
75         if(ed==0)
76             ed=2*n;
77         printf("Case %d:\n",tcase++);
78         if(ed<=n)
79             cout<<"INVALID"<<endl;
80         else
81         {
82             for(int i=1;i<=2*n;i++)
83                 num[i]-=minnum;
84             for(int i=pos;i<pos+dis;i++)
85             {
86                 int ret=i%(2*n);
87                 if(ret==0)
88                     ret=2*n;
89                 num[ret]--;
90             }
91             int ret=(pos+dis)%(2*n);
92             if(ret==0)
93                 ret=2*n;
94             num[ret]=ans+dis;
95             cout<<num[1];
96             for(int i=2;i<=n;i++)
97                 cout<<" "<<num[i];
98             cout<<endl;
99             cout<<num[2*n];
100             for(int i=2*n-1;i>n;i--)
101                 cout<<" "<<num[i];
102             cout<<endl;
103         }
104     }
105     return 0;
106 }```

0 条评论

• ### Codeforces Round #410 (Div. 2)(A,字符串,水坑，B,暴力枚举，C,思维题，D,区间贪心)

A. Mike and palindrome time limit per test:2 seconds memory limit per test:256 m...

• ### POJ 1012 Joseph

Joseph Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 53862 ...

• ### AIM Tech Round 4 (Div. 2)(A，暴力，B，组合数，C，STL+排序)

A. Diversity time limit per test：1 second memory limit per test：256 megabytes in...

• ### 【PAT甲级】Counting Ones

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### ZOJ 3204 Connect them

Connect them ---- Time Limit: 1 Second      Memory Limit: 32768 KB ---- You have...

• ### POJ 1163（数字三角形）

7 3 8 8 1 0 2 7 4 4 4 5 2 6 5

• ### Codeforces Round #410 (Div. 2)(A,字符串,水坑，B,暴力枚举，C,思维题，D,区间贪心)

A. Mike and palindrome time limit per test:2 seconds memory limit per test:256 m...

• ### 搜索专题2 | 3D地宫寻路 POJ - 2251

上一篇我们做了一道棋子摆放的题目，采用的是DFS算法，本篇是一篇BFS算法，在刚开始学习搜索算法的时候，会觉得DFS和BFS算法非常相似，因为都是搜索然后得到结...

• ### POJ-2585-Window Pains

Window PainsTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 2915 ...

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...