-1

这段代码在spoj中得到了错误的答案 我想要更强大的测试用例来检查我的代码..帮助表示赞赏..

SUM 问题可以表述如下:给定四个整数值列表 A、B、C、D,计算有多少四元组 (a, b, c, d) 属于 A x B x C x D 使得 a + b + c + d = 0 。在下文中,我们假设所有列表具有相同的大小 n

输入

输入文件的第一行包含列表 n 的大小(这个值可以大到 4000)。然后,我们有 n 行包含四个整数值(绝对值与 2^28 一样大),它们分别属于 A、B、C 和 D 。

例子

输入:

6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45

输出:

5

#include<stdio.h>
#include<stdlib.h>

int binarys(int a,long int b[],int low,int up,int k)
{
    int par;

    if(low <= up) {
        par = partition(low,up,b);
        if(b[par] + a == 0) {
            k = k + 1;
            k = binarys(a,b,low,par-1,k);
            k = binarys(a,b,par+1,up,k);
        }
        if(b[par] > -1*a)
            k = binarys(a,b,low,par-1,k);
        if(b[par] < -1*a)
            k = binarys(a,b,par+1,up,k);
    }
    return k;
}

int partition(int low,int up,int b[])
{
    int i;
    int j;
    int m;
    int a;

    j = low - 1;
    m = b[up];

    for(i=low; i < up; i++) {
        if(b[i] <= m ) {
            j++;
            a = b[i];
            b[i] = b[j];
            b[j] = a;
        }
    }
    a = b[j+1];
    b[j+1] = b[up];
    b[up] = a;

    return j + 1;
}

int main()
{
    long int *A = NULL;
    long int *B = NULL;
    long int *C = NULL;
    long int *D = NULL;
    long int *a = NULL;
    long int *b = NULL;
    int n;
    int i;
    int j;
    int k;
    int l;
    int sum;

    scanf("%d",&n);

    k = 0;
    sum = 0;
    A = (long int*)malloc(n*sizeof(long int));
    B = (long int*)malloc(n*sizeof(long int));
    C = (long int*)malloc(n*sizeof(long int));
    D = (long int*)malloc(n*sizeof(long int));
    a = (long int*)malloc(n*n*sizeof(long int));
    b = (long int*)malloc(n*n*sizeof(long int));

    for(i=0; i < n; i++) {
        scanf("%d%d%d%d",&A[i],&B[i],&C[i],&D[i]);
    }

    for(i=0; i < n; i++) {
        for(j=0; j < n; j++) {
            a[k] = A[i] + B[j];
            b[k] = C[i] + D[j];
            k++;
        }
    }

    for(i=0; i < n*n; i++) {
        l = binarys(a[i],b,0,n*n,0);
        sum = sum + l;
    }
    printf("%d",sum);
    return 0;

}
4

1 回答 1

2

使用 gcc 4.7.2 编译,-Wall -Wextra -Wshadow

a.c: In function ‘binarys’:
a.c:9:9: warning: implicit declaration of function ‘partition’ [-Wimplicit-function-declaration]
a.c: In function ‘main’:
a.c:75:9: warning: format ‘%d’ expects argument of type ‘int *’, but argument 2 has type ‘long int *’ [-Wformat]
a.c:75:9: warning: format ‘%d’ expects argument of type ‘int *’, but argument 3 has type ‘long int *’ [-Wformat]
a.c:75:9: warning: format ‘%d’ expects argument of type ‘int *’, but argument 4 has type ‘long int *’ [-Wformat]
a.c:75:9: warning: format ‘%d’ expects argument of type ‘int *’, but argument 5 has type ‘long int *’ [-Wformat]

您的示例测试用例

$ ./a
6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45
0$

它既不符合您提供的期望 (5),也不在输出后打印换行符。评分者可能会期待换行并拒绝您的程序,因为您没有编写它。

其他基本测试用例

$ ./a
1
0 0 0 0
2

预期 1。

$ ./a
2
1 1 1 1
-3 100 100 100
0

预期 1。

$ ./a
2
-1 2 2 2
-2 3 3 3
2

预期为 0。

$ ./a
1
9223372036854775807 -9223372036854775808 1 0   // LONG_MAX, LONG_MIN on my architecture
0

预期 1。

$ ./a
0
0

正确答案0!

于 2013-05-29T12:17:53.670 回答