it is said that the testcase 9 is as follow: 4 4 1 11.1 1 2 2.0 0.5 0.5 0.5 2 3 1.05 1 0.01 1.0 3 4 1.05 1 0.01 1.0 4 2 1.05 1 0.01 1.0 the right answer is YES. but i think there is no possibility to increase his money, so the answer should be NO. could someone explain this test case to me.? thanks a lot.. Edited by author 19.09.2010 18:45 Oh, such a ridiculous situation! Edited by author 19.09.2010 18:58 Edited by author 19.09.2010 18:58 i know it....something wrong with my brain. I'm the same with you…… it showed the ans as: NO ……………… 3 2 1 100.0 1 2 1.0 0.0 1.0 10000 2 3 1.1 0.0 1.1 0.0 please, how can I get test cases on this oj? You need to have a deep understanding of the bellman-ford algorithm, especially THE RELAXING OPERATION how Andrey will increase the capital? 2: (20-1)*1 =19 3: (19-1)*1=18 **** How can more, than 20? thank I understood,...:) Edited by author 18.02.2017 01:54 I'm too... Please, somebody explane sample. Why I can only increase money: 1->2 (20-1)*1=19 2->3 (19-1)*1.1=19.8 3->2 (19.8-1)*1.1=20.68 2->1 (20.68-1)*1=19.68 Where I mistake. Or Nick can just do all day 2->3 3->2 2->3 3->2 ........ ........ 2->3 3->2 and when he will have INF money, he exchange currency from 2 on 1. =) Edited by author 10.10.2012 03:56 just ignore the words "Let us call some sequence of the exchange operations simple if no exchange point is used more than once in this sequence." it's sample spfa Write Bellman-Ford. And receive AC :) This problem can easily be solved by DFS in 0.001 time. I also think that there are several other ways to get AC. But looking at the forum, it seems that there is only one correct solution by Bellman-Ford algo. It is disappointing statement No, I've solved it just with DP with some optimizations to avoid TLE... Please give me some tricky tests, I have 22 attempts on this problem and I can't solve it. I have the same problem. Please help !!! You mean you are the same man, uh? :D Can't you say somethin usefull? I know that there are people who got WA10 using Bellman-Ford and AC-ed it after a while. Please help... I have AC using Bellman_Ford. Algoritm needs some attention in adaptation. But what your want just real work in verification of your program. In other words specialist will make comparison your code and all steps of right algorithm. I thihk that is field for business. Thanks, it was just a floating point error. After adding an Eps = 1e-5 I've got AC. Giorgi Saghinadze: > lol I'll catch you man :D Bellman-Ford. Do Bellman-Ford once to find the longest path. If there is a positive cycle then Yes,otherwise No. I am in contest know please help I must solve this problem 1217. N = 12, 14, 16. 12--3052783504 14--266095289560 16--23194144960900 GL! [code deleted] Edited by moderator 23.06.2006 17:15 this is wrong: ... else begin writeln('YES'); halt; end; It isn't necessarily a YES. You can't be sure that there's positive cycle by only condition that you've found 2 different positive values for money[b]. Your code can be easily modified (took me 1 min) though in such a way that you get AC, checking the condition of 'YES' answer correctly. I can write you an email, telling how to do that, if you want. [code deleted] Edited by moderator 23.06.2006 17:15 another question : "pre[b]:=pre[a]+pre[b]+[a];" May I use "pre[b]:=pre[a]+[a]" ?? 3 2 1 10 1 2 1 0 10 100 2 3 1.01 0 1 0 Right answer: YES. First operation: 1 => 2. Sum[2] = 10. Second operation: (2 => 3) & (3 => 2). Sum[2] = 10*1.01. Repeat {second operation} until {sum[2] > 101}. Third action: 2 => 1. Sum[1] = (sum[2] - 100)*10 > 10. May be, I did not understood 1162? Condition about "simple sequences" obviously hold. Bellman-Ford will not find such long cycle. I am right? I have WA on #10. Here is a prog: type long = record x,y : longint; rx,cx,ry,cy : real; end; var d : array [1..100] of real; a : array [1..100] of long; i,j,n,m,s : longint; procedure inp; begin fillchar(d,sizeof(d),0); read(n,m,s,d[s]); for i := 1 to m do with a[i] do read(x,y,rx,cx,ry,cy); end; procedure find; begin for i := 1 to n-1 do for j := 1 to m do begin if ((d[a[j].x]-a[j].cx)*a[j].rx > d[a[j].y]) then d[a[j].y] := (d[a[j].x]-a[j].cx)*a[j].rx; if ((d[a[j].y]-a[j].cy)*a[j].ry > d[a[j].x]) then d[a[j].x] := (d[a[j].y]-a[j].cy)*a[j].ry; end; end; procedure out; begin for i := 1 to m do begin if ((d[a[i].x]-a[i].cx)*a[i].rx > d[a[i].y]) then begin writeln('YES'); halt; end; if ((d[a[i].y]-a[i].cy)*a[i].ry > d[a[i].x]) then begin writeln('YES'); halt; end; end; writeln('NO'); end; begin inp; find; out; end. program P1162; {$APPTYPE CONSOLE} uses SysUtils; const Max=100; var n,m,s:integer; Value,Temp:real; a:array[1..Max] of real; b:array[1..Max] of 0..1; c:array[1..Max] of 0..100; AB:array[1..2*Max,1..2] of integer; RV:array[1..2*Max,1..2] of real; i,j,ci,cx,x,y:integer; procedure input; var i:integer; begin readln(n,m,s,Value); for i:=1 to n do begin a[i]:=0; b[i]:=0; c[i]:=0; end; a[1]:=Value; b[1]:=1; cx:=1; c[1]:=1; for i:=1 to m do begin read(x,y); AB[i,1]:=x; AB[i,2]:=y; read(RV[i,1],RV[i,2]); AB[m+i,1]:=y; AB[m+i,2]:=x; read(RV[m+i,1],RV[m+i,2]); end; end; procedure main; function FindValue(x:integer):real; var Te:real; begin Te:=(a[AB[x,1]]-RV[x,2])*RV[x,1]; FindValue:=Te; end; begin ci:=1; while ci<=cx do begin for i:=1 to 2*m do if AB[i,1]=c[ci] then begin j:=AB[i,2]; Temp:=FindValue(i); if Temp>a[j] then begin a[j]:=Temp; if b[j]=0 then begin b[j]:=1; inc(cx); c[cx]:=j; end; end; if a[1]>Value then begin writeln('YES'); halt(0); end; end; b[c[1]]:=0; dec(cx); for i:=1 to cx do c[i]:=c[i+1]; end; writeln('NO'); end; begin input; main; end. > program P1162; > {$APPTYPE CONSOLE} > uses > SysUtils; > > const Max=100; > var > n,m,s:integer; > Value,Temp:real; > a:array[1..Max] of real; > b:array[1..Max] of 0..1; > c:array[1..Max] of 0..100; > AB:array[1..2*Max,1..2] of integer; > RV:array[1..2*Max,1..2] of real; > i,j,ci,cx,x,y:integer; > procedure input; > var > i:integer; > begin > readln(n,m,s,Value); > for i:=1 to n do > begin > a[i]:=0; > b[i]:=0; > c[i]:=0; > end; > a[1]:=Value; b[1]:=1; > cx:=1; c[1]:=1; > for i:=1 to m do > begin > read(x,y); > AB[i,1]:=x; AB[i,2]:=y; > read(RV[i,1],RV[i,2]); > AB[m+i,1]:=y; AB[m+i,2]:=x; > read(RV[m+i,1],RV[m+i,2]); > end; > end; > procedure main; > function FindValue(x:integer):real; > var > Te:real; > begin > Te:=(a[AB[x,1]]-RV[x,2])*RV[x,1]; > FindValue:=Te; > end; > begin > ci:=1; > while ci<=cx do > begin > for i:=1 to 2*m do > if AB[i,1]=c[ci] then > begin > j:=AB[i,2]; > Temp:=FindValue(i); > if Temp>a[j] then > begin > a[j]:=Temp; > if b[j]=0 then > begin > b[j]:=1; > inc(cx); > c[cx]:=j; > end; > end; > if a[1]>Value then > begin > writeln('YES'); > halt(0); > end; > end; > b[c[1]]:=0; > dec(cx); > for i:=1 to cx do > c[i]:=c[i+1]; > end; > writeln('NO'); > end; > begin > input; > main; > end. My program: Program t1162;{$N+} Const MaxM=100; Eps=1E-15; Type Point=record S1,S2 :integer; RS1S2 :extended; CS1S2 :extended; RS2S1 :extended; CS2S1 :extended; end; Var N,M,S,i,j :integer; V,CurV :extended; CurS,step :integer; P :array[1..MaxM]of Point; Procedure Rec; var i :integer; predv :extended; begin step:=step+1; if CurS=S then if CurV-V>Eps then begin Writeln('YES'); Halt(0); end; if step>15000 then exit; predv:=curv; for i:=1 to m do if p[i].s1=curs then if curv>p[i].cs1s2 then begin curs:=p[i].s2; curv:=(curv-p[i].cs1s2)*p[i].rs1s2; rec; curv:=predv; curs:=p[i].s1; end; for i:=1 to m do if p[i].s2=curs then if curv>p[i].cs2s1 then begin curs:=p[i].s1; curv:=(curv-p[i].cs2s1)*p[i].rs2s1; rec; curv:=predv; curs:=p[i].s2; end; step:=step-1; end; begin Read(N,M,S,V); for i:=1 to M do read(P[i].S1,P[i].S2,P[i].rS1S2,P[i].cS1S2,P[i].rS2S1,P[i].cS2S1); CurV:=V; CurS:=S; step:=0; Rec; Writeln('NO'); end. Well, firstly, it may take more than 15000 steps before a correct solution is found. 15000 is way too little actually... secondly, isn't your solution kind of slow? There's a polynomial time algorithm to solve it. I know you work not by yourself, why do not you discuss in your team. |
|