program valiutos_keitimas;
  { 41 u‘davinys }
  const MAX_N = 10;  { maksimalus valstybi— skai‡ius }
  type kursai = array [1..MAX_N, 1..MAX_N] of real;
       marsrutas = array [1..MAX_N] of record
                                         pin: real;  { turim— pinig— kiekis }
                                         v: integer  {  kuri… valstybŠ }
                                       end;          { einama }
       aibe = set of 1..MAX_N; { aib‚ valstybi—, kuriose apsilankyta }

  procedure ieskoti (n: integer; k: kursai;
                     var rasta: boolean; { ar egzistuoja maržrutas }
                     var m: marsrutas;
                     var pradzia: integer; { kurioje valstyb‚je prasideda }
                                           { maržrutas }
                     var pelnas: real);

    var pasiekta: aibe; { aplankyt— valstybi— aib‚ }

    procedure eiti (var i: integer);
    { rekursin‚ proced–ra, iežkanti maržruto }
    { ji naudoja globalius kintamuosius: }
    { pasiekta, k, rasta, m, pradzia, pelnas }
      var j, t: integer;
          galima: boolean;
    begin
      pasiekta := pasiekta + [i];
      for j := 1 to n do
        if (k[i, j] <> 0) and not rasta  { jei galima eiti  j-t…j… valstybŠ }
        then if m[j].v = 0            { ir joje dar neb–ta }
             then begin
                    { apskai‡iuojame turim… pinig— kiek }
                    m[j].pin := m[i].pin * k[i, j];
                    m[i].v := j;
                    { gal b–t  ži… valstybŠ galima patekti tiesiogiai }
                    { iž jau apeit— valstybi— ir tur‚ti daugiau pinig— }
                    galima := false;
                    for t := 1 to n do
                      if (k[t, j] <> 0) and (m[t].pin <> 0) and (i <> t)
                         and (k[t, j] * m[t].pin >= m[j].pin)
                         then galima := true;
                    if not galima
                       then eiti (j);
                    if not rasta { gr‘tame per ‘ingsn atgal }
                       then begin
                              m[j].pin := 0;
                              m[i].v := 0
                            end;
                  end
             else if m[j].pin < m[i].pin * k[i, j]
                  then begin  { jei j-toje valstyb‚je jau b–ta }
                         rasta := true;
                         pradzia := j;
                         pelnas := m[i].pin * k[i,j] / m[j].pin * 100 - 100
                       end;
    end; { eiti }

    var i, j: integer;
  begin { iežkoti }
     rasta := false;
     for j := 1 to n do
       begin
         m[j].pin := 0;
         m[j].v := 0
       end;
     m[1].pin := 1.0;
     pradzia := 1; { pard‚sime keliauti nuo pirmosios valstyb‚s }
     pasiekta := [];
     for i := 1 to n do { bandome keliauti iž kiekvienos valstyb‚s }
       if not (i in pasiekta) and not rasta
          then begin
                 pradzia := i;
                 m[i].pin := 1.0;
                 eiti (i)
               end;
  end;

  var f: text;
      pelnas: real;
      n, i, j, ilgis, pradzia: integer;
      k: kursai;
      m: marsrutas;
      rasta: boolean;
begin
  assign (f, 'VALIUTOS.DAT');
  reset (f);
  readln (f, n);
  for i := 1 to n do
    begin
      for j := 1 to n do
        read (f, k[i, j]);
      readln (f)
    end;
  close (f);
  ieskoti (n, k, rasta, m, pradzia, pelnas);
  if not rasta
     then writeln ('PELNINGO MARŸRUTO NRA')
     else begin
            write ('PELNINGAS MARŸRUTAS: ');
            i := pradzia;
            repeat
              write (i, ' ');
              i := m[i].v
            until i = 0;
            writeln;
            writeln ('PELNAS: ', pelnas: 4: 1, '%')
          end
end.