CARDSHUF - Cards shuffing

Phú ông có bộ bài gồm n lá bài. Phú ông xếp chúng thành tập và ghi vào mỗi lá bài số thứ tự ban đầu của lá bài đó trong tập bài (vị trí các lá bài được đánh số từ 1 tới n từ trên xuống dưới).
Tiếp theo Phú ông tiến hành tráo tập bài, mỗi phép tráo kí hiệu bởi S(i, j): rút ra lá bài thứ i và chèn lên trên lá bài thứ j trong số n - 1 lá bài còn lại (1 ≤ i, j ≤ n), quy ước rằng nếu j = n thì lá bài thứ i sẽ được đặt vào vị trí cuối cùng của tập bài.
Ví dụ (n=6):

Sau x phép tráo bài, Phú ông đưa cho Bờm tập bài và thách Bờm dùng ít phép tráo nhất để xếp lại các lá bài về vị trí ban đầu. Hãy giúp Bờm thực hiện điều đó.

Dữ liệu

- Dòng đầu tiên chứa hai số nguyên dương n, x.
- x dòng tiếp theo, dòng thứ p chứa hai số nguyên ip, jp cho biết phép tráo thứ p của Phú ông là S(ip, jp).

Kết quả

- Một số duy nhất là số phép tráo cần thực hiện để đưa các lá bài về vị trí ban đầu.

Ví dụ

Dữ liệu:
6 4
2 3
1 2
4 5
1 6

Kết quả:
2

Giới hạn

- 1 ≤ n, x ≤ 105.


Được gửi lên bởi:AnhDQ
Ngày:2009-05-19
Thời gian chạy:0.100s-0.239s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Mr Hoang Le Minh (HNEU) - Vietnam

hide comments
2016-11-03 14:54:19
Code pascal:
http://shink.in/4rng8
2015-11-03 23:15:01
Tham khảo : http://www.oni.vn/uR57W

Blog Thuật toán SPOJ (vnspoj) hy vọng giúp mọi người với solution và code hơn 300 bài tại : http://www.oni.vn/uR57W
2015-08-16 07:01:59 [Nghien] Le Long
undo ???
2014-11-01 23:56:19 Nguyễn Duy Long
splay tree
2011-01-25 14:26:35 Hy Trường Sơn
nice problem!
2010-03-05 15:25:45 phoebe
sao time bài này chặt thế +_+'!!!!!!:((
2009-07-02 07:21:16 Mệt
- chắc là gạch đầu dòng thôi.
2009-07-01 16:43:33
-1 <= n, x <= 10^5.
Nếu n = -1 thì kq thế nào nhỉ.

Bài này của thầy Hoàng, HNUE (tự nhiên AnhDQ móc đâu ra HNEU +_@)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.