Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

SWAPB - Hoán đổi

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/swapb


            Thời buổi khoa học công nghệ, biết mình không thể nhờ cậy tài phép của thần đèn mãi được nên Aladdin quyết tâm trau dồi kiến thức tin học. Aladdin đặc biệt thích lập trình. Dưới sự kèm cặp của Abu và thần đèn, Aladdin tập luyện ngày đêm nuôi ước mơ đại diện xứ Ba Tư tham dự kì thi IOI.

            Trong một lần làm bài, Aladdin phải nhập dữ liệu vào một bảng A kích thước MxN (M hàng, N cột). Tuy nhiên, do đang mải mơ màng nghĩ tới Jasmine nên Aladdin lại nhập thành bảng NxM và giá trị đáng ra phải ghi vào bảng A ở hàng i cột j thì H lại ghi vào hàng j cột i. Ví dụ với M=3, N=4 :

Bảng Aladdin phải nhập

3

4

-10

5

6

7

0

-12

2

1

9

20

 

 

 

Bảng Aladdin nhập vào

3

6

2

4

7

1

-10

0

9

5

-12

20

 

 

 

            Aladdin định nhập lại từ đầu, nhưng tá hỏa khi biết file dữ liệu đầu vào đã bị virus ăn mất. Vậy nên Aladdin phải viết một chương trình để đưa dữ liệu về bảng A về đúng yêu cầu. Kẹt nỗi mọi chuyện không đơn giản vì Aladdin dùng một máy vi tính đặc biệt. Máy này lưu bảng A dưới dạng một mảng một chiều kích thước MxN và sẽ ghi lần lượt lên mảng này theo thứ tự nhập (theo từng dòng, trên mỗi dòng theo từng cột).

            VD : nếu Aladdin nhập đúng thì mảng  A sẽ như sau

3

4

-10

5

6

7

0

-12

2

1

9

20

           Máy của Aladdin có 2 chế độ : ở chế độ 1 có thể đổi vị trí 2 phần tử bất kì ở vị trí i và j, còn ở chế độ 2 nó chỉ có thể đổi vị trí 2 phần tử liên tiếp i và i+1

           Aladdin định viết 1 chương trình để đưa mảng A về trạng thái đúng. Tuy nhiên trước khi bắt tay vào code, Aladdin muốn biết sẽ tốn ít nhất bao nhiêu phép hoán đổi để đưa bảng về dữ liệu đúng. Có một điều may mắn là Aladdin nhớ rằng khi nhập dữ liệu vào không có 2 phần tử nào có giá trị bằng nhau. Có thể điều này sẽ giúp việc tính toán dễ dàng hơn.


Input
 

            Dòng đầu tiên gồm 3 số nguyên dương M, N là kích thước đúng của bảng  A

            Dòng tiếp hai gồm 1 số duy nhất S là chế độ hiện thời của máy (1 hoặc 2).

            Giới hạn :   1 <= M,N <= 5x105

                             MxN <= 5x105

                             Trong 30% số test với S=2, MxN <= 5000

Output

            Ghi ra một số nguyên duy nhất là số phép hoán đổi ít nhất cần thực hiện để đưa bảng về đúng trạng thái.

Example

Trong khi thi submission sẽ được chấm 2 test, 1 test S = 1 và 1 test S = 2 

Input

Output

2 4

1

4

2 4

2

6


Được gửi lên bởi:Alex & Friends
Ngày:2014-07-16
Thời gian chạy:0.100s-1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C CSHARP C++ 4.3.2 CPP JAVA PAS-GPC PAS-FPC
Nguồn bài:by winterwolf94

hide comments
2019-11-03 09:02:20
sd

Last edit: 2019-11-03 09:02:28
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.