Cod sursa(job #120237)

Utilizator DastasIonescu Vlad Dastas Data 4 ianuarie 2008 18:07:09
Problema Ordine Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <cstdio>
#include <cstring>

const int maxn = 1000001;
const int maxa = 30;

FILE *in = fopen("ordine.in","r"), *out = fopen("ordine.out","w");

int n;
char a[maxn];
int fr[maxa];

int main()
{
	fscanf(in, "%s", a);

    n = strlen(a);
	for ( int i = 0; i < n; ++i )
        ++fr[ a[i] - 'a' ];

    int ex = 0;
    char which = 0;
    for ( char i = 'a'; i <= 'z'; ++i )
        if ( fr[ i - 'a' ] == (n / 2) + 1 )
            ex = 1, which = i;

    if ( ex )
    {
        for ( int i = 1; i <= n; ++i )
        {
            if ( i % 2 == 1 )
                fprintf(out, "%c", which);
            else
            {
                char what = 0;
                for ( char j = 'a'; j <= 'z'; ++j )
                    if ( j != which && fr[ j - 'a' ] )
                    {
                        what = j;
                        --fr[ j - 'a' ];
                        break;
                    }
                fprintf(out, "%c", what);
            }
        }

        return 0;
    }

    char prev = 0;
    for ( int i = 1; i <= n; ++i )
    {
        int ok = 0;
        char what = 0;

        for ( char j = 'a'; j <= 'z'; ++j )
            if ( fr[ j - 'a' ] == ((n - i + 1) / 2) + 1 )
                ok = 1, what = j;

        if ( ok )
            fprintf(out, "%c", what), --fr[ what - 'a' ], prev = what;
        else
        {
            for ( char j = 'a'; j <= 'z'; ++j )
                if ( fr[ j - 'a' ] > 0 && j != prev )
                {
                    --fr[ j - 'a' ];
                    what = j;
                    prev = j;
                    break;
                }

            fprintf(out, "%c", what);
        }
    }

	return 0;
}