trang chủ / đề bài / icpcwf20_k

Tường không gian

Đề bài

Mô tả

Tập đoàn Place-Y Technology sắp phóng một trạm vũ trụ mới. Vị giám đốc của công ty nổi tiếng là người cầu toàn. Chẳng hạn, ông yêu cầu mọi bề mặt bên ngoài của trạm phải thường xuyên được đánh bóng và dọn sạch thứ mà ông gọi là "rác vũ trụ", chủ yếu để trạm trông đẹp trong ảnh. Nhóm kỹ sư đã cố thuyết phục giám đốc rằng việc này không cần thiết nhưng thất bại. Vì vậy họ phát triển một công nghệ mới để bảo trì bề mặt mà hạn chế tối đa việc con người phải ra ngoài trạm. Việc bảo trì do nhiều robot nhỏ di chuyển trên bề mặt trạm đảm nhiệm, giống như robot hút bụi. Trước chuyến bay đầu tiên, Place-Y cần đánh giá nguy cơ va chạm khi các robot hoạt động. Đây chính là lúc bạn vào cuộc.

Trong bài này, trạm vũ trụ được mô hình hóa là một tập các khối lập phương đơn vị có cạnh song song với các trục tọa độ (không nhất thiết liên thông). Mỗi robot bắt đầu tại thời điểm t=0 ở tâm một mặt lộ ra ngoài của một khối lập phương đơn vị của trạm (tức là một mặt không dùng chung với một khối khác của trạm). Robot hướng theo một trong bốn hướng song song với một cạnh của mặt đó. Sau mỗi đơn vị thời gian, robot đi thẳng về phía trước sang một mặt khối khác, có thể xoay 90 độ qua các cạnh của trạm để luôn bám trên bề mặt trạm. Lưu ý rằng nếu hai khối dùng chung một cạnh thì robot không thể lách qua giữa chúng (không có khe hở).

Hình minh họa ví dụ 1. Các chấm tròn là vị trí xuất phát của hai robot.

Cho hình dạng của trạm và vị trí xuất phát của tất cả robot, hãy xác định thời điểm xảy ra va chạm sớm nhất (nếu có). Thời điểm va chạm là đơn vị thời gian mà hai hay nhiều robot cùng ở phần trong của cùng một mặt khối, hoặc đơn vị thời gian mà hai robot định đổi chỗ cho nhau (xem ví dụ 3 cho trường hợp thứ hai).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n và k, trong đó n (1≤n≤100) là số vùng mô tả hình dạng trạm và k (0≤k≤100) là số robot trên bề mặt.

Mỗi dòng trong n dòng tiếp theo chứa sáu số nguyên x1,y1,z1,x2,y2,z2 (0≤x1<x2≤106, 0≤y1<y2≤106, 0≤z1<z2≤106) mô tả một vùng: mọi điểm (x,y,z) thỏa mãn x1≤x≤x2, y1≤y≤y2, z1≤z≤z2 đều thuộc trạm. Lưu ý rằng một khối lập phương đơn vị có thể thuộc nhiều vùng.

Tiếp theo là k dòng, mỗi dòng mô tả vị trí xuất phát của một robot gồm ba tọa độ x, y, z và hai hướng f→ và d→. Ba tọa độ cho biết robot xuất phát trên một mặt của khối lập phương đơn vị (x,y,z)−(x+1,y+1,z+1). Mặt cụ thể được xác định bởi f→, còn hướng di chuyển ban đầu được xác định bởi d→. Mỗi hướng f→ và d→ là một trong sáu xâu x+, x-, y+, y-, z+, z-, trong đó x+ là chiều dương của trục x, tức vectơ (1,0,0), và tương tự cho các xâu còn lại. Chữ cái chỉ trục của f→ khác chữ cái chỉ trục của d→. Dữ liệu đảm bảo khối xuất phát thuộc trạm và mặt đã cho là mặt lộ ra ngoài.

Dữ liệu ra

In ra thời điểm xảy ra va chạm đầu tiên. Nếu không bao giờ có va chạm, in ra ok.

Ràng buộc

  • 1≤n≤100; 0≤k≤100.
  • 0≤x1<x2≤106, 0≤y1<y2≤106, 0≤z1<z2≤106.
  • Khối xuất phát của mỗi robot thuộc trạm, mặt f→ của nó lộ ra ngoài, trục của f→ khác trục của d→.

Ví dụ

Input Output Giải thích
9 2
1 1 1 7 7 7
0 0 0 3 3 3
5 0 0 8 3 3
0 5 0 3 8 3
0 0 5 3 3 8
5 5 0 8 8 3
5 0 5 8 3 8
0 5 5 3 8 8
5 5 5 8 8 8
0 1 0 z- x+
3 5 1 z- y+
44 Trạm và hai robot trong hình minh họa.
1 3
0 0 0 1 1 1
0 0 0 x+ z+
0 0 0 y+ x+
0 0 0 z- y+
ok Trạm chỉ gồm một khối. Ba robot không bao giờ cùng ở một mặt và không bao giờ đổi chỗ cho nhau.
1 2
0 0 0 2 1 1
0 0 0 y+ x+
1 0 0 y+ x-
0 Hai robot ở hai mặt y+ kề nhau và đi về phía nhau: ngay ở đơn vị thời gian 0 chúng định đổi chỗ cho nhau.

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