24h購物| | PChome| 登入
2011-06-01 22:23:39| 人氣1,602| 回應0 | 上一篇 | 下一篇

a064. SPOJ 4580.ABCDEF

推薦 0 收藏 0 轉貼0 訂閱站台

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;
}

台長: Morris
人氣(1,602) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:d316. Quadrangle!
此分類上一篇:d416. 投影最大值

是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文