2006/2007 ACM International Collegiate Programming Contest
University of Ulm Local Contest

Homogeneous squares

Assume you have a square of size n that is divided into n×n positions just as a checkerboard. Two positions (x₁,y₁) and (x₂,y₂), where 1 ≤ x₁,y₁,x₂,y₂ ≤ n, are called "independent" if they occupy different rows and different columns, that is, x₁≠x₂ and y₁≠y₂. More generally, n positions are called independent if they are pairwise independent. It follows that there are n! different ways to choose n independent positions.

Assume further that a number is written in each position of such an n×n square. This square is called "homogeneous" if the sum of the numbers written in n independent positions is the same, no matter how the positions are chosen. Write a program to determine if a given square is homogeneous!

Input Specification

The input contains several test cases.
The first line of each test case contains an integer n (1 ≤ n ≤ 1000). Each of the next n lines contains n numbers, separated by exactly one space character. Each number is an integer from the interval [-1000000,1000000].
The last test case is followed by a zero.

Output Specification

For each test case output whether the specified square is homogeneous or not. Adhere to the format shown in the sample output.

Sample Input

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

Sample Output

homogeneous
not homogeneous

---

隨機化檢測正確與否

#include <stdio.h>
#include <stdlib.h>
int A[1000][1000];
int main() {
    int n;
    while(scanf("%d", &n) == 1 && n) {
        int tot = 0, i, j;
        for(i = 0; i < n; i++) {
            for(j = 0; j < n; j++) {
                scanf("%d", &A[i][j]);
            }
        }
        for(i = 0; i < n; i++)
            tot += A[i][i];
        int test = 500, err = 0, m, s;
        int M, st[2050] = {}, prev, last, sum;
        for(M = 1; M < n+1; M <<= 1);
        while(test--) {
            for(i = 2*M-1; i > 0; i--) {
                if(i >= M)
                    st[i] = 1;
                else
                    st[i] = st[i<<1] + st[i<<1|1];
            }
            prev = 0;
            sum = 0;
            for(i = 1; i <= n; i++) {
                m = (rand()+prev)%(n-i+1);
                if(m == 0)  m = n-i+1;
                prev = m-1;
                for(s = 1; s < M; ) {
                    if(st[s<<1] < m)
                        m -= st[s<<1], s = s<<1|1;
                    else
                        s = s <<1;
                }
                last = s-M+1;
                sum += A[i-1][last-1];
                while(s)
                    st[s]--, s >>= 1;
            }
            if(sum != tot) {
                err = 1;
                break;
            }
        }
        if(err)
            puts("not homogeneous");
        else
            puts("homogeneous");
    }
    return 0;
}