/*
   Sprendim… bei testus pareng‚ Mindaugas Plukas.
   Sprendimo pagrindas yra grafo tranzityvaus u‘darinio radimo algoritmas,
   pasi–lytas Floyd'o bei Warshall'o.
   Sprendimo id‚ja yra tokia. Tarkime, kad turime apskai‡iuot… valiut—
   santyki— lentelŠ, kai ižvestiniams santykiams apskai‡iuoti galima naudoti
   tarpines valiutas 1,...,k (k>=0); pa‘ym‚kime ži… lentelŠ V(k), o jos elementus -
   V(k)[i,j] ( i=1...N,j=1..N, cia N - valiutu kiekis). Tada valiutu santykiu
   lentele V(k+1), kai ižvestiniams santykiams apskai‡iuoti galima naudoti tarpines
   valiutas 1,...,k+1 , galime apskai‡iuoti tokiu b–du:
      V(k+1)[i,j] = V(k)[i,j], jei V(k)[i,j] != 0 ir
      V(k+1)[i,j] = V(k)[i,k+1] * V(k)[k+1,j], jei V(k)[i,j] = 0.

   Taigi , jei V(0) yra duotoji valiut— santyki— lentel‚, papildyta santykiais, kuriuos
   galime apskai‡iuoti be tarpini— valiut— pagalbos, tai V(N) bus iežkomoji galimai
   pilna valiut— santyki— lentel‚.

   Algoritmo operacij— skai‡ius yra apribotas C * N^3, ‡ia C - konstanta(nepriklausanti nuo N).

*/


#include <stdlib.h>
#include <stdio.h>



/*
  Valiut— santyki— lentelŠ saugome dvima‡iame masyve. Jo elementas [i][j]
  ( i=0,...,N-1, j=0,...,N-1 ) nusako kiek valstyb‚s (i+1) valiutos vienetas
  kainuoja valstyb‚s (j+1) valiutos vienet—.
*/
#define MAX_VALSTYBIU_SK  120
typedef float TSantykiuLentele[MAX_VALSTYBIU_SK][MAX_VALSTYBIU_SK] ;


int valstSk = 0 ;
TSantykiuLentele valiutuSant ;


void main()
{
   FILE *fpPrDuom = NULL ;
   FILE *fpRezDuom = NULL ;
   int i = 0, j = 0, k = 0 ;


   /* Nuskaitom pradinius duomenis */
   fpPrDuom = fopen( "VALIUTOS.DAT", "r" ) ;
   fscanf( fpPrDuom, " %d ", &valstSk ) ;
   for ( i = 0 ; i < valstSk ; i ++ )
     for ( j = 0 ; j < valstSk ; j ++ )
      {
        fscanf( fpPrDuom, " %f ", &valiutuSant[i][j] ) ;
      }
   fclose( fpPrDuom ) ;


   /* Apskai‡iuojam tr–kstamus tiesioginius(be tarpini— valiut—) santykius */
   for ( i = 0 ; i < valstSk ; i ++ )
     for ( j = 0 ; j < valstSk ; j ++ )
       if ( valiutuSant[i][j] == 0.0 )
        {
          if ( i == j )
           {
             valiutuSant[i][i] = 1.0 ;
           }
          else
           {
             if ( valiutuSant[j][i] != 0.0 )
               valiutuSant[i][j] = 1/valiutuSant[j][i] ;
           }
        }

   for ( k = 0 ; k < valstSk ; k ++ )
     /* Apskai‡iuojam santykius, kuriuos galima apskai‡iuoti pasinaudojant  */
     /* tarpin‚mis valiutomis {1,2,...,k+1}                                 */
    for ( i = 0 ; i < valstSk ; i ++ )
     for ( j = 0 ; j < valstSk ; j ++ )
       if ( valiutuSant[i][j] == 0.0 )
        {
          if ( valiutuSant[i][k] != 0.0 &&
               valiutuSant[k][j] != 0.0 )
            valiutuSant[i][j] = valiutuSant[i][k] * valiutuSant[k][j] ;
        }


   /* Ižvedam rezultat… */
   fpRezDuom = fopen( "VALIUTOS.REZ", "w" ) ;
   fprintf( fpRezDuom, "%d\n", valstSk ) ;
   for ( i = 0 ; i < valstSk ; i ++ )
    {
      for ( j = 0 ; j < valstSk ; j ++ )
        fprintf( fpRezDuom, "%12f  ", valiutuSant[i][j] ) ;
      fprintf( fpRezDuom, "\n" ) ;
    }
   fclose( fpRezDuom ) ;

}