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.
hide comments
treenipples:
2021-11-03 11:14:44
Treap + Segment tree passes |
|
Stupid Dog:
2015-02-21 04:32:37
FastIO + rb_tree_tag = time limit exceeded |
|
Danh Nguyen:
2013-08-15 23:42:43
@Buda IM: Could you please provide your Faster IO methods? |
|
Buda IM (retired):
2012-05-07 19:37:17
Faster IO methods should be used, my N log N passes only with fast io |
|
Seshadri R:
2011-11-18 09:53:34
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. |
|
Seshadri R:
2009-10-29 08:45:36
Under Limitations, it is stated that
|
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 |