can you please share the Idea of test 3? Notice, that you can move duons alongside diagonal (A->F, A->H, G->E, ...) First sample != test 1 :( Edited by author 25.01.2017 09:23 Why for test 1 0 1 0 3 1 0 0 answer EF- AE- DH+ CD- EH- is wrong? "You should right a program that helps scientists get rid of troubleduons." => "You should write a program that helps scientists get rid of troubleduons." New tests were added. 112 authors lost AC verdict. vector<pair<int,int> > add,rem; .... my program crashed(acess v..) many times, but it got ac after i have commented this code! i suppose there is no data that can make this code crash...maybe there are some troubles in Intel C++ compiler ? for(int i=int(add.size())-1;i>=0;--i) ____for(int j=int(rem.size())-1;j>=0;--j) ________if(add[i]==rem[j]) ____________add.erase(add.begin()+i), ____________rem.erase(rem.begin()+j); Edited by author 25.06.2007 16:34 Old validator was fixed, during rejudge 7 submits changed verdict. for the text:1 0 1 0 3 1 0 0 why the answer can't be AE- EF- DH+ CD- EH- It's also right! it can Edited by author 08.08.2005 23:35 Edited by author 08.08.2005 23:35 My solution: 1. (A+C+F+H)-(B+D+E+G)=const => if const!=0 then IMPOSSIBLE 2. While we have to destroy some we do two operations. (3,4) 3. If we can do one of (AB, BC, CD, DA, EF, FG, GH, HE, AE, BF, CG, DH)- we do it. 4. If AG => BF+ AB- GF- If BH => CG+ BC- HG- If CE => DH+ CD- EH- If DF => AE+ DA- FE- Why it gets WA #5? Is it wrong algorithm or wrong realization?
My code: Here was nearly AC code :) Edited by author 30.05.2005 05:31 though I don't know what "2. While we have to destroy some we do two operations. (3,4)" mean, I think you solution is right,because I got AC in the same way.maybe there's some bugs in your code. 2, 3 and 4 are right. 1 is wrong. const may be different from 0 when there is a solution Are you sure? Can you give me example? I can prove it: We process operation with pair of vertexes. The one is in {A,C,F,H} another is in {B,D,E,G}. So (A+C+F+H)-(B+D+E+G)=const Supose we already annighilated all 'troubles' then A=B=C=D=E=F=G=H=0 => const=0 => If const is not equal to zero we can't annighilate all 'troubles' => IMPOSSIBLE What is wrong in it? Algorithm is Ok, but in my code was one misprint. Here's my idea: we eliminate all adjacent values on sides by minimum value. Finally there will be only values on the diagonals. We "grow" the common sides with the minimum from the two values and then cut the other two sides. After a few operations like this we have one vertex. If it's != 0 there is no solution. const way:Array[1..8] of byte=(8,7,6,5,1,2,3,4); list:array[1..8,0..3] of byte=( (2,2,4,0),(1,3,0,0),(1,4,0,0),(0,0,0,0), (1,1,0,0),(2,2,5,0),(2,3,6,0),(3,4,5,7)); tt:string='ABCDEFGH'; maxn=10000; var a:Array[1..8] of integer; i,j,k,p,q,r,tot:longint; s:array[1..maxn] of string[3]; begin fillchar(s,sizeof(s),0); tot:=0; fillchar(a,sizeof(A),0); for i:=1 to 8 do read(a[i]);readln; if a[1]+a[3]+a[6]+a[8]<>a[2]+a[4]+a[5]+a[7] then begin writeln ('IMPOSSIBLE');halt;end; for i:=1 to 7 do begin p:=way[i]; for j:=1 to list[p,0] do if a[p]>0 then begin if a[p]<=a[list[p,j]] then begin for k:=1 to a[p] do begin inc(tot); s[tot]:=tt[p]+tt[list[p,j]]+'-'; end; dec(a[list[p,j]],a[p]); a[p]:=0; end else begin q:=list[p,j]; for k:=1 to a[q] do begin inc(tot);s[tot]:=tt[p]+tt[q]+'-'; end; dec(a[p],a[q]);a[q]:=0; end; end; if (a[p]>0) then begin q:=way[i+1];r:=way[i+2]; for k:=1 to a[p] do begin inc(tot);s[tot]:=tt[q]+tt[r]+'+'; inc(tot);s[tot]:=tt[p]+tt[q]+'-'; end; a[q]:=a[p];a[p]:=0;inc(a[r],a[q]); end; end; for i:=1 to tot do writeln(s[i]); end. > Could you give me an idea?? > > Could you give me an idea?? You must use full search to solve the problem. If sum of al trou.. is not diveded by 2 then it is IMPOSSIBLE to show the need way. If you want more help you can send to e-mail nsc2001@rambler.ru P.S. Please, give me an idea for problem 1146. :-)) CAREFUL 8-) 1 0 1 0 0 0 0 0 If you get this input there will be no solution even though the sum can be devided by 2. THe problem is fairly easy indeed allthough you might need some math skills to paint the cameras in 2 colors. (damn ...2 is a magin number) P.S. Email me too if you know how to solve 1146 : swin@mail2000.ru Welcome to email to "hyz12345678@163.com". |
|