ACM Linux 对拍程序写法

0x00 引入

我们知道样例是靠不住的，样例是只要是个算法都能过的，我们可以用一种更可靠的方式来验证——对拍。

0x01 实现方法

对拍，就是将两个程序给相同的输入，看看输出是否一样

生成测试数据；
两个程序分别跑一遍，生成两个输出；
比较两个输出。

0x02 准备

一个能够保证正确的程序
一个你准备验证的程序
一个数据生成程序
对拍程序

0x03 数据生成

数据生成很简单，就是指定系统随机生成你需要的数据。
在C++中，我们有rand()函数来生成随机数。

#include <bits/stdc++.h>
using namespace std;

int main(){
    for(int i = 0; i < 10; i++){
        printf("%d\n", rand());
    }
}

但是直接调用该函数出来的是伪随机数，每次运行程序，生成的数据都是相同的。

因为这个程序的随机数种子都是相同的，我们应该在每次生成数据之前设置不同的随机数种子。
在程序最前面加上srand((unsigned int)time(NULL));
将当前种子设置为时间即一秒一变就可以保证每次程序运行的随机数种子不同了

#include <bits/stdc++.h>
using namespace std;

int main(){
    srand((unsigned int)time(NULL));
    for(int i = 0; i < 10; i++){
        printf("%d\n", rand());
    }
}

那么接下来拿题目来举例子。
POJ - 1862 Stripies为例，首先看输入要求

The first line of the input contains one integer N (1 <= N <= 100) - the number of stripies in a colony. Each of next N lines contains one integer ranging from 1 to 10000 - the weight of the corresponding stripie.

我们需要在第一行生成一个1~~100的随机数n，在接下来n行生成共n个1~~10000的随机数。

那么我们可以写下这个程序

#include <bits/stdc++.h>
using namespace std;

int main(){
    srand((unsigned int)time(NULL));

    int n = rand() % 100;
    printf("%d\n", n);
    for(int i = 0; i < n; i++){
        printf("%d\n", rand() % 10000);
    }
}

查看生成的数据

这样一组数据就生成好了

0x04 对拍程序

生成完了数据生成程序之后，接下来就是要让对拍程序对两个程序进行校对。
有两种方法写对拍程序，一种是bash程序，一种是cpp程序。

这里以bash为例子。直接上代码

i=0
while true; do
    let i++
    ./createData > in
    ./check < in > out1
    ./correct < in > out2
    if diff out1 out2 ; then
        printf "Accept in case $i \n"
    else
        printf "Wrong Answer in case $i\n"
        printf "************\ninput: \n"
           cat < in    
        exit 0;
    fi
done

解释一下这一段程序。

文件名	作用
createData	数据生成文件
correct	标准程序
check	待测程序

第二行中的while函数，是对拍程序不停地在 $$ $生成数据 \rightarrow 运行标准程序 \rightarrow 运行待测程序 \rightarrow 比较两者输出程序 \rightarrow 生成数据 \rightarrow .............$ $$ 中不停循环

./createData > in 表示运行一次数据生成文件，并将生成的数据重定向至in文件
./check < in > out1表示运行一次待测程序，从in文件输入，并将运行结果重定向至out1文件
./correct < in > out2表示运行一次标准程序，从in文件输入，并将运行结果重定向至out2文件
if diff out1 out2 ; then判断两个输出文件是否相同，如果相同则输出Accept；如果不同则输出Wrong Answer，输出错误的input并退出对拍程序。

0x05 运行对拍程序

写完对拍程序后，开始进行对拍。
如果是第一次运行对拍程序，记得chmod 777 gocheck.sh以保证能够运行程序.

接下来是各个程序的代码：

createData.cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
    srand((unsigned int)time(NULL));

    int n = rand() % 100;
    printf("%d\n", n);
    for(int i = 0; i < n; i++){
        printf("%d\n", rand() % 10000);
    }
}

correct.cpp

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

typedef long double ld;

const int MAXN = 25000 + 10;


int main() {

    int n;
    cin >> n;
    vector<ld> v(n);

    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
    sort(v.begin(), v.end(), greater<ld>());
    ld res = v[0];
    for(int i = 1; i < n; i++){
        res = 2 * sqrt(res * v[i]);
    }
    printf("%.3LF\n", res);
}

错误的check.cpp (感谢学弟的友情提供www)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{
    int n;double a[10000];
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%lf",&a[i]);
    }
    sort(a,a+n);
    for(int i=n-1;i>0;i--){
        a[i-1]=2*sqrt(a[i-1]*a[i]);
    }
    printf("%.3f\n",a[1]);
}

正确的check.cpp (感谢学弟的友情提供www)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{
    int n;double a[10000];
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%lf",&a[i]);
    }
    sort(a,a+n);
    for(int i=n-1;i>0;i--){
        a[i-1]=2*sqrt(a[i-1]*a[i]);
    }
    printf("%.3f",a[0]);
}

gocheck.sh

i=0
while true; do
    let i++
    ./createData > in
    ./check < in > out1
    ./correct < in > out2
    if diff out1 out2 ; then
        printf "Accept in case $i \n"
    else
        printf "Wrong Answer in case $i\n"
        printf "************\ninput: \n"
           cat < in    
        exit 0;
    fi

done

接下来编译前三个文件，得到3个可执行文件。
接下来只需要在终端输入./gocheck.sh即可开始该对拍程序.

我们先测试错误的check程序