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.|

NK05EOPR - Đổi chỗ

Cho một dãy số là một hoán vị của 12 số tự nhiên đầu tiên (từ 0 đến 11). Giả sử số 0 ở vị trí thứ i trong dãy số (vị trí được đánh số từ 0 đến 11, từ trái sang phải) thì bạn có thể đổi chỗ số 0 với số ở vị trí thứ j nếu thỏa mãn cả hai điều kiện sau:

  • | i – j | = dk , với k=1..3 và (d1,d2,d3,d4)=(1;3;6;12)

  • [i/dk+1]=[j/dk+1], với [] là hàm phần nguyên

Bạn hãy tìm số phép đổi chỗ ít nhất để có thể sắp xếp dãy số theo thứ tự tăng dần

Dữ liệu vào

Dòng đầu tiên là một số nguyên t cho biết số lượng test (t<=20)

Mỗi bộ test bao gồm một dòng là dãy bao gồm các số từ 0 đến 11, mỗi số ngăn cách bởi một khoảng trắng.

Biết rằng mỗi dãy số cho trước luôn luôn có thể sắp xếp tăng dần bằng phép đổi chỗ đã quy định

Kết qủa

Với mỗi bộ test, in ra số phép đổi chỗ ít nhất để sắp xếp dãy số đã cho theo thứ tự tăng dần

Ví dụ

Dữ liệu mẫu
2
1 10 2 3 0 5 7 4 8 6 9 11
6 4 1 0 3 5 9 7 2 10 11 8

Kết qủa
8
9

Được gửi lên bởi:Duc
Ngày:2005-05-02
Thời gian chạy:18s
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:Từ acm.uva.es

hide comments
2016-02-05 11:45:24
có chắc chắn sẽ luôn thỏa mãn i và j nào đó để đổi chỗ ko ad, nếu vào trường hợp ko thể đổi chỗ thì dãy không thể sắp xếp theo một giải thuật (chẳng may lặp vô hạn)
2014-07-03 10:10:24 KNEO
k = 1..4 chứ
2011-08-20 17:53:23 Bùi Ðức Trí
That weird! For above testcase I have another result. It's "6 9", not "8 9".

Last edit: 2011-08-20 17:53:53
2010-07-13 11:41:15 Normal Skills
TIMES LIMIT BIG


Last edit: 2010-07-13 11:41:49
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.