trang chủ / đề bài / icpcwf16_l

Không gian hoán đổi

Đề bài

Mô tả

Bạn quản trị một cụm máy tính lớn, các ổ cứng của cụm dùng nhiều loại hệ thống tệp khác nhau để lưu dữ liệu. Gần đây bạn quyết định thống nhất tất cả về cùng một loại hệ thống tệp. Đây là một thử thách không nhỏ vì mọi ổ đều đang được sử dụng, ổ nào cũng chứa đầy dữ liệu quan trọng tới đúng dung lượng của nó, và bạn không được phép làm mất bất kỳ dữ liệu nào. Hơn nữa, định dạng lại một ổ sang hệ thống tệp mới có thể làm dung lượng của ổ thay đổi đáng kể. Để việc định dạng lại khả thi, bạn sẽ phải mua thêm một ổ cứng phụ. Dĩ nhiên bạn muốn tiết kiệm tiền bằng cách làm cho dung lượng của ổ phụ này nhỏ nhất có thể.

Bạn có thể định dạng lại các ổ theo thứ tự bất kỳ. Trước khi định dạng lại một ổ, bạn phải chuyển toàn bộ dữ liệu trên ổ đó sang một hoặc nhiều ổ khác, được phép chia nhỏ dữ liệu nếu cần. Sau khi một ổ được định dạng lại, bạn có thể dùng nó ngay để chứa dữ liệu từ các ổ khác. Dữ liệu không nhất thiết phải nằm lại trên đúng các ổ ban đầu của nó (thực tế điều này thậm chí có thể không làm được nếu một số ổ có dung lượng nhỏ hơn với hệ thống tệp mới). Cũng được phép để một phần dữ liệu nằm lại trên ổ phụ khi kết thúc.

Ví dụ, giả sử có bốn ổ A, B, C, D với dung lượng lần lượt 6, 1, 3, 3 GB. Với hệ thống tệp mới, dung lượng của chúng lần lượt trở thành 6, 7, 5, 5 GB. Nếu chỉ mua thêm 1 GB, bạn có thể chuyển dữ liệu trên ổ B sang đó rồi định dạng lại ổ B. Lúc này ổ B trống 7 GB, nên bạn có thể chuyển 6 GB của ổ A sang ổ B rồi định dạng lại ổ A. Cuối cùng, bạn chuyển tổng cộng 6 GB dữ liệu của ổ C và ổ D sang ổ A, rồi định dạng lại C và D.

Dữ liệu vào

Dòng đầu chứa số nguyên n, số ổ cứng trong cụm. Mỗi dòng trong n dòng tiếp theo mô tả một ổ bằng hai số nguyên a và b, trong đó a là dung lượng với hệ thống tệp cũ và b là dung lượng với hệ thống tệp mới.

Mọi dung lượng tính bằng gigabyte.

Dữ liệu ra

In ra tổng dung lượng phụ (tính bằng gigabyte) nhỏ nhất bạn phải mua để định dạng lại được tất cả các ổ.

Ràng buộc

  • 1≤n≤106.
  • 1≤a,b≤109.

Ví dụ

Input Output Giải thích
4
6 6
1 7
3 5
3 5
1 Đây là ví dụ trong đề: mua 1 GB, định dạng lại lần lượt B, A, rồi C và D. Không mua gì thì không thể chuyển dữ liệu của ổ nào ra ngoài.
4
2 2
3 3
5 1
5 10
5 Mua 5 GB: chuyển dữ liệu ổ thứ tư sang ổ phụ và định dạng lại nó (còn trống 10 GB), sau đó lần lượt định dạng lại ổ thứ nhất, thứ hai, rồi ổ thứ ba (lúc đó còn trống 10 GB trên các ổ khác, đủ chứa 5 GB). Ổ thứ nhất và thứ hai không đổi dung lượng, nên trước lần đầu định dạng lại ổ thứ ba hoặc thứ tư, chỗ trống đúng bằng dung lượng mua thêm, mà cả hai ổ này đều chứa 5 GB: ít hơn 5 GB là không đủ.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0