[UVA] 10710 - Chinese Shuffle
Problem F
Chinese
Shuffle
Input: standard input
Output: standard output
Time Limit: 1 second
Jimmy was a math student in Chicago in the thirties of the last century. Being a student was tough those days (as it still is), and he was always short of money. So he decided to moonlight at the casino of his uncle. Well, casino is a big word; it was the upstairs room of a cafe, and you had to know the guy at the back door to be alowed to enter at all. Anyway, making profit was the main goal of his uncle, so Jimmy was expected to do just that.
One day, sitting alone in his room, not knowing where to start studying for his next exam, he took up a deck of playing cards and began practicing his "Perfect Shuffle". Let me explain what a perfect shuffle is.
In an ordinairy shuffle, the dealer splits the deck in two roughly equal parts, takes one half in each hand and then releases the cards alternating from his left and right hand onto a new pile on the table. You probably know what I mean; when you try it yourself, the cards end up all over the place. In Jimmy's perfect shuffle you start with N cards (N=52 for an ordinary deck). Take the top N/2 cards in your right hand (round down if N is odd) and the remaining cards in your left. Now drop the bottom most card from your left hand, cover it with the bottom most card from your right hand, drop the next bottom most from your left hand, etc., alternating between left and right until all the cards are in one pile again.
Let's take 10 cards, numbered 1 to 10 from top to bottom. After one shuffle the order becomes:
RIGHT: 1 2 3 4 5, LEFT: 6 7 8 9 10 -> 1 6 2 7 3 8 4 9 5 10
With 11 cards:
RIGHT: 1 2 3 4 5, LEFT: 6 7 8 9 10 11 -> 6 1 7 2 8 3 9 4 10 5 11
Jimmy practiced his shuffle to perfection. There is of course a great benifit in being able to do a perfect shuffle: once you know the order of the cards before the shuffle, you can predict the order after the shuffle. Dealing at the Black Jack table, he made his uncle very happy. But that's beside the point now. The thing Jimmy noticed while he was practicing, was that only 8 out of all 52! different orderings of a standard deck of cards could be attained by repeatedly applying his shuffle. In other words: after 8 perfect shuffles the cards were in their original order again. He started wondering what was so special about the number 8 and added a Joker to the deck. With this new deck of 53 cards he discovered that he needed 52 perfect shuffles to return to the original ordering. A completely different number. Now his mathematical curiosity was roused and he started experimenting with different numbers of cards.
For example for 9 cards:
original : 1 2 3 4 5 6 7 8 9
shuffle 1: 5 1 6 2 7 3 8 4 9
shuffle 2: 7 5 3 1 8 6 4 2 9
shuffle 3: 8 7 6 5 4 3 2 1 9
shuffle 4: 4 8 3 7 2 6 1 5 9
shuffle 5: 2 4 6 8 1 3 5 7 9
shuffle 6: 1 2 3 4 5 6 7 8 9
Here are the results for N=3 to 20:
3: 2 shuffles
4: 2 shuffles 5: 4 shuffles 6: 4 shuffles 7: 3 shuffles 8: 3 shuffles 9: 6 shuffles10: 6 shuffles11: 10 shuffles
12: 10 shuffles
13: 12 shuffles
14: 12 shuffles
15: 4 shuffles16: 4 shuffles17: 8 shuffles18: 8 shuffles19: 18 shuffles
20: 18 shuffles
Completing the list up to 53 cards, he made some preliminary conclusions:
- If N is even, the number of shuffles is equal to the number of shuffles for N-1;
- The maximum number of shuffles for N cards is N-1;
- The values of N for which this maximum is attained (up to 53) are: 3, 5, 11, 13, 19, 29, 37 and 53.
(For N=1 and N=2 the situation is doubtful; one can argue if so few cards are "shufflable".)
Of course he recognised these numbers, as you probably do, but he felt that some were missing. Notably 7, 17, 23, 31, 41, 43 and 47 had less than the maximum number of shuffles. But for these numbers he discovered that the original order would also be restored after N-1 shuffles. For instance it takes 8 shuffles to restore the order of 17 cards, which means the order is also restored after 2 x 8 = 16 shuffles. Up to N=53, no other values than the mentioned ones have this property. Jimmy had the impression that he was on to something big, but since his hands can only hold a limited number of cards, he asks for your assistance to calculate the result for bigger values of N. (There is this small issue of time-warping the results back some 70 years, but that will be solved some other time.)
Let's define a Jimmy-number as:
- take a deck of N playing cards in some predefined order;
- make N-1 perfect shuffles, as defined above;
- if the cards are in their original order, N is a Jimmy-number;
- if they are not in their original order, N is not a Jimmy-number.
Input
A maximum of 2000 integer numbers between 54 and 2000000000 (2 billion), both inclusive, each on a line by it self, terminated by a –1, which should not be processed.
Output
For each number in the input one line of output: "NUMBER is a Jimmy-number" or "NUMBER is not a Jimmy-number", whichever appropriate, where NUMBER is replaced by the input number.
Sample Input Output for Sample Input
5410114419719999999731999999975-1 |
54 is not a Jimmy-number101 is a Jimmy-number144 is not a Jimmy-number197 is a Jimmy-number1999999973 is a Jimmy-number
1999999975 is not a Jimmy-number
|
Problem setter: Little Joey
但是後面主要是問你有 N 張牌，進行 N-1 次的完美切牌，會不會回到 1, 2, ..., n
會發現，切地 i 次排，位置會移動 2^i 個，因此檢查 2^(n-1)%n == 1 ?
#include <stdio.h>
long long mpow(long long x, long long y, long long mod) {
long long ret = 1;
while(y) {
if(y&1)
ret = (ret*x)%mod;
y >>= 1;
x = (x*x)%mod;
}
return ret;
}
int main() {
long long n;
while(scanf("%lld", &n) == 1 && n > 0) {
printf("%lld ", n);
if(mpow(2, n-1, n) == 1)
puts("is a Jimmy-number");
else
puts("is not a Jimmy-number");
}
return 0;
}