trang chủ / đề bài / cheese / lời giải

Hầm Ngục Hogwarts

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả: huunguyenhuunguyen

Lời giải: Hầm Ngục Hogwarts

Hướng tiếp cận

Bài toán yêu cầu kiểm tra xem có đường đi từ mặt đáy (z=0) đến mặt trần (z=H) thông qua các buồng hình cầu. Đây là bài toán kiểm tra tính liên thông trong đồ thị.

Nhận xét quan trọng

  1. Mô hình hóa đồ thị: Mỗi buồng là một đỉnh. Hai buồng i và j có cạnh nối nếu khoảng cách giữa tâm ≤2R, tức là: (xi−xj)2+(yi−yj)2+(zi−zj)2≤2R Bình phương hai vế để tránh số thực: (xi−xj)2+(yi−yj)2+(zi−zj)2≤4R2

  2. Nút ảo: Thêm nút ảo "đáy" nối với mọi buồng có zi≤R, và nút ảo "trần" nối với mọi buồng có zi≥H−R.

  3. Tránh tràn số: Tọa độ lên đến 109, nên hiệu bình phương lên đến 1018. Tổng 3 bình phương lên đến 3×1018, và 4R2 lên đến 4×1018. Cả hai đều nằm trong phạm vi long long (≈9.2×1018).

Thuật toán

Sử dụng Union-Find (Disjoint Set Union) hoặc BFS/DFS:

  1. Tạo N+2 đỉnh: N buồng + 1 nút đáy + 1 nút trần.
  2. Duyệt mọi buồng i:
    • Nếu zi≤R: nối buồng i với nút đáy.
    • Nếu zi≥H−R: nối buồng i với nút trần.
  3. Duyệt mọi cặp buồng (i,j): nếu khoảng cách bình phương ≤4R2, nối i với j.
  4. Kiểm tra xem nút đáy và nút trần có cùng thành phần liên thông hay không.

Độ phức tạp

  • Thời gian: O(T·N2·α(N)) với α là hàm Ackermann ngược (gần như hằng số).
  • Bộ nhớ: O(N).
  • Với T≤20 và N≤1000, tổng thao tác ≈20×106, hoàn toàn đủ nhanh.

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