| Submit | All submissions | Best solutions | Back to list |
CARDSHUF - Cards shuffing |
| English | Tiếng Việt |
"Phú ông" has a card deck consits of n cards. He writes on each card a number from 1 to n from the top to the bottom of the deck.
Then he does shuffle the card deck several times, each time is described by S(i, j) meaning: pull out the ith card then put it on the jth of the remaining cards (1 ≤ i, j ≤ n). If j = n, the ith card will be the bottom card of the new one.
For example (n=6):
Afer x times of shuffing, "Phú ông" gives "Bờm" the card deck and chanllenges him to make it into the original order. Please help "Bờm"!
Input
- The first line contains two integer n, x.
- Next x line(s), the pth line contains two integer ip, jp describing the pth time of shuffing (S(ip, jp)).
Output
- A single integer means the minimal number of times of shuffing the card deck to help "Bờm".
Example
Input:
6 4
2 3
1 2
4 5
1 6
Output:
2
Limitations
- 1 ≤ n, x ≤ 105.
| Added by: | AnhDQ |
| Date: | 2009-05-19 |
| Time limit: | 0.100s-1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
| Resource: | Mr Hoang Le Minh (HNEU) - Vietnam |
hide comments
|
2021-11-03 11:14:44
Treap + Segment tree passes |
|
|
2015-02-21 04:32:37 Stupid Dog
FastIO + rb_tree_tag = time limit exceeded |
|
|
2013-08-15 23:42:43 Danh Nguyen
@Buda IM: Could you please provide your Faster IO methods? |
|
|
2012-05-07 19:37:17 Buda IM (retired)
Faster IO methods should be used, my N log N passes only with fast io |
|
|
2011-11-18 09:53:34 Seshadri R
One more example with i and j differing by more than one would have helped. Otherwise, except for the last one, all the illustrations mislead the reader to think that it is a simple exchange of i and j. |
|
|
2009-10-29 08:45:36 Seshadri R
Under Limitations, it is stated that - 1 ≤ n, x ≤ 10 to the power of 5. Is the minus sign in front of 1 a typo? |
RSS