SPOJ：洗牌 [英] SPOJ:Card Shuffling

问题描述

最近我开始解决网上评委提问。我被困在在SPOJ 这样一个问题：

Recently I started solving questions on online judges. I am stuck in this question in SPOJ:

下面是一个算法洗牌N卡：

Here is an algorithm for shuffling N cards:

  
1. 该卡被划分成K等于桩，其中K是N的因子。
  
2. 底部N / K卡属于堆1中相同的顺序（因此.initial桩的底部卡是桩1的底部卡）。
  
3. 从底部的下一个N / K卡属于桩2，依此类推。
  
4. 现在，洗牌桩顶卡桩1。下一张牌的顶部卡桩2顶牌，...，洗牌桩的第K卡是一堆K的顶部卡，然后（K + 1）个卡是这是目前在桩1的顶部，第（K + 2）是这是目前在桩2的顶部等的卡的卡。
  

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.

例如，如果N = 6，K = 3，一副扑克牌ABCDEF（从上到下）一次洗牌时，将改变为ECAFDB。

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?

我试着模仿，但超过时间限制。是否有任何数学公式​​？

---

I tried simulating but it exceeds time limit. Is there any mathematical equation?

推荐答案

是的，有这个问题的数学解决方案。

Yes, there is a mathematical solution for this problem.

首先让我先就如何处理这一问题的一些建议，然后我会给实际的解决方案的一些技巧。我不太完成它，这样仍有一定的挑战左侧。

First let me start with some tips on how to approach such problems and then I will give some tips on the actual solution. I will not quite finish it so that there is still some challenge left.

所以：如何处理这一问题？你所做的其实是一个良好的开端。撰写模拟运行对一些小的情况下。仿真应该是相当快出现。现在你有更多的价值。把它们写在一张纸上，并开始盯着他们。你必须回回例如在K = X <子> 1 和N = Y <子> 1 那么结果为z <子> 1 和更多这样的对。揣摩一些公式。重点有对于x一个固定的值，y或用于z三倍。他们有什么共同点？等等。你盯着通常你在一段时间后得到一个好主意：）

So: how to approach such problems? What you did is actually a good start. Write a simulation and run it against some small cases. The simulation should be fairly fast there. Now you have some more values. Write them down on a piece of paper and start staring at them. You have fro instance if K = x₁ and N = y₁ then the result is z₁ and a lot more such pairs. Try to figure some formula. Focus on triples that have a fixed value for x, for y or for z. What do they have in common? And so on. You stare and usually you get a bright idea after some time :)

现在：关于这方面的问题的一些技巧。执行洗牌的单次迭代并记下每张卡去。例如卡1进入在位置3卡3进入在位置2等。注意，一些链将形成这种方式 - 在本例中，例如，N = 6，K = 3，我们有一个链长度为6的：1-> 3-> 2-> 6-> 4-> 5-> 1 。现在计算所有的链的长度（每张卡将属于正好一个链），并试图找到怎样的答案取决于这些长度。

Now: some tips on this particular problem. Do a single iteration of the shuffling and note where each card goes. For instance card 1 goes in position 3 card 3 goes in position 2 and so on. Note that some chains will be formed this way - for instance in the example n=6, k=3, we have a chain of length 6: 1->3->2->6->4->5->1. Now compute the lengths of all the chains(each card will belong to exactly one chain) and try to find how does the answer depend on these lengths.

希望这是足以帮助你解决问题。

Hope this is enough to help you solve the problem.

编辑：纵观模拟哪怕一个迭代的约束可能会很慢。如果是这样的话，你做了之后，我建议我的第二个技巧尝试计算链条的长度，而不必实际模拟一台洗牌

taking a look at the constraints simulating even a single iteration might be very slow. If that is the case, after you have done what I advice in my second tip try calculating the lengths of chains without actually having to simulate one shuffle

这篇关于SPOJ：洗牌的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！