Обсуждение @ 1162. Currency Exchange @ Timus Online Judge

liuhy help, i have a question on test 9.. [5] // Задача 1162. Currency Exchange 19 сен 2010 18:44

tahara WA on test 10, ac on poj // Задача 1162. Currency Exchange 6 окт 2017 18:21

wangbicheng1 Good problem! // Задача 1162. Currency Exchange 11 ноя 2015 17:08

alp I do not understand an sample. help, please [3] // Задача 1162. Currency Exchange 26 июн 2012 22:38

asdffdsauiui why i'm stucking at 9#point?any data can be showed? // Задача 1162. Currency Exchange 11 ноя 2010 08:53

Quiet WOLF Very easy problem) [2] // Задача 1162. Currency Exchange 14 авг 2007 22:21

acid Why simple algorithm using Bellman-Ford is WA-ing on 10? [6] // Задача 1162. Currency Exchange 7 дек 2006 16:49

Maigo Akisame (maigoakisame@yahoo.com.cn) Any hint? How to solve it with shortest path? [9] // Задача 1162. Currency Exchange 24 окт 2004 06:12

ACM.Tolstobrov_Anatoliy[Ivanovo SPU] Nice present for New Year. My AC 0.001s and only 660 bytes.(+ first attempt). // Задача 1162. Currency Exchange 2 янв 2006 02:05

Kit I have one test, on which your AC programs may give incorrect answer (which use Belman-Ford mainly).(+) // Задача 1162. Currency Exchange 7 июл 2005 12:23

Wrong Limit Acces Violation What's wrong with my code? Give me any hint, please! [1] // Задача 1162. Currency Exchange 4 апр 2005 20:47

Yu YuanMing I got AC in the end. Just find the maximum way. // Задача 1162. Currency Exchange 2 июл 2004 17:52

Alien What's wrong with my program (Pascal)? Need help or some AC tests! [1] // Задача 1162. Currency Exchange 7 май 2002 06:39

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.

Koala Ural uses Free Pascal to test your program. So {$apptype console} and uses sysutils is illegal! // Задача 1162. Currency Exchange 26 фев 2003 16:58

> 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.

Nazarov Denis (nsc2001@rambler.ru) What's wrong with my program? Please,help me!!! [4] // Задача 1162. Currency Exchange 13 янв 2002 15:30

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.

Christopher Moh Re: What's wrong with my program? Please,help me!!! [3] // Задача 1162. Currency Exchange 13 янв 2002 16:14

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.

shitty.Mishka There is a solution of O(m*n), right? [2] // Задача 1162. Currency Exchange 13 янв 2002 18:14

Christopher Moh Yes, there is an algorithm of O(MN) [1] // Задача 1162. Currency Exchange 13 янв 2002 21:23

Nazarov Denis (nsc2001@rambler.ru) Re: I don't know this algorithm, but my solution is very fast. You can see it in statistic. // Задача 1162. Currency Exchange 13 янв 2002 22:12

>

Huang Yizheng I wonder why the difficulty of this problem is so high,I think this problem is rather easy.(Email:"hyz12345678@163.com") [1] // Задача 1162. Currency Exchange 20 дек 2001 11:22

Обсуждение задачи 1162. Currency Exchange