ACM Linux 对拍程序写法

0x00 引入

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

0x01 实现方法

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

  1. 生成测试数据;
  2. 两个程序分别跑一遍,生成两个输出;
  3. 比较两个输出。

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.

我们需要在第一行生成一个1100的随机数n,在接下来n行生成共n个110000的随机数。

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

#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函数,是对拍程序不停地在 $$$$ 中不停循环

./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程序

可以看到第一个测试点就出现了错误。这样你也就收获了一个样例,用这个样例去debug吧

接下来测试正确的check程序

清一色的accept,说明程序没有问题,你可以按CTRL + C停止这个对拍程序

0x06 结尾

对拍在程序竞赛还是挺常见的,实在不知道那个程序点出错时,对拍总能帮上你一个忙。

全部评论

相关推荐

05-11 11:48
河南大学 Java
程序员牛肉:我是26届的双非。目前有两段实习经历,大三上去的美团,现在来字节了,做的是国际电商的营销业务。希望我的经历对你有用。 1.好好做你的CSDN,最好是直接转微信公众号。因为这本质上是一个很好的展示自己技术热情的证据。我当时也是烂大街项目(网盘+鱼皮的一个项目)+零实习去面试美团,但是当时我的CSDN阅读量超百万,微信公众号阅读量40万。面试的时候面试官就告诉我说觉得我对技术挺有激情的。可以看看我主页的美团面试面经。 因此花点时间好好做这个知识分享,最好是单拉出来搞一个板块。各大公司都极其看中知识落地的能力。 可以看看我的简历对于博客的描述。这个帖子里面有:https://www.nowcoder.com/discuss/745348200596324352?sourceSSR=users 2.实习经历有一些东西删除了,目前看来你的产出其实很少。有些内容其实很扯淡,最好不要保留。有一些点你可能觉得很牛逼,但是面试官眼里是减分的。 你还能负责数据库表的设计?这个公司得垃圾成啥样子,才能让一个实习生介入数据库表的设计,不要写这种东西。 一个公司的财务审批系统应该是很稳定的吧?为什么你去了才有RBAC权限设计?那这个公司之前是怎么处理权限分离的?这些东西看着都有点扯淡了。 还有就是使用Redis实现轻量级的消息队列?那为什么这一块不使用专业的MQ呢?为什么要使用redis,这些一定要清楚, 就目前看来,其实你的这个实习技术还不错。不要太焦虑。就是有一些内容有点虚了。可以考虑从PR中再投一点产出
点赞 评论 收藏
分享
我就是0offer糕手:北大不乱杀
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务