[UVA][hash] 11386 - Triples＠Morris' Blog｜PChome Online 個人新聞台

2012-06-03 13:01:07| 人氣874| 回應0 | 上一篇 | 下一篇

[UVA][hash] 11386 - Triples

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

 



 
  I I U C   O N L I N E   C O N T E S T   2 0 0 8

 

  Problem B: Triples

 

  Input: standard input

  Output: standard output

 

   

 

  Given
  a sequence of positive integers. You need to find the number of triples in
  that sequence. For this problem, (x, y, z) constructs a triple if and only if
  x + y = z. So, (1, 2, 3) is a triple, where (3, 4, 5) is not.
 

 

  Input

 

  Each input set starts with a positive integer N. Next
  few lines contain N positive integers. Input is terminated by EOF.
 

 

  Output

 

  For
  each case, print the number of triples in a line.
 

 

  Constraints

 

  -           3
  ≤ N ≤ 5000
 

 

  Sample Input

  Output for Sample Input

 

  6
1 2 3 4 5 6
6 
1 2 4 8 16 32
3
100000000
  200000000 100000000
5
1 1 1 2 2

  6
0
1
6

 

   

 

  Problem setter: Md.
  Kamruzzama

 


#include <stdio.h>
#include <algorithm>
#define N 1048575
using namespace std;
int hash[N+1];
typedef struct {
    int next, t;
    unsigned v;
} Node;
Node nd[5005];
int size = 0;
void insert(unsigned v) {
    static unsigned m;
    static int now, pre;
    m = v&N, now = hash[m], pre = 0;
    while(now) {
        if(nd[now].v == v) {
            nd[now].t ++;
            return ;
        }
        if(nd[now].v > v)
            break;
        pre = now, now = nd[now].next;
    }
    size++;
    if(!pre)    hash[m] = size;
    else        nd[pre].next = size;
    nd[size].v = v, nd[size].t = 1;
    nd[size].next = now;
}
int find(unsigned v) {
    static unsigned m;
    static int now, pre;
    m = v&N, now = hash[m], pre = 0;
    while(now) {
        if(nd[now].v == v)
            return nd[now].t;
        if(nd[now].v > v)
            return 0;
        pre = now, now = nd[now].next;
    }
    return 0;
}
int main() {
    int n, i, j;
    unsigned a[5000], b[5000], f[5000];
    while(scanf("%d", &n) == 1) {
        for(i = 1; i <= size; i++) {
            hash[nd[i].v&N] = 0;
        }
        size = 0;
        for(i = 0; i < n; i++) {
            scanf("%u", &a[i]);
            insert(a[i]);
        }
        sort(a, a+n);
        int m = 0;
        for(i = 0; i < n; i++) {
            if(m == 0 || a[i] != b[m-1]) {
                b[m] = a[i];
                f[m] = 1;
                m++;
            } else {
                f[m-1]++;
            }
        }
        long long ans = 0;
        for(i = 0; i < m; i++) {
            ans += find(b[i]+b[i])*f[i]*(f[i]-1)/2;
            for(j = i+1; j < m; j++) {
                ans += find(b[i]+b[j])*f[i]*f[j];
            }
        }
        printf("%lld\n", ans);

    }
    return 0;
}
 

我要檢舉

#11386#Triples

台長： Morris

您可能對以下文章有興趣

[UVA] 467 - Synching Signals

[UVA] 391 - Mark-up

[UVA] 10528 - Major Scales

[UVA][ConvexHull] 218 - Moth Eradication

人氣(874) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][ST] 12299 - RMQ with Shifts
此分類上一篇:[UVA][gcd變形] 10104 - Euclid Problem

回應(0)

I I U C O N L I N E C O N T E S T 2 0 0 8
Problem B: Triples
Input: standard input Output: standard output

Given a sequence of positive integers. You need to find the number of triples in that sequence. For this problem, (x, y, z) constructs a triple if and only if x + y = z. So, (1, 2, 3) is a triple, where (3, 4, 5) is not.
Input
Each input set starts with a positive integer N. Next few lines contain N positive integers. Input is terminated by EOF.
Output
For each case, print the number of triples in a line.
Constraints
- 3 ≤ N ≤ 5000
Sample Input	Output for Sample Input
6 1 2 3 4 5 6 6 1 2 4 8 16 32 3 100000000 200000000 100000000 5 1 1 1 2 2	6 0 1 6

Problem setter: Md. Kamruzzama