Cod sursa(job #115076)

Utilizator alutzuAlexandru Stoica alutzu Data 16 decembrie 2007 10:38:48
Problema Grozavesti Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda 2, Clasele 5-8 Marime 3.57 kb
#include<stdio.h>
#define NMAX 315

int  n ;
long x [ NMAX ] [ NMAX ] ;

int ok ( )
     {

        int i , ok = 1 ;

        for ( i = 1 ; i < n && ok ; i ++ )
           if ( x [ i ] [ i ] > x [ i + 1 ] [ i + 1 ] )
              ok = 0 ;

        if ( ! ok )
           return ( i - 1 );

        return 0 ;


     }

void sch_lin ( int l1 , int l2 ) ;
void sch_col ( int c1 , int c2 ) ;

struct solutie
  {

      char tip ;
      int x , y ;

  };

solutie sol [ 2 * NMAX ] ;
int u ;

int main ( )
     {

          freopen ( "grozavesti.in" , "r" , stdin ) ;
          freopen ( "grozavesti.out" , "w" , stdout ) ;

          scanf ( "%d" , & n ) ;

          int i , j ;

          for ( i = 1 ; i <= n ; i ++ )
             for ( j = 1 ; j <= n ; j ++ )
                scanf ( "%ld" , & x [ i ] [ j ] ) ;

          long NR = 0 ;
          int bad ;

           while  ( ( bad = ok ( ) ) )
                {

                   NR ++ ;
                   //gasim cea mai buna varianta pentru bad

                   long min = x [ bad ] [ bad ] , mini = 0 , minj = 0;

                   for ( i = 1 ; i < bad ; i ++ )
							  if ( x [ i ] [ bad ] < min && x [ i ] [ bad ] > x [ bad - 1 ] [ bad - 1 ] )
                           {

                              min = x [ i ] [ bad ] ;
                              mini = i ;

                           }
                       else
                          if ( x [ bad ] [ i ] < min )
                            {

                               min = x [ bad ] [ i ] ;
                               minj = i ;

                            }


                   for ( i = bad + 1 ; i <= n ; i ++ )
							  if ( x [ i ] [ bad ] < min && x [ i ] [ bad ] > x [ bad - 1 ] [ bad - 1 ] )
                           {

                              min = x [ i ] [ bad ] ;
                              mini = i ;

                           }
                       else
                          if ( x [ bad ] [ i ] < min )
                            {

                               min = x [ bad ] [ i ] ;
                               minj = i ;

                            }

                   if ( mini ) //interschimbam doua LINII
                       {

                           sol [ ++ u ] . tip = 'L' ;
                           sol [ u ] . x = bad ;
                           sol [ u ] . y = mini ;
                           sch_lin ( bad , mini ) ;

                       }
                   else
                         {

									   sol [ ++ u ] . tip = 'C' ;
                              sol [ u ] . x = bad ;
                              sol [ u ] . y = minj ;
                              sch_col ( bad , minj ) ;

                         }

                }


          printf ( "%ld\n" , NR ) ;

          for ( i = 1 ; i <= u ; i ++ )
             printf ( "%c %d %d\n" , sol [ i ] . tip , sol [ i ] . x , sol [ i ] . y ) ;

          return 0 ;
     }

void sch_col ( int l1 , int l2 )
     {
         int i , aux ;

         for ( i = 1 ; i <= n ; i ++ )
            {

                aux = x [ i ] [ l1 ] ;
                x [ i ] [ l1 ] = x [ i ] [ l2 ] ;
                x [ i ] [ l2 ] = aux ;

            }
     }

void sch_lin ( int c1 , int c2 )
     {

         int i , aux ;

         for ( i = 1 ; i <= n ; i ++ )
            {

                aux = x [ c1 ] [ i ] ;
                x [ c1 ] [ i ] = x [ c2 ] [ i ] ;
                x [ c2 ] [ i ] = aux ;

            }

     }