trang chủ / đề bài / icpc23_mn_l

Luffy và kho báu One Piece

Đề bài

Mô tả

Thuyền trưởng Luffy cùng các thuyền viên đang lên đường tìm kiếm kho báu huyền thoại "One Piece". Luffy có trong tay tấm bản đồ Grand Line. Bản đồ biểu diễn một vùng biển kích thước m×n, chia thành các ô vuông đơn vị, chỉ số bắt đầu từ 1. Luffy hiện đang ở một hòn đảo tại tọa độ (x,y) trên bản đồ. Anh nhận được một lời gợi ý bí ẩn: "Hãy tìm ở nơi xa nhất, và đến lần thử thứ k, kho báu sẽ hiện ra."

Theo lời gợi ý, Luffy lên kế hoạch thám hiểm như sau:

  • Ở chuyến đi đầu tiên, anh đến ô biển xa hòn đảo nhất và thám hiểm ở đó.
  • Ở chuyến đi thứ hai, anh thám hiểm ô xa thứ hai tính từ hòn đảo trong số các ô chưa được thám hiểm.
  • Ở chuyến đi thứ ba, anh thám hiểm ô xa thứ ba tính từ hòn đảo trong số các ô chưa được thám hiểm.
  • Cứ tiếp tục như vậy cho đến lần thám hiểm thứ k, nơi kho báu One Piece được cho là đang nằm dưới đáy biển.

Tuy nhiên, Luffy nhận ra rằng có rất nhiều vị trí có thể chứa kho báu (vì nhiều ô có cùng khoảng cách tới hòn đảo). Nếu cứ đi theo lộ trình này, các băng hải tặc đối thủ có thể tìm ra kho báu trước. Vì vậy Luffy nhờ bạn giúp đỡ, nhưng anh chỉ cần biết khoảng cách từ hòn đảo đến vị trí có kho báu. Biết được khoảng cách này, Luffy tin rằng trực giác của mình sẽ giúp anh tìm ra chính xác nơi cất giấu kho báu.

Mọi khoảng cách trong vùng biển này đều tính theo khoảng cách Manhattan: khoảng cách giữa hai ô (x1,y1) và (x2,y2) là |x1−x2|+|y1−y2|.

Nói cách khác, xếp các ô của bảng theo khoảng cách tới ô (x,y) giảm dần, hãy in ra khoảng cách của ô thứ k.

Dữ liệu vào

Một dòng gồm 5 số nguyên m, n, x, y và k (2≤m,n≤109; 1≤x≤m; 1≤y≤n; 1≤k≤m×n−1).

Dữ liệu ra

In ra một số nguyên là khoảng cách Manhattan từ hòn đảo đến kho báu One Piece.

Ràng buộc

  • 2≤m,n≤109
  • 1≤x≤m, 1≤y≤n
  • 1≤k≤m×n−1

Ví dụ

Input Output Giải thích
5 6 4 3 4 5 Ô xa nhất là (1,6) với khoảng cách 6. Có 3 ô ở khoảng cách 5 là (1,1), (1,5), (2,6), nên các lần thám hiểm thứ 2, 3, 4 đều ở khoảng cách 5.
5 6 4 3 6 4 Các lần thám hiểm thứ 5 trở đi đến các ô ở khoảng cách 4 như (1,2), (1,4), (2,1), (2,5), (3,6), (5,6).

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