Sphere Online Judge

SPOJ Problem Set (classical)

9723. Card Shuffling

Problem code: CODESPTC


 

Here is an algorithm for shuffling N cards:
1) The cards are divided into K equal piles, where K is a factor of N.
2) The bottom N / K cards belong to pile 1 in the same order (so the bottom card of the initial pile is the bottom card of pile 1).
3) The next N / K cards from the bottom belong to pile 2, and so on.
4) Now the top card of the shuffled pile is the top card of pile 1. The next card is the top card of pile 2,..., the Kth card of the shuffled pile is the top card of pile K. Then (K + 1)th card is the card which is now at the top of pile 1, the (K + 2)nd is the card which is now at the top of pile 2 and so on.
For example, if N = 6 and K = 3, the order of a deck of cards "ABCDEF" (top to bottom) when shuffled once would change to "ECAFDB".
Given N and K, what is the least number of shuffles needed after which the pile is restored to its original order?
Input:
The first line contains the number of test cases T. The next T lines contain two integers each N and K.
Output:
Output T lines, one for each test case containing the minimum number of shuffles needed. If the deck never comes back to its original order, output -1.
Constraints:
T <= 10000
2 <= K <= N <= 10^9
K will be a factor of N.
Sample Input:
3
6 3
4 2
5 5
Sample Output:
6
4
2

 

Here is an algorithm for shuffling N cards:

1) The cards are divided into K equal piles, where K is a factor of N.

2) The bottom N / K cards belong to pile 1 in the same order (so the bottom card of the initial pile is the bottom card of pile 1).

3) The next N / K cards from the bottom belong to pile 2, and so on.

4) Now the top card of the shuffled pile is the top card of pile 1. The next card is the top card of pile 2,..., the Kth card of the shuffled pile is the top card of pile K. Then (K + 1)th card is the card which is now at the top of pile 1, the (K + 2)nd is the card which is now at the top of pile 2 and so on.

 

For example, if N = 6 and K = 3, the order of a deck of cards "ABCDEF" (top to bottom) when shuffled once would change to "ECAFDB".

 

Given N and K, what is the least number of shuffles needed after which the pile is restored to its original order?

 

Input:

The first line contains the number of test cases T. The next T lines contain two integers each N and K.

 

Output:

Output T lines, one for each test case containing the minimum number of shuffles needed. If the deck never comes back to its original order, output -1.

 

Constraints:

T <= 10000

2 <= K <= N <= 10^9

K will be a factor of N.

 

Sample Input:

3

6 3

4 2

5 5

 

Sample Output:

6

4

2

 

 


Added by:Varun Jalan
Date:2011-10-15
Time limit:4s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All
Resource:own problem used for CodeSprint - InterviewStreet Contest

hide comments
2013-04-16 19:37:13 (Tjandra Satria Gunawan)(曾毅昆)
Why my memory usage is 2.6MB? I didn't precompute the value that much. Is SPOJ change the system?
@Francky: Thanks for your recomendation that was great ;-) Imho, it's better to put all your recommended problem in one page like TJANDRA page. :-)
edit: 4.27s is my best, I can't beat your record, congratulations..
--ans(francky)--> I'll try to take some time to make my Francky page. You made a good chrono too, congratulation to you too. Concerning memory usage, I confirm a 'spoj change' as my same code have now more memory usage. I don't know yet the reason, please let us continue speaking about that in the forum section. ;-)

Last edit: 2013-04-17 17:34:44
2013-04-13 11:03:31 Francky
My 200th problem, AC at first try, and first place. I highly recommend this one to all great solvers ;-)
Many thanks to Varun Jalan for the quality of his tasks.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.