Bàn cờ của Mr. Bender

Điểm: 6,00 (OI)

Giới hạn thời gian: 2.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

Cho một bảng vuông kích thước $N \times N$ . Các hàng được đánh số từ $1$ đến $N$ (từ trên xuống), các cột được đánh số từ $1$ đến $N$ (từ trái sang phải).

Ban đầu, chỉ có duy nhất một ô tại vị trí $(X, Y)$ được bật sáng, tất cả các ô còn lại đều tắt.

Sau mỗi giây, mọi ô đang tắt mà có ít nhất một ô kề cạnh (chung cạnh) đang sáng sẽ được bật sáng. Hai ô được gọi là kề cạnh nếu chúng khác nhau ở đúng một tọa độ và sai khác $1$ ở tọa độ còn lại.

Hãy tìm số giây nhỏ nhất cần thiết để số ô đang sáng trên bảng đạt ít nhất $C$ .

Dữ liệu vào

Một dòng duy nhất chứa bốn số nguyên $N$ , $X$ , $Y$ , $C$ cách nhau bởi dấu cách.

Dữ liệu ra

In ra một số nguyên duy nhất — số giây nhỏ nhất cần thiết.

Ràng buộc

$1 \leq N, C \leq 10^{9}$
$1 \leq X, Y \leq N$
$C \leq N^{2}$

Ví dụ

Input	Output	Giải thích
6 4 3 1	0	Ban đầu đã có $1$ ô sáng nên không cần thêm giây nào.
9 3 8 10	2	Sau $1$ giây có $5$ ô sáng (chưa đủ $10$ ). Sau $2$ giây vùng sáng là hình thoi bán kính $2$ bị cột $9$ cắt mất một ô, tổng cộng $13 - 1 = 12$ ô — đủ điều kiện.

Bình luận

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