[ACM] ZOJ 3844 Easy Task (模擬+哈希）

[ACM] ZOJ 3844 Easy Task (模擬+哈希）

You are given n integers. Your task is very easy. You should find the maximum integer a and the minimum integer b among these n integers. And then you should replace both a and bwith a-b. Your task will not be finished unless all the integers are equal.

Now the problem come, you want to know whether you can finish you task. And if you can finish the task, you want to know the final result.

Input

The first line of the input contain an integer T(T≤ 20) indicates the number of test cases.

Then T cases come. Each case consists of two lines. The first line is an integer n(2≤ n≤ 10) as the problem described. The second line contains n integers, all of them are no less than -100000 and no more than 100000.

Output

For each case you should print one line. If you can finish your task, you should print one of the n integers. Otherwise, you should print "Nooooooo!"(without quotes).

Sample Input

2
3
1 2 3
2
5 5

Sample Output

2
5

解題思路：

題意為給定n個數（2<=n<=10),每個數的范圍為 -100000到100000，有一種操作：找到這n個數中最大的數max,最小的數min，把這兩個數都替換為 max-min ， 重復這樣的操作，直到這n個數完全相同，如果可以達到這樣的目的，就輸出最後那n個數中的其中一個（每個數都一樣）,如果不能，則輸出 Nooooooo!。

n的范圍很小，直接按照題意排序模擬即可，一開始覺得任何數據都可以達到目的，沒有輸出Nooooooo!的情況，寫了一發，交上去，果斷WA.後來和二師兄討論，應該記錄狀態才對，一旦出現相同的狀態，那麼就不能達到目的，輸出Nooooooo!。方法為哈希查找，每一個狀態用包含這n個數的結構體來保存，關鍵字是這n個數的和，以n個數的和對一個大素取余作為關鍵字，10個數的最大和不超過100000*10,所以開辟這麼大的結構體類型的vector數組，當出現一個新的狀態時，就去該狀態的和取余後的索引中的那些狀態去比較，這樣可以減少比較次數，因為一個狀態和另一個狀態相同，它們分別的元素之和取余後相等是大前提。

注意：n個元素和可能是負數，建立索引要加上mod變為正數.

代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include