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

VMKEY - Thế giới năm 1000003

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/vmkey


Nếu là một người ưa phát minh, chắc hẳn bạn sẽ cảm thấy thế giới năm 1000003 vô cùng nhàm chán. Lúc này, tất cả mọi phát minh mà con người từng mơ ước tới đều đã trở thành hiện thực. Ô tô bay, nhà bay, thành phố bay... đã xuất hiện nhiều nhan nhản. Tất cả mọi người sống trong những ngôi nhà thông minh được điều khiển bởi giọng nói, ánh mắt hoặc suy nghĩ, với sự hỗ trợ của các hệ thống máy tính hiện đại nhất. Con người có thể di chuyển tức thời giữa không gian (giữa các hành tinh ở cách nhau hàng nghìn năm ánh sáng) và thời gian - điều này đã góp phần khiến cho dân số thế giới tăng với tốc độ chóng mặt, vượt qua con số 10001000 vào năm 1000003.

Lúc này, những chiếc SmartPhone đã trở nên lỗi thời, do chúng không chịu được áp lực quá lớn khi đi qua cổng dịch chuyển tức thời hoặc khi đi vào các cỗ máy thời gian. Tất cả mọi người đều dùng điện thoại Nokia.

Do dân số thế giới đã tăng vượt mốc 10001000, những dãy số điện thoại cũng đã dài tới hàng trăm nghìn chữ số. Điều này đã khiến cho việc bấm phím số điện thoại trở nên ác mộng. Trước tình trạng này, hãng điện thoại Nokia đã đưa ra tính năng mới, cho phép bạn có thể thay đổi vị trí các phím số trên bàn phím, để bạn có thể bấm số điện thoại một cách nhanh nhất có thể.

Thời gian để bạn bấm số điện thoại bằng tổng thời gian di chuyển của ngón tay bạn giữa các phím số liên tiếp trong dãy số. Thời gian này đúng bằng khoảng cách Manhattan giữa 2 phím số: Nếu phím số A ở dòng i, cột j, và phím số B ở dòng u, cột v, thì khoảng cách Manhattan giữa 2 phím số được tính theo công thức:

dist(A, B) = |i - u| + |j - v| 

Chẳng hạn, bạn muốn gọi số 357468, nếu sử dụng bàn phím cổ điển:

1 2 3
4 5 6
7 8 9
0    

bạn sẽ mất tổng thời gian là;

dist(3, 5) + dist(5, 7) + dist(7, 4) + dist(4, 6) + dist(6, 8)

= ( |1 - 2| + |3 - 2| ) + ( |2 - 3| + |2 - 1| ) + ( |3 - 2| + |1 - 1| ) + ( |2 - 2| + |1 - 3| ) + ( |2 - 3| + |3 - 2|)

= 2 + 2 + 1 + 2 + 2

= 9

Nhưng nếu bạn thay đổi vị trí các phím số như hình dưới:

3 5 7
8 6 4
1 2 9
0    

 

thì bạn chỉ mất tổng thời gian là:

dist(3, 5) + dist(5, 7) + dist(7, 4) + dist(4, 6) + dist(6, 8)

= 1 + 1 + 1 + 1 + 1

= 5

Chú ý: Bạn chỉ được phép đổi chỗ các phím số, nghĩa là sau khi bạn thay đổi các phím số, mỗi phím phải tương ứng với duy nhất 1 số, và mỗi số phải tương ứng với duy nhất 1 phím. Các phím phải nằm đúng ở 10 vị trí chứa các số 0-9 trong bàn phím cổ điển. Các phím trên điện thọai được đánh số hàng từ trên xuống dưới, đánh số cột từ trái sang phải (xem ví dụ).

Input

Gồm 1 dòng duy nhất chứa dãy số điện thoại

Output

Gồm 1 dòng duy nhất ghi thời gian nhỏ nhất để bạn bấm dãy số điện thoại, sau khi đã thay đổi vị trí các phím số một cách hợp lý

Giới hạn

  • Độ dài dãy số điện thoại không quá 400,000
  • Trong 20% số test, độ dài dãy số điện thoại không quá 625

Chấm bài

Bài của bạn sẽ được chấm trên thang điểm 100. Điểm mà bạn nhận được sẽ tương ứng với % test mà bạn giải đúng.

Trong quá trình thi, bài của bạn sẽ chỉ được chấm với 1 test ví dụ có trong đề bài.

Khi vòng thi kết thúc, bài của bạn sẽ được chấm với bộ test đầy đủ.

Example

Input:
357468

Output:
5

Được gửi lên bởi:VOJ Team
Ngày:2013-06-27
Thời gian chạy:1s
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ừ: ASM64 GOSU PERL6 PYPY RUST SED

hide comments
2021-07-24 07:09:51
1 đấm ac :)))
2017-09-22 11:12:11
trâu cũng AC
2016-05-24 11:44:43 Lương Ðức Tuấn Ðạt
Tham khảo thuật toán + code tại: http://yeulaptrinh.pw/196/vmkey-spoj/
2015-11-30 16:31:02 Lương Ðức Tuấn Ðạt
có ai để
freopen("VMKEY.inp", "r", stdin);
freopen("VMKEY.out", "w", stdout);
chạy thì bị lỗi
đổi thành tên khác bất kỳ
freopen("vao.inp", "r", stdin);
freopen("ra.out", "w", stdout);
thì lại chạy ok như mình không?? @@
2014-02-22 14:15:49 Lê Quang Hải


Last edit: 2014-02-25 08:44:37
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.