| Show all threads Hide all threads Show all messages Hide all messages | | help, i have a question on test 9.. | liuhy | 1162. Currency Exchange | 4 Oct 2023 18:35 | 6 | 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 | | WA on test 10, ac on poj | tahara | 1162. Currency Exchange | 6 Oct 2017 18:21 | 1 | please, how can I get test cases on this oj? | | Good problem! | wangbicheng1 | 1162. Currency Exchange | 11 Nov 2015 17:08 | 1 | You need to have a deep understanding of the bellman-ford algorithm, especially THE RELAXING OPERATION | | I do not understand an sample. help, please | alp | 1162. Currency Exchange | 23 Nov 2012 16:21 | 4 | 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 | | why i'm stucking at 9#point?any data can be showed? | asdffdsauiui | 1162. Currency Exchange | 11 Nov 2010 08:53 | 1 | | | Very easy problem) | Quiet WOLF | 1162. Currency Exchange | 30 Aug 2008 23:31 | 3 | 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... | | Why simple algorithm using Bellman-Ford is WA-ing on 10? | acid | 1162. Currency Exchange | 28 Dec 2006 16:51 | 7 | 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 | | Any hint? How to solve it with shortest path? | Maigo Akisame (maigoakisame@yahoo.com.cn) | 1162. Currency Exchange | 23 Jun 2006 14:12 | 10 | 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]" ?? | | Nice present for New Year. My AC 0.001s and only 660 bytes.(+ first attempt). | ACM.Tolstobrov_Anatoliy[Ivanovo SPU] | 1162. Currency Exchange | 2 Jan 2006 02:05 | 1 | | | I have one test, on which your AC programs may give incorrect answer (which use Belman-Ford mainly).(+) | Kit | 1162. Currency Exchange | 7 Jul 2005 12:23 | 1 | 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? | | What's wrong with my code? Give me any hint, please! | Wrong Limit Acces Violation | 1162. Currency Exchange | 4 Apr 2005 20:58 | 2 | 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. | | I got AC in the end. Just find the maximum way. | Yu YuanMing | 1162. Currency Exchange | 2 Jul 2004 17:52 | 1 | | | What's wrong with my program (Pascal)? Need help or some AC tests! | Alien | 1162. Currency Exchange | 26 Feb 2003 16:58 | 2 | 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. | | What's wrong with my program? Please,help me!!! | Nazarov Denis (nsc2001@rambler.ru) | 1162. Currency Exchange | 13 Jan 2002 22:12 | 5 | 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 wonder why the difficulty of this problem is so high,I think this problem is rather easy.(Email:"hyz12345678@163.com") | Huang Yizheng | 1162. Currency Exchange | 20 Dec 2001 18:17 | 2 | I know you work not by yourself, why do not you discuss in your team. |
|
|
