2015
04-13

# Inverting Cups

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65568/32768 K (Java/Others)
Total Submission(s): 326    Accepted Submission(s): 60

Problem Description
When people drink some tea in the teahouse, they also play some casual games. Now, inverting cups is a popular game. The meaning of the question is, now there are some cups which are upturned, we can regard the total number of the cups as a positive integer number A , and we can invert some cups, the number is B and B is also a positive integer number. We define one retroflexion that if the original cup is upturned, one retroflexion makes it downward, and if the original cup is downward, one retroflexion makes it upturned. So the question is if the whole original cups are upturned , can we invert these cups to make all the cups downward? And if it is possible, how many is the least of times?

Input
The input contains multiple test cases(cases<=100000). Each case one line given two numbers , the first integer A (1<=A<=2^63) and the second integer B (1<=B<=A). The input is terminated by the end of file.

Output
For each test case, you should output how many the least of times if it is possible for us to invert all the cups, and if it is impossible please output “No Solution!”

Sample Input
5 3
14 4
8 5
11 4

Sample Output
3
4
4
No Solution!

Source

n为奇数m为偶数的情况无解，因为m为偶数，每次翻转将把从正面翻到反面的个数x减去从反面翻到正面的个数y，得到的数必定为偶数。因为x+y为偶数，x-y也为偶数。而总个数为奇数，所以无解。

n，m同奇偶，且3*m>n的时候，可以3次解决：

1.将m个正的变成反的，则此时正的有n-m个，反的有m个。

2.将(n-m)/2个正的翻成反的，将(3m-n)/2个反的翻成正的，此时正的有n-m-(n-m)/2+(3m-n)/2=m，反的有m+(n-m)/2-(3m-n)/2=n-m

3.将剩下m个正的翻成反的。

1.先将m个正的翻成反的，此时有n-m个正的，m个反的。

2.将(n-m-1)/2个正的翻成反的，将(3m-n+1)/2个反的翻成正的，则此时有m+1个正的，n-m-1个反的。

3.将(m+1)/2个正的硬币翻成反的，将(m-1)/2个反的硬币翻成正的，此时有m个正的，n-m个反的。

4.将剩下所有的正的翻过来。

#include <stdio.h>

__int64 Solve(__int64 n,__int64 m)
{
if (n%m==0) return n/m;
if (n%2==1 && m%2==0) return -1;
if (n>=3*m) return (n/m-2)+Solve(n%m+2*m,m);
if ((n%2)==(m%2)) return 3;
if (n>=2*m) return 4;
return Solve(n,n-m);
}

int main()
{
__int64 n,m,ret,q,r;
while(scanf("%I64d%I64d",&n,&m)!=EOF)
{
ret=Solve(n,m);
if (ret<0) printf("No Solution!\n");
else printf("%I64d\n",ret);
}
return 0;
}


1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

2. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.