Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:因为他的程序有bug,他那样是骗分的,详见内

Posted by mofixroot at 2009-10-29 21:52:44 on Problem 1275
In Reply To:因为他的程序有bug,他那样是骗分的,详见内 Posted by:Liuzhaoliang at 2009-08-04 21:46:11
> 我觉得是因为他原来的程序过不了所以测试数据,不知怎么搞到了测试数据,发现只有n==4的一个测试用例过不了,而且正确答案是No solution.所有他就加上这一句来AC。   其实,他是忘了加 add(-1,23,ans)这条边。
> //冯威论文的程序,他的程序有小bug,已经修改。
> const
>   maxn=230;
> 
> var
>   g:array[-1..maxn,1..4]of record
>       n,v:integer;
>     end;
>   d,xu,num,a:array[-1..maxn]of integer;
>   ans:integer;
>   x,n,casen,o,i:integer;
>   flag:boolean;
> 
> procedure add(a,b,c:integer);
>   begin
>     inc(num[a]);
>     g[a,num[a]].n:=b;
>     g[a,num[a]].v:=c;
>   end;
> 
> procedure init;
>   var i:integer;
>   begin
>     fillchar(g,sizeof(g),0);
>     add(-1,23,ans);   //原程序没有加这条边
>     for i:=0 to 23 do begin
>       if i<=7  then add(i+16,i,xu[i]-ans)
>                else add(i-8,i,xu[i]);
>       add(i-1,i,0);
>       add(i,i-1,-a[i]);
>       
>     end;
>   end;
> 
> function bellman_ford:boolean;
>   var i,j,k:integer;
>       ff:boolean;
>   begin
>     bellman_ford:=false;
>     fillchar(d,sizeof(d),0);
>     for i:=0 to 23 do begin
>       ff:=true;
>       for j:=-1 to 23 do
>         for k:=1 to num[j] do
>           if d[j]+g[j,k].v>d[g[j,k].n] then begin
>             d[g[j,k].n]:=d[j]+g[j,k].v;ff:=false;
>           end;
>       if ff then break;
>     end;
>     for j:=0 to 23 do if d[j]-d[j-1]>a[j] then exit;
>     for j:=-1 to 23 do
>       for k:=1 to num[j] do
>         if d[j]+g[j,k].v>d[g[j,k].n] then exit;
>     
>     bellman_ford:=d[23]=ans; //这句,是判断 d[23]-d[-1]是否就是ans,直接返回true也能AC,可见数据不是很强。
>   end;
> 
> begin
> //  assign(input,'e:\input.txt');reset(input);assign(output,'e:\output.txt');rewrite(output);
>   readln(casen);
>   for o:=1 to casen do begin
>     for i:=0 to 23 do read(xu[i]);readln;readln(n);
>     for i:=1 to n do begin read(x);inc(a[x]);end;
>     flag:=false;
>     for ans:=0 to n do begin
>       fillchar(d,sizeof(d),0);
>       fillchar(num,sizeof(num),0);
>       init;
>       if bellman_ford then begin
>         flag:=true;
>         break;
>       end;
>     end;
>     if flag then writeln(ans) else writeln('No Solution');
>   end;
> //  close(output);close(input);
> end.
> 
> 这是论文里的程序,希望不被删贴。
> 
> 
> 
> 
> 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
> 4
> 0 8 16 23
> 
> 
> 比如这组数据,明显,我们取 0,8,16 这三个员工就能完成一天的工作,答案是3.而冯威的原程序,是输出无解的。

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator