trang chủ / đề bài / icpcwf10_g

Các hòn đảo

Đề bài

Mô tả

Wen Chen là thuyền trưởng một chiếc tàu cứu hộ. Một trong những nhiệm vụ quan trọng của anh là mỗi ngày đi một vòng qua một nhóm đảo để kiểm tra xem mọi thứ có ổn không. Thuyền trưởng Wen xuất phát từ hòn đảo ở xa nhất về phía tây, đi một lượt sang hòn đảo ở xa nhất về phía đông và ghé thăm một số hòn đảo trên đường, rồi đi lượt thứ hai từ hòn đảo xa nhất phía đông quay về hòn đảo xuất phát và ghé thăm các hòn đảo còn lại. Trong mỗi lượt, Wen luôn tiến đều về phía đông (ở lượt thứ nhất) hoặc về phía tây (ở lượt thứ hai), nhưng có thể di chuyển về phía bắc hay phía nam bao xa tùy ý để tới các hòn đảo. Điều phức tạp duy nhất là có hai hòn đảo đặc biệt nơi Wen tiếp nhiên liệu cho tàu, nên anh phải ghé thăm chúng ở hai lượt khác nhau. Hình dưới đây (ví dụ 1, bộ test thứ nhất) cho thấy hai hòn đảo đặc biệt 1 và 3 (tô đỏ) cùng một đường đi có thể của thuyền trưởng Wen.

graph directed base=0
0 1
1 4
4 3
3 2
2 0
pos 0 60 180
pos 1 180 120
pos 2 240 300
pos 3 420 60
pos 4 480 180
label 0 (1,3)
label 1 (3,4)
label 2 (4,1)
label 3 (7,5)
label 4 (8,3)
highlight red 1 3

Hãy tính độ dài của đường đi ngắn nhất ghé thăm tất cả các hòn đảo trong hai lượt, khi biết vị trí của từng hòn đảo và hai hòn đảo đặc biệt.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa ba số nguyên n, b1 và b2 (4≤n≤100, 0<b1,b2<n−1, b1≠b2), trong đó n là số hòn đảo (đánh số từ 0 đến n−1), b1 và b2 là hai hòn đảo đặc biệt. Tiếp theo là n dòng, mỗi dòng chứa hai số nguyên là tọa độ x và y của một hòn đảo (0≤x,y≤2000), bắt đầu từ hòn đảo 0. Không có hai hòn đảo nào cùng tọa độ x, và các hòn đảo được cho theo thứ tự từ tây sang đông (tức là tọa độ x tăng dần).

Sau bộ test cuối cùng là một dòng chứa ba số 0.

Dữ liệu ra

Với mỗi bộ test, in ra hai dòng. Dòng thứ nhất ghi số thứ tự bộ test và độ dài của hành trình ngắn nhất mà thuyền trưởng Wen có thể đi, làm tròn đến hàng phần trăm (hai chữ số sau dấu chấm thập phân). Dòng thứ hai là danh sách các hòn đảo theo thứ tự được ghé thăm, cách nhau bởi dấu cách, bắt đầu bằng hòn đảo 0 rồi đến hòn đảo 1, và kết thúc bằng hòn đảo 0. Mỗi bộ test có đúng một lời giải. Làm theo đúng định dạng trong ví dụ.

Ràng buộc

  • 4≤n≤100, 0<b1,b2<n−1, b1≠b2.
  • 0≤x,y≤2000; tọa độ x tăng ngặt theo số hiệu hòn đảo.
  • Số bộ test trong một file không cho trước.

Ví dụ

Input Output Giải thích
5 1 3
1 3
3 4
4 1
7 5
8 3
5 3 2
0 10
3 14
4 7
7 10
8 12
0 0 0
Case 1: 18.18
0 1 4 3 2 0
Case 2: 24.30
0 1 3 4 2 0
Bộ test 1 là hình trên: lượt đi 0→1→4 qua đảo đặc biệt 1, lượt về 4→3→2→0 qua đảo đặc biệt 3.
4 2 1
0 0
1 5
2 0
3 5
6 4 1
0 5
2 9
4 1
6 8
8 3
10 5
0 0 0
Case 1: 14.20
0 1 3 2 0
Case 2: 26.55
0 1 3 5 4 2 0
Bộ test 2: lượt đi 0→1→3→5 chứa đảo đặc biệt b2=1, lượt về 5→4→2→0 chứa đảo đặc biệt b1=4. Hành trình được in theo chiều bắt đầu bằng 0 rồi 1.

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