trang chủ / đề bài / icpcwf12_a

Kiểm lâm tiểu hành tinh

Đề bài

Mô tả

Năm 2112, loài người đã chinh phục hệ Mặt Trời. Quân đoàn Kiểm lâm Không gian đã đặt căn cứ trên mọi khối đá có thể ở được dù chỉ một chút. Là thành viên của Bộ Liên lạc Tiểu hành tinh, nhiệm vụ của bạn là bảo đảm mọi căn cứ trên các tiểu hành tinh có thể liên lạc với nhau với chi phí rẻ nhất. Bạn có thể lập kênh liên lạc trực tiếp từ mỗi căn cứ tới mọi căn cứ khác, nhưng như vậy thì quá đắt. Thay vào đó, bạn muốn lập ít kênh nhất có thể sao cho ai cũng gửi được tin nhắn tới mọi người khác, có thể thông qua việc chuyển tiếp ở một hoặc nhiều căn cứ trung gian. Chi phí của một kênh tỉ lệ thuận với khoảng cách giữa hai căn cứ mà nó nối, nên bài toán có vẻ không khó lắm.

Tuy nhiên có một khó khăn nhỏ. Các tiểu hành tinh luôn di chuyển, nên hai căn cứ hiện đang ở rất gần nhau có thể sẽ không còn gần trong tương lai. Vì vậy theo thời gian, bạn phải sẵn sàng đổi các kênh liên lạc để lúc nào cũng dùng hệ thống chuyển tiếp rẻ nhất. Việc đổi kênh tốn thời gian và tiền bạc, nên bạn muốn biết mình sẽ phải thực hiện việc đổi như vậy bao nhiêu lần.

Một vài giả thiết giúp bài toán dễ hơn. Mỗi tiểu hành tinh được coi là một điểm. Các tiểu hành tinh luôn chuyển động thẳng với vận tốc không đổi. Không có hai tiểu hành tinh nào va chạm nhau. Ngoài ra, mọi hệ thống chuyển tiếp trở thành tối ưu tại một thời điểm t≥0 sẽ là hệ thống tối ưu duy nhất tại mọi thời điểm s thỏa mãn t<s<t+10−6. Hệ thống chuyển tiếp tối ưu ban đầu là duy nhất.

Nói cách khác: hệ thống chuyển tiếp tối ưu tại mỗi thời điểm là cây khung nhỏ nhất của đồ thị đầy đủ trên các căn cứ, trọng số mỗi cạnh là khoảng cách Euclid (trong không gian ba chiều) giữa hai căn cứ tại thời điểm đó. Hãy đếm số lần hệ thống phải được thiết lập hoặc thay đổi trong khoảng thời gian t≥0: lần thiết lập ban đầu tại t=0 cũng được tính.

Dữ liệu vào

Dữ liệu gồm nhiều bộ test, kết thúc ở cuối file. Mỗi bộ test bắt đầu bằng một dòng chứa số nguyên n là số căn cứ. Tiếp theo là n dòng, mỗi dòng chứa sáu số nguyên x,y,z,vx,vy,vz: ba số đầu là vị trí ban đầu của một tiểu hành tinh, ba số sau là các thành phần theo trục x, y, z của vận tốc tiểu hành tinh đó (đơn vị không gian trên một đơn vị thời gian). Tại thời điểm t, tiểu hành tinh ở vị trí (x+vxt,y+vyt,z+vzt).

Dữ liệu ra

Với mỗi bộ test, in ra một dòng gồm số thứ tự bộ test và số lần hệ thống chuyển tiếp cần được thiết lập hoặc thay đổi, theo đúng định dạng trong ví dụ.

Ràng buộc

  • 2≤n≤50.
  • −150≤x,y,z≤150.
  • −100≤vx,vy,vz≤100.
  • Không có hai tiểu hành tinh nào va chạm nhau, và các giả thiết về tính duy nhất ở trên luôn được thỏa mãn.

Ví dụ

Input Output Giải thích
3
0 0 0 0 0 0
5 0 0 0 0 0
10 1 0 -1 0 0
4
0 0 0 1 0 0
0 1 0 0 -1 0
1 1 1 3 1 1
-1 -1 2 1 -1 -1
Case 1: 3
Case 2: 3
Hai bộ test. Ở bộ thứ nhất, ban đầu hệ thống gồm các kênh 1-2 và 2-3. Tiểu hành tinh 3 bay về phía âm của trục x: tại t=10−24≈5,10 khoảng cách 1-3 bằng 5, sau đó kênh 1-2 được thay bằng 1-3; tại t=5+24≈9,90 khoảng cách 2-3 bằng 5, sau đó kênh 2-3 được thay bằng 1-2. Tổng cộng 3 lần.
5
0 0 0 -1 0 0
2 0 0 0 0 -1
0 2 0 0 0 0
2 2 0 1 2 0
1 1 0 1 1 2
Case 1: 5 Một bộ test với 5 căn cứ: hệ thống ban đầu và 4 lần thay đổi sau đó.

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