Cod sursa(job #2736331)

Utilizator mariusn01Marius Nicoli mariusn01 Data 3 aprilie 2021 12:57:31
Problema Grozavesti Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>

using namespace std;
int a[301];
int b[301];
int v[301];
int n, m, i, j, x, minim, poz;
int main () {
    ifstream fin ("grozavesti.in");
    ofstream fout("grozavesti.out");
    fin>>n;
    for (i=1;i<=n;i++) {
        for (j=1;j<=n;j++) {
            fin>>x;
            if (i == j)
                v[i] = x;
        }
    }

    /**
    for (i=1;i<n;i++)
        for (j=i+1;j<=n;j++)
            if (v[i] > v[j]) {
                swap(v[i], v[j]);
            }
    **/
    /// care este numarul maxim de interschimbari care se poate ajunge sa se faca ?
    /// n(n-1)/2 de ordin n patrat
/**
    do {
        sortat = 1;
        for (i=1;i<n;i++)
            if (v[i] > v[i+1]) {
                sortat = 0;
                swap(v[i], v[i+1]);
            }
    } while (sortat == 0);
**/
    /// si aici, pe cazul cel mai defavorabil (al sirului sortat descrescator)
    /// se ajunge la n(n-1)/2 interschimbari (de ordin n patrat)

    for (i=1;i<n;i++) {
        minim = v[i];
        poz = i;
        for (j=i+1;j<=n;j++)
            if (v[j] <= minim) {
                minim = v[j];
                poz = j;
            }
        if (i!=poz) {
            swap(v[i], v[poz]);
            m++;
            a[m] = i;
            b[m] = poz;
        }
    }
    fout<<2*m<<"\n";
    for (i=1;i<=m;i++) {
        fout<<"L "<<a[i]<<" "<<b[i]<<"\n";
        fout<<"C "<<a[i]<<" "<<b[i]<<"\n";
    }

    return 0;
}