d039: 11044 - Searching for Nessy
Tags :
Accepted rate : 1671人/1760人 ( 95% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-09-14 15:14

Content

尼斯湖水怪是一隻住在尼斯湖中神秘且不明的動物。尼斯湖則是北蘇格蘭的印芬尼斯市附近的一個大且深的淡水湖。尼斯怪通常被視為一種湖怪。
http://en.wikipedia.org/wiki/Loch_Ness_Monster

背景

2003 7 月,BBC (英國國家廣播電視公司) 曾報導了一項他們對尼斯湖所作的大規模研究,他們用 600 支聲納也沒有辦法在湖中找到任何「水怪」(也就是任何已知或未知的大型動物) 的踪跡。他們推論尼斯怪並不存在。現在我們要重覆這項實驗。

問題

給你一個 n m 行的格子代表尼斯湖,6 n, m 10000,找出最少要放幾個聲納才能控制所有的方格,條件如下:

  • 一個聲納佔一格;它的監控範圍為所在的那一格及緊鄰的格子;
  • 邊緣的格子不需要監控,因為尼斯怪太大了,無法蔵在那兒。
例如, 

                 

 其中 X 代表聲納,灰色區域則是它所監控的範圍。最後一個圖則是一組可接受的解答。
Input
輸入的第一行有一個整數,t,代表測試筆數。每筆測資一行,含有兩個由空白分開的數字,6 n, m 10000,也就是格子的大小 (n m )
Output
每筆測資輸出一行,顯示符合上述條件的最小數字。
Sample Input
3
6 6
7 7
9 13
Sample Output
4
4
12
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
Hint :
Tags:
出處:
UVa11044 [管理者:
snail (蝸牛)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」