trang chủ / đề bài / icpcwf11_i

Xác ướp điên cuồng

Đề bài

Mô tả

Trong một chuyến dã ngoại ra sa mạc tại ICPC World Finals 2011, bạn tình cờ bắt gặp một ngôi mộ Ai Cập cổ. Không may, mở ngôi mộ ra hóa ra là một ý tồi: bỗng nhiên, vùng sa mạc vừa mới trống trơn vài phút trước giờ đầy những xác ướp cáu kỉnh (bạn cũng sẽ cáu kỉnh nếu đột nhiên bị đánh thức sau vài nghìn năm ngủ yên). (May thay, sau khi giải xong bài này, bạn tỉnh dậy an toàn trong một phòng khách sạn ở Florida. Lũ xác ướp giận dữ chỉ là một giấc mơ. Hay không phải vậy?)

Đối mặt với đám xác ướp điên cuồng đầy sát khí này, cơ hội duy nhất của bạn là bỏ chạy và cố thoát trước khi chúng bắt được bạn. Câu hỏi là: phải mất bao lâu thì một xác ướp bắt được bạn, giả sử cả bạn lẫn các xác ướp đều không bao giờ mệt?

Ta mô hình hóa sa mạc thành một lưới ô vuông. Bạn và các xác ướp lần lượt di chuyển trên lưới, bạn đi trước. Trong lượt của mình, bạn có thể di chuyển sang một trong tám ô kề với vị trí hiện tại, hoặc đứng yên. Trong lượt của các xác ướp, mỗi xác ướp di chuyển sang ô kề với nó mà đưa nó đến gần bạn nhất (đo bằng khoảng cách Euclid, coi như bạn và mọi xác ướp đứng ở tâm ô của mình). Hai xác ướp có thể cùng ở một ô.

Một bước thời gian gồm lượt đi của bạn, sau đó là lượt đi của các xác ướp. Một xác ướp bắt được bạn nếu nó di chuyển vào ô bạn đang đứng, hoặc nếu bạn di chuyển vào ô có xác ướp. Dĩ nhiên, bạn cố tránh bị bắt càng lâu càng tốt. Sau bao nhiêu bước thời gian thì bạn bị bắt?

Hình trên minh họa một cuộc rượt đuổi với bốn xác ướp. Ô ghi H là vị trí ban đầu của bạn, các ô ghi M là vị trí ban đầu của các xác ướp. Sau bốn bước thời gian, bạn bị bắt bởi xác ướp có vị trí ban đầu là (3,4) so với vị trí ban đầu của bạn.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng một số nguyên n (0≤n≤105) là số xác ướp trong sa mạc. Tiếp theo là n dòng, mỗi dòng chứa hai số nguyên x và y, cho biết ban đầu có một xác ướp ở tọa độ (x,y) của sa mạc, trong đó giá trị tuyệt đối của x và y đều không vượt quá 106. Vị trí xuất phát của bạn là (0,0) và không có xác ướp nào xuất phát ở vị trí này.

Sau bộ test cuối cùng là một dòng chứa số −1.

Dữ liệu ra

Với mỗi bộ test, in số thứ tự của bộ test, theo sau là số bước thời gian lớn nhất cho tới khi bạn bị bắt (tính bằng tổng số lượt đi mà bạn có), hoặc từ never nếu bạn có thể tránh bị bắt mãi mãi. Theo đúng định dạng của ví dụ.

Ràng buộc

  • 0≤n≤105.
  • |x|,|y|≤106; không có xác ướp nào ở (0,0).

Ví dụ

Input Output Giải thích
4
-3 5
3 4
-6 -2
1 -5
1
0 -1
-1
Case 1: 4
Case 2: never
Bộ 1 là cuộc rượt đuổi trong hình. Bộ 2: bạn chạy thẳng lên trên, xác ướp duy nhất luôn ở ngay phía sau cách bạn một ô.
4
-2 0
2 0
0 -2
0 2
2
-5 0
3 0
3
-2 2
-2 -2
2 -2
-1
Case 1: 2
Case 2: 4
Case 3: never
Bộ 1: dù bạn đi đâu ở bước đầu, sau bước 2 vẫn bị bắt. Bộ 3: bạn chạy theo hướng (1,1), không xác ướp nào bắt kịp.

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