//
you're reading...
Bài tập huấn luyện

Bài tập huấn luyện:Chống phân mảnh đĩa cứng

 

Đĩa cứng của máy tính sau một thời gian hoạt động sẽ xảy ra tình trạng phân mảnh, có nghĩa là có một số file dữ liệu thay vì được lưu trữ liên tiếp trên đĩa cứng lại nằm rải rác ở các vị trí khác nhau. Điều này không những làm chậm tốc truy xuất file mà còn làm giảm tuổi thọ của đầu từ do đầu từ cần di chuyển nhiều hơn. Để khắp phục tình trạng này, người ta thường chạy một chương trình chống phân mảnh đĩa cứng và kết quả sau đó là các phần nằm rải rác của các file được di chuyển sao cho sau đó các file đều nằm liên tiếp trên đĩa cứng, tuy nhiên thời gian chạy thường là rất lâu.

BB nhận ra nguyên nhân có thể là do các chương trình yếu kém khi xác định vị trí của các khối dữ liệu cần di chuyển sẽ phải di chuyển đến đâu vì vậy BB quyết định viết một chương trình chống phân mảnh siêu tốc với bí quyết là giảm thiểu số khối dữ liệu cần di chuyển.

Biết rằng đĩa cứng gồm N khối, mỗi khối có thể đã được chiếm bởi 1 file hoặc còn trống. Khối thứ i của đĩa được thể hiện bởi cặp số (Fi, Ti) với Fi là số hiệu của file đang được ghi trên khối đó và Ti là số thứ tự của khối trong file. Trong trường hợp khối thứ i còn trống thì Fi = Ti = 0.

Hiện tại BB đã viết xong phiên bản 0.9 của chương trình chống phân mảnh của mình, tuy nhiên BB muốn đọ với các bạn xem thuật toán của BB và của các bạn thì thuật toán nào cần di chuyển ít khối hơn mà vẫn đảm bảo sau khi di chuyển thì các khối thuộc một file nằm liên tiếp và có số hiệu tăng dần liên tục.

Input: DEFRAC.INP

  • Dòng đầu tiên chứa số nguyên dương N là kích thước của đĩa cứng.
  • Dòng thứ i trong N dòng tiếp theo ghi 2 số nguyên (Fi, Ti) thể hiện tình trạng khối thứ i của đĩa.

Output: DEFRAC.OUT

Ghi ra N cặp số tự nhiên trên N dòng biểu diễn tình trạng N khối của đĩa cứng sau khi được chống phân mảnh theo quy ước đã dùng trong file Input.

Giới hạn:

  • N ≤ 10000
  • 1 ≤ Fi ≤ 10000.
  • Số thứ tự của các khối trong 1 file là các số nguyên dương được đánh liên tiếp bắt đầu từ 1.
  • Thời gian: 1 s/test
  • Bộ nhớ: 16 MB

Ví dụ:

DEFRAC.INP DEFRAC.OUT
6

0 0

2 1

1 2

1 1

2 2

0 0

0 0

2 1

2 2

1 1

1 2

0 0

( Với cách chống phân mảnh như trên thì số khối cần di chuyển là 2 )

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười 2016
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Fast-flying Falcon

sunset and fishing nets

Force of Life - Pushing Boundaries I

More Photos

Thống kê

  • 81,544 lượt xem

%d bloggers like this: