trang chủ / đề bài / icpc25_mt_m

Hai con tàu

Đề bài

Mô tả

Một công ty được giao nhiệm vụ thu gom khoáng sản từ N mỏ nằm ở các tọa độ cho trước trên biển. Mỗi mỏ có đúng 1 tấn khoáng sản. Ngoài ra có hai hòn đảo A và B, mỗi đảo nằm ở một tọa độ cho trước.

Công ty có hai con tàu:

  • Một tàu xuất phát từ đảo A và phải quay về đảo A.
  • Tàu còn lại xuất phát từ đảo B và phải quay về đảo B.

Mỗi tàu chở được lượng khoáng sản không giới hạn và có thể ghé nhiều mỏ theo thứ tự bất kỳ. Tuy nhiên, mỗi tàu chỉ được rời đảo và quay về đúng một lần.

Khi một tàu di chuyển từ địa điểm này sang địa điểm khác (giữa một mỏ và một đảo, hoặc giữa hai mỏ), tàu tiêu tốn nhiên liệu. Lượng nhiên liệu cho một lần di chuyển là:

(Số tấn khoáng sản đang có trên tàu) × (khoảng cách Manhattan giữa hai địa điểm)

Khoảng cách Manhattan giữa hai điểm (x1,y1) và (x2,y2) là |x1−x2|+|y1−y2|. Khi bắt đầu hành trình (rời đảo), mỗi tàu chở 0 tấn, nên lần di chuyển đầu tiên không tốn nhiên liệu.

Yêu cầu: Phân mỗi mỏ cho một trong hai tàu và xác định lộ trình của mỗi tàu (bắt đầu và kết thúc ở đảo của nó) sao cho thu gom được toàn bộ N tấn khoáng sản và tổng nhiên liệu của cả hai tàu là nhỏ nhất.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên N: số mỏ.
  • N dòng tiếp theo, mỗi dòng chứa hai số nguyên xi, yi: tọa độ mỏ thứ i.
  • Dòng tiếp theo chứa hai số nguyên xA, yA: tọa độ đảo A.
  • Dòng cuối cùng chứa hai số nguyên xB, yB: tọa độ đảo B.

Dữ liệu ra

In ra một số nguyên là tổng nhiên liệu nhỏ nhất cần dùng để thu gom toàn bộ khoáng sản và mang về các đảo.

Ràng buộc

  • 1≤N≤8
  • −1000≤xi,yi,xA,yA,xB,yB≤1000
  • Mọi tọa độ đều phân biệt.

Ví dụ

Input Output Giải thích
3
1 1
2 2
3 3
0 0
4 4
8 Tàu A: A(0,0)→(2,2)→(1,1)→A, tốn 0+1·2+2·2=6. Tàu B: B(4,4)→(3,3)→B, tốn 0+1·2=2. Tổng 8.
4
5 0
6 0
-5 0
-6 0
0 0
10 10
40 Ví dụ bổ sung (không có trong đề gốc). Tàu A: A→(−6,0)→(−5,0)→A, tốn 0+1+2·5=11. Tàu B: B→(5,0)→(6,0)→B, tốn 0+1+2·14=29. Tổng 40; một mình tàu A gom cả bốn mỏ tốn ít nhất 46.

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