trang chủ / đề bài / icpcwf09_a

Tiếp cận cẩn trọng

Đề bài

Mô tả

Nếu bạn nghĩ tham gia một kỳ thi lập trình là căng thẳng, hãy thử tưởng tượng mình là một kiểm soát viên không lưu. Khi tính mạng con người đang bị đe dọa, kiểm soát viên không lưu phải tập trung vào công việc trong điều kiện liên tục thay đổi, đồng thời xử lý những sự cố bất ngờ.

Xét nhiệm vụ lập lịch cho các máy bay hạ cánh xuống một sân bay. Các máy bay đang đến báo cáo vị trí, hướng bay và tốc độ, sau đó kiểm soát viên phải lập ra một lịch hạ cánh đưa tất cả máy bay xuống mặt đất an toàn. Nói chung, thời gian giữa hai lần hạ cánh liên tiếp càng dài thì lịch hạ cánh càng "an toàn". Khoảng thời gian dư ra này cho phi công cơ hội phản ứng với thời tiết thay đổi và các tình huống bất ngờ khác.

May mắn là một phần của việc lập lịch này có thể được tự động hóa, và đây là lúc bạn vào cuộc. Bạn được cho các kịch bản hạ cánh của máy bay. Mỗi máy bay có một khoảng thời gian mà trong đó nó có thể hạ cánh an toàn. Bạn phải tìm một thứ tự hạ cánh cho tất cả máy bay tôn trọng các khoảng thời gian này. Hơn nữa, các lần hạ cánh phải được giãn ra nhiều nhất có thể, sao cho khoảng cách thời gian nhỏ nhất giữa hai lần hạ cánh liên tiếp là lớn nhất có thể. Ví dụ, nếu ba máy bay hạ cánh lúc 10:00, 10:05 và 10:15 thì khoảng cách nhỏ nhất là năm phút, giữa hai máy bay đầu tiên. Các khoảng cách không nhất thiết phải bằng nhau, nhưng khoảng cách nhỏ nhất phải lớn nhất có thể.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test, mỗi bộ test mô tả một kịch bản hạ cánh. Mỗi bộ test bắt đầu bằng một dòng chứa một số nguyên n (2≤n≤8) là số máy bay trong kịch bản. Tiếp theo là n dòng, dòng thứ i chứa hai số nguyên ai, bi cho biết đầu và cuối của đoạn đóng [ai,bi] mà máy bay thứ i có thể hạ cánh an toàn trong đó. Các số ai và bi tính bằng phút và thỏa mãn 0≤ai≤bi≤1440.

Dữ liệu vào kết thúc bằng một dòng chứa duy nhất số nguyên 0.

Dữ liệu ra

Với mỗi bộ test, in ra số thứ tự của bộ test (bắt đầu từ 1), tiếp theo là khoảng cách thời gian nhỏ nhất (giữa hai lần hạ cánh liên tiếp) lớn nhất có thể đạt được. In thời gian dưới dạng số phút và số giây, làm tròn tới giây gần nhất. Làm theo đúng định dạng trong ví dụ: số giây luôn gồm hai chữ số.

Ràng buộc

  • 2≤n≤8.
  • 0≤ai≤bi≤1440, các số đều nguyên.
  • Mỗi file có không quá 50 bộ test.

Ví dụ

Input Output Giải thích
3
0 10
5 15
10 15
2
0 10
10 20
0
Case 1: 7:30
Case 2: 20:00
Bộ 1: hạ cánh lúc 0, 7.5 và 15 phút, khoảng cách nhỏ nhất là 7 phút 30 giây. Bộ 2: hạ cánh lúc 0 và 20.
8
0 10
0 10
0 10
0 10
0 10
0 10
0 10
0 10
8
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
2
5 5
5 5
0
Case 1: 1:26
Case 2: 0:09
Case 3: 0:00
Bộ 1: tám máy bay chia đều đoạn [0,10], khoảng cách 10/7 phút ≈85.71 giây, làm tròn thành 1 phút 26 giây. Bộ 2: 60/7≈8.57 giây, làm tròn thành 9 giây. Bộ 3: cả hai máy bay phải hạ cánh lúc 5, khoảng cách bằng 0.

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