11055 - Homogeneous squares

假設你有一個大小為n x n的棋盤(例如西洋棋盤)，我們定義：如果兩個位置(或稱格子)分別為(x1, y1),  (x2, y2)其中1 <= x1, y1, x2, y2 <= n，彼此之間是"獨立"的，則此兩個位置分別在不同列也不同行，也就是: x1 != x2且y1 != y2。更進一步定義：如果有 n 個位置彼此之間是"獨立"的，表示任兩個位置皆是獨立的。n x n大小的方格中選擇n個彼此獨立的位置共有 n! 種可能的組合。
再進一步假設，如果在這 n x n 的棋盤方格中每個位置都有一個數字，且不管選擇何種 n 個彼此獨立的組合，將這 n 個位置上的數字加總後其總合皆相同，則我們稱此 n x n 的棋盤方格為"協調的"(homogeneous)。


Input Specification
輸入有多筆測試資料。每筆測試資料的第一列為整數 n (1 <= n <= 1000)表示棋盤方格大小為 n x n，接下來有 n 列，每列 n 個整數表示每個位置上的數字，其值介於[-1000000, 1000000]之間。當 n = 0表示測試資料結束。

Output Specification

若該組資料為"協調的"請輸出"homogeneous"，否則請輸出"not homogeneous"。

Sample Input

2
1 2
3 4
3
1 3 4
8 6 -2
-3 4 0
0

Sample Output

homogeneous
not homogeneous


原文出處

11044 - Searching for Nessy

有關尼斯湖水怪請參考：http://en.wikipedia.org/wiki/Loch_Ness_Monster

2003年7月，BBC廣播團隊發表一則關於尼斯湖水怪的研究，該研究利用了600個獨立的聲納探測儀後發現，尼斯湖內並無任何大型生物，所以該團隊認為尼斯湖水怪並不存在。如今，我們想要重複實作此實驗。

湖的大小定為 n 列與 m 行，6n, m10000，在湖中佈滿聲納探測儀，用來偵測湖上的動靜，其中：

1. 探測儀可偵測的範圍為九宮格的大小，如下圖X點及其相鄰的八個區塊。

2. 湖邊四周圍並不需要偵測，因為湖水太淺，水怪不會游到這邊來。

X點表示聲納所在位置，而灰色區域表示可偵測的範圍，如上圖。

Input

輸入的第一行為整數 t 表示測試資料的組數，每一組資料一行有兩個以空白隔開的整數 n, m，6n, m10000，表示湖的大小(n 列 m 行)。

Output

請對每一組輸入資料，輸出最少需要幾組聲納儀才能使偵測範圈涵蓋所有監控區域。

Sample Input

3
6 6
7 7
9 13

Sample Output

4
4
12

---

原文出處