[ZJ] a064. SPOJ 4580.ABCDEF

http://zerojudge.tw/ShowProblem?problemid=a064

內容 ：

You are given a set S of integers between -30000 and 30000 (inclusive).
Find the total number of sextuples  that satisfy:

輸入說明 ：

The first line contains integer N (1 ≤ N ≤ 100), the size of a set S.
Elements of S are given in the next N lines, one integer per line. Given numbers will be distinct.

輸出說明 ：

Output the total number of plausible sextuples.

範例輸入 ：

112232-1135710

範例輸出 ：

142410

提示 ：

Added by:	Luka Kalinovcic
Date:	2009-07-13
Time limit:	2s
Source limit:	50000B
Languages:	All except: ERL JS PERL 6
Resource:	own problem

题目来源SPOJ 4580，输入只有一笔，不用EOF判断结束。

出處 ：

SPOJ 4580 (管理：liouzhou_101)

以下是 O(n^4)
要看O(n^3) 請用"百度"搜尋，是用HASH的

/**********************************************************************************/
/*  Problem: a064 "SPOJ 4580.ABCDEF" from SPOJ 4580                               */
/*  Language: C                                                                   */
/*  Result: AC (780ms, 737KB) on ZeroJudge                                        */
/*  Author: morris1028 at 2011-05-31 22:36:21                                     */
/**********************************************************************************/


#include<stdio.h>
#include<stdlib.h>
#define move 60000
main() {
    int N, S[100], i, j, k, l;
    while(scanf("%d", &N) == 1) {
        for(i = 0; i < N; i++)
            scanf("%d", &S[i]);
        int ef[120001] = {};
        long long A = 0;
        for(i = 0; i < N; i++)
            for(j = 0; j < N; j++)
                ef[(S[i]+S[j]+move)]++;
        for(i = 0; i < N; i++) {
            for(j = i+1; j < N; j++)
                for(l = 0; l < N; l++)
                    for(k = 0; k < N; k++){
                        if(S[k] != 0 && (S[i]*S[j]+S[l])%S[k] == 0 && abs((S[i]*S[j]+S[l])/S[k]) < 60000 )
                        A+=2*ef[(S[i]*S[j]+S[l])/S[k]+move];
                    }
            j = i;
                for(l = 0; l < N; l++)
                    for(k = 0; k < N; k++){
                        if(S[k] != 0 && (S[i]*S[j]+S[l])%S[k] == 0 && abs((S[i]*S[j]+S[l])/S[k]) < 60000 )
                        A+=ef[(S[i]*S[j]+S[l])/S[k]+move];
                    }
        }
        printf("%lld\n", A);
    }
    return 0;
}