trang chủ / đề bài / icpc22_nat_l

Chiếm đất trên sao Hỏa

Đề bài

Mô tả

Năm 2030, Elon Sumk và Jeff Sozeb hạ cánh thành công xuống sao Hỏa. Cả hai cùng chọn một vùng đất bằng phẳng để hạ cánh tàu vũ trụ. Vùng đất này có thể mô hình hóa thành một bảng hình chữ nhật gồm r hàng và c cột. Các hàng được đánh số từ 1 đến r theo hướng từ Bắc xuống Nam, các cột được đánh số từ 1 đến c theo hướng từ Tây sang Đông. Ô ở hàng thứ u và cột thứ v được ký hiệu là (u,v).

Elon Sumk hạ cánh tại ô (rE,cE), Jeff Sozeb hạ cánh tại ô (rJ,cJ). Sau khi hạ cánh thành công, họ bắt đầu chiếm thêm đất. Do công nghệ còn hạn chế, họ chỉ có thể chiếm đất bên trong vùng đất hình chữ nhật này. Trên sao Hỏa, người ta dùng khoảng cách Manhattan để đo khoảng cách giữa các ô.

Elon Sumk và Jeff Sozeb thống nhất chiếm các ô đất theo quy tắc sau:

  • Nếu một ô gần vị trí hạ cánh của Elon Sumk hơn hẳn so với vị trí hạ cánh của Jeff Sozeb, ô đó thuộc về Elon Sumk.
  • Nếu một ô gần vị trí hạ cánh của Jeff Sozeb hơn hẳn so với vị trí hạ cánh của Elon Sumk, ô đó thuộc về Jeff Sozeb.
  • Nếu khoảng cách từ một ô đến hai vị trí hạ cánh bằng nhau, không ai chiếm ô đó.

Trong bài toán này, bạn được cho kích thước vùng đất r và c, số ô thuộc về Elon Sumk là E và số ô thuộc về Jeff Sozeb là J. Nhiệm vụ của bạn là xác định vị trí hạ cánh của hai người.

Nhắc lại, khoảng cách Manhattan giữa hai ô (x1,y1) và (x2,y2) là |x1−x2|+|y1−y2|.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên t, số bộ test. Tiếp theo là t bộ test, mỗi bộ test nằm trên một dòng gồm bốn số nguyên dương r, c, E và J (1≤r,c≤250, 2≤E+J≤r·c).

Dữ liệu vào đảm bảo tổng r·c trên mọi bộ test không vượt quá 625000.

Dữ liệu ra

Với mỗi bộ test, in ra trên một dòng bốn số nguyên rE, cE, rJ và cJ là vị trí hạ cánh của Elon Sumk và Jeff Sozeb, hoặc in -1 -1 -1 -1 nếu không có lời giải.

Nếu có nhiều lời giải, in ra một lời giải bất kỳ.

Ràng buộc

  • 1≤r,c≤250.
  • E,J là số nguyên dương, 2≤E+J≤r·c.
  • Tổng r·c trên mọi bộ test không vượt quá 625000.

Ví dụ

Input Output Giải thích
1
3 3 3 3
3 3 1 1 Elon Sumk hạ cánh ở góc (3,3), Jeff Sozeb ở góc (1,1). Elon Sumk chiếm 3 ô (3,3), (3,2), (2,3); Jeff Sozeb chiếm 3 ô (1,1), (1,2), (2,1); 3 ô trên đường chéo (1,3), (2,2), (3,1) không thuộc về ai.
4
2 2 1 1
2 2 3 1
1 5 2 3
3 4 2 7
1 1 2 2
-1 -1 -1 -1
1 2 1 3
-1 -1 -1 -1
Ví dụ này không có trong đề gốc. Ở bộ test thứ nhất, hai người hạ cánh ở hai góc đối nhau, mỗi người chiếm đúng ô của mình, hai ô còn lại không thuộc về ai. Ở bộ test thứ ba, Elon Sumk chiếm các cột 1,2, Jeff Sozeb chiếm các cột 3,4,5.

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