1961 問題 E: 藍橋杯算法提高VIP-Mummy Madness
時間限制: 1s
內存限制: 128MB 提交: 8 解決: 5
題目描述
在2011年ACM-ICPC World Finals上的一次游覽中，你碰到了一個埃及古墓。
不幸的是，你打開了墳墓之后，才發(fā)現這是一個壞主意：突然之間，原本空無一物的沙漠上已經爬滿了暴躁的木乃伊。（如果你也沉睡幾千年而突然被驚醒，你也會變得如此暴躁的。）（幸運的是，當你做完這道題的時候，你醒來了，發(fā)現你在弗羅里達的酒店里。那些木乃伊只是一場夢。）
面對這一大堆瘋狂的木乃伊，你唯一的機會就是試圖在他們抓到你之前逃跑。問題是：假如你與木乃伊永不疲倦，那么經過多長時間你會被木乃伊抓到？
我們把沙漠看成一個正方形的網格，你與木乃伊輪流移動（你走出第一步）。輪到你時，你可以移動到相鄰的8個格子之一，或者站著不動。輪到木乃伊時，每個木乃伊會移動到其相鄰的格子之一，使得他與你的歐幾里得距離盡量?。僭O你與木乃伊都站在格子的中心位置）。允許多個木乃伊同時占據同一個格子。
在每個單位時間內，你先做出移動，然后木乃伊做出移動。如果你與任何一個木乃伊站在同一位置，你會被抓住。當然，你試圖盡量長時間避免被抓住。經過多少單位時間你會被抓住呢？
下圖描述了你被4個木乃伊追逐的例子。H代表你的初始位置，而M代表木乃伊的初始位置。以你的初始位置為原點，則經過4個單位時間后，你被初始位置為(3,4)的木乃伊抓住。
不幸的是，你打開了墳墓之后，才發(fā)現這是一個壞主意：突然之間，原本空無一物的沙漠上已經爬滿了暴躁的木乃伊。（如果你也沉睡幾千年而突然被驚醒，你也會變得如此暴躁的。）（幸運的是，當你做完這道題的時候，你醒來了，發(fā)現你在弗羅里達的酒店里。那些木乃伊只是一場夢。）
面對這一大堆瘋狂的木乃伊，你唯一的機會就是試圖在他們抓到你之前逃跑。問題是：假如你與木乃伊永不疲倦，那么經過多長時間你會被木乃伊抓到？
我們把沙漠看成一個正方形的網格，你與木乃伊輪流移動（你走出第一步）。輪到你時，你可以移動到相鄰的8個格子之一，或者站著不動。輪到木乃伊時，每個木乃伊會移動到其相鄰的格子之一，使得他與你的歐幾里得距離盡量?。僭O你與木乃伊都站在格子的中心位置）。允許多個木乃伊同時占據同一個格子。
在每個單位時間內，你先做出移動，然后木乃伊做出移動。如果你與任何一個木乃伊站在同一位置，你會被抓住。當然，你試圖盡量長時間避免被抓住。經過多少單位時間你會被抓住呢？
下圖描述了你被4個木乃伊追逐的例子。H代表你的初始位置，而M代表木乃伊的初始位置。以你的初始位置為原點，則經過4個單位時間后，你被初始位置為(3,4)的木乃伊抓住。
輸入
輸入文件包含若干組數據。每組數據的第一行為一個數n(0≤n≤10^5)，表示沙漠中木乃伊的個數。接下來n行，每行兩個整數x y，表示初始時在(x,y)有一個木乃伊。x,y的絕對值均不超過10^6。你的初始位置是(0,0)，保證一開始這里沒有木乃伊。
輸入文件以一行-1結束。
輸入文件以一行-1結束。
輸出
對于每組測試數據，輸出一行，包括它的編號和被抓住經過的最長時間（即你做出決策的次數）；或輸出"never"，如果你有辦法永遠不被抓住。
請以樣例輸出的格式輸出數據。
請以樣例輸出的格式輸出數據。
樣例輸入
4 -3 5 3 4 -6 -2 1 -5 1 0 -1 -1
樣例輸出
Case 1: 4 Case 2: never
比賽公告
歡送開學！
比賽結束歡迎提供題解！
聯(lián)系QQ群管理員有獎勵！