Thành phố Tablecity

Điểm: 5,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Thành phố Tablecity là một lưới $1000 \times 2$ , mỗi ô là một khu phố mang tên $(X, Y)$ với $1 \leq X \leq 1000$ và $1 \leq Y \leq 2$ .

Có một tên trộm đang lẩn trốn trong thành phố. Ở thời điểm ban đầu (giờ thứ $1$ ), tên trộm có thể ở bất kỳ ô nào trong lưới. Mỗi giờ trôi qua, sau khi cảnh sát điều tra xong, tên trộm sẽ rời khu phố $(X, Y)$ hiện tại và di chuyển sang đúng một trong các khu phố sau (miễn là khu phố đó nằm trong thành phố):

$(X - 1, Y), (X + 1, Y), (X - 1, Y - 1), (X - 1, Y + 1), (X + 1, Y - 1), (X + 1, Y + 1) .$

Nói cách khác, hoành độ $X$ luôn đổi $\pm 1$ , còn tung độ $Y$ có thể đổi $- 1$ , $0$ hoặc $+ 1$ .

Cảnh sát trưởng Albert có đủ người để mỗi giờ kiểm tra đúng hai khu phố. Nếu trong giờ đó tên trộm đang ở một trong hai khu phố bị kiểm tra thì hắn bị bắt.

Albert đã hứa với Tổng thống rằng sẽ bắt được tên trộm trong không quá $2015$ giờ. Hãy giúp Albert lập kế hoạch điều tra đảm bảo bắt được tên trộm, bất kể vị trí ban đầu và chiến lược di chuyển của hắn.

Dữ liệu vào

Không có dữ liệu vào.

Dữ liệu ra

Dòng đầu in số nguyên $N$ — số giờ cảnh sát điều tra ( $0 \leq N \leq 2015$ ).

Trong $N$ dòng tiếp theo, dòng thứ $i$ chứa $4$ số nguyên $X_{i, 1} Y_{i, 1} X_{i, 2} Y_{i, 2}$ là toạ độ hai khu phố mà cảnh sát kiểm tra trong giờ thứ $i$ (theo thứ tự thời gian). Cần đảm bảo $1 \leq X \leq 1000$ và $1 \leq Y \leq 2$ .

Kế hoạch của bạn phải đảm bảo: với mọi vị trí ban đầu của tên trộm và mọi cách di chuyển hợp lệ của hắn, tên trộm sẽ bị bắt trong vòng $N$ giờ.

Bài có nhiều đáp án hợp lệ. Bộ chấm sẽ mô phỏng tên trộm theo hướng bất lợi nhất để xác nhận kế hoạch của bạn có đảm bảo bắt được hay không.

Ràng buộc

$0 \leq N \leq 2015$
$1 \leq X \leq 1000$ , $1 \leq Y \leq 2$ cho mọi toạ độ kiểm tra.

Ví dụ

Input	Output	Giải thích
(trống)	2 5 1 50 2 8 1 80 2	Đây không phải đáp án đúng, chỉ minh hoạ định dạng. Nếu tên trộm ban đầu ở $(1, 1)$ rồi di chuyển sang $(2, 2)$ thì cảnh sát không bắt được.
(trống)	2000 1 1 1 2 2 1 2 2 ... 1000 1 1000 2 1000 1 1000 2 ... 1 1 1 2	Quét cột $1, 2, \dots, 1000$ rồi quét ngược lại $1000, 999, \dots, 1$ là một cách hợp lệ.

Bình luận

Không có bình luận tại thời điểm này.