trang chủ / đề bài / icpcwf25_k

Bản đồ kho báu

Đề bài

Mô tả

Sau nhiều năm tìm kiếm, bạn tìm được tấm bản đồ cũ của thuyền trưởng Râu Đen, chỉ ra nơi cất giấu kho báu thất lạc từ lâu của ông, nằm sâu dưới đáy đại dương. Tấm bản đồ vốn là một bản đồ độ sâu, tức là nó ghi độ sâu của đáy biển trong vùng quanh kho báu, nhưng theo thời gian nhiều mốc độ sâu đã phai mờ và không còn đọc được.

Cụ thể, bản đồ bao phủ một vùng biển hình chữ nhật, được chia thành lưới (n−1)×(m−1) ô vuông đơn vị. Ban đầu bản đồ ghi độ sâu d(p) tại mỗi điểm p=(x,y) có tọa độ nguyên với 1≤x≤n và 1≤y≤m. Trong vùng này không có đảo nhỏ nào, nói cách khác, biết chắc rằng d(p)≥0 với mọi điểm.

Việc vẽ bản đồ hẳn đã rất vất vả với Râu Đen, vì không có một cách tự nhiên duy nhất để nội suy độ sâu tại các điểm có tọa độ không nguyên. Xét một ô vuông đơn vị của lưới với bốn đỉnh là các điểm lưới A, B, C, D theo chiều kim đồng hồ, và độ sâu d(p) đã biết tại mỗi p∈{A,B,C,D}. Một cách tự nhiên là nội suy tuyến tính độ sâu trong tam giác ABC, và tương tự trong tam giác CDA. Một cách tự nhiên không kém là nội suy tuyến tính trong tam giác BCD, và tương tự trong tam giác DAB. Thông thường kết quả của hai cách nội suy này khác nhau. Ví dụ, nếu d(A)=d(B)=d(C)=0 và d(D)=1 thì cách thứ nhất cho độ sâu bằng 0 trên toàn bộ tam giác ABC (độ sâu chỉ dương trong tam giác CDA), còn cách thứ hai cho độ sâu dương tại mọi điểm bên trong ô vuông.

Tuy nhiên Râu Đen vừa tàn bạo vừa cứng đầu, không để những sự mơ hồ vặt vãnh như vậy cản đường. Để tìm nơi giấu kho báu hoàn hảo, ông lùng sục khắp bảy đại dương để tìm một vùng biển mà tại mỗi ô vuông đơn vị, hai cách nội suy trên cho cùng một kết quả (hoặc có thể ông đã bắt vài tên cướp biển cải tạo địa hình cho được như vậy, các học giả vẫn chưa thống nhất).

Trở lại hiện tại, bạn đang chuẩn bị một chuyến thám hiểm để lấy kho báu, và muốn biết kho báu có thể nằm ở độ sâu nào. Cụ thể, cho các dữ liệu độ sâu còn đọc được trên bản đồ, hãy tính độ sâu nhỏ nhất có thể tại vị trí kho báu.

Dữ liệu vào

Dòng đầu tiên chứa năm số nguyên n, m, k, tx và ty, trong đó n và m là tọa độ lớn nhất của lưới, k là số độ sâu đã biết, và (tx,ty) là vị trí kho báu.

Mỗi dòng trong k dòng tiếp theo chứa ba số nguyên x, y và d, cho biết độ sâu tại tọa độ (x,y) của lưới bằng d. Mỗi cặp (x,y) xuất hiện trong dữ liệu vào nhiều nhất một lần.

Dữ liệu ra

Nếu các điểm dữ liệu đã cho có thể mở rộng thành một bản đồ hợp lệ (tức là một bản đồ mà tại mỗi ô vuông đơn vị, hai cách nội suy cho cùng kết quả, và mọi điểm đều có độ sâu không âm), in ra một số nguyên: độ sâu nhỏ nhất có thể tại (tx,ty). Có thể chứng minh rằng giá trị này luôn là số nguyên. Ngược lại, in ra impossible.

Ràng buộc

  • 2≤n,m≤3·105.
  • 1≤k≤3·105.
  • 1≤tx≤n, 1≤ty≤m.
  • 1≤x≤n, 1≤y≤m, 0≤d≤109.

Ví dụ

Input Output Giải thích
3 3 5 1 1
1 3 1
3 3 2
2 3 3
2 2 4
2 1 5
3 Với mọi bản đồ hợp lệ khớp dữ liệu, độ sâu tại (1,1) đều bằng 3.
3 5 4 3 4
2 4 1
2 2 2
1 1 4
3 1 5
1 Có bản đồ hợp lệ với độ sâu tại (3,4) bằng 1, và không có bản đồ hợp lệ nào cho độ sâu nhỏ hơn.
3 3 3 3 3
2 3 1
2 1 2
1 2 4
0 Có bản đồ hợp lệ với độ sâu tại (3,3) bằng 0.
3 3 4 3 2
2 1 2
2 3 3
1 3 4
1 1 5
impossible Không có bản đồ hợp lệ nào khớp với cả bốn độ sâu đã cho.
3 3 3 2 2
3 2 0
2 2 1
2 3 0
impossible Dù độ sâu tại (2,2) đã được cho, các điểm dữ liệu không thể mở rộng thành một bản đồ hợp lệ, nên đáp án là impossible.

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