Cod sursa(job #583543)

Utilizator radubbRadu B radubb Data 20 aprilie 2011 19:16:02
Problema Ordine Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <cstdio>
#include <string>
using namespace std;

#define nmax 1000001
long n, y;
char s[nmax], sout[nmax], c;
long q[27]; // quantity
bool poz[nmax];

void citire()
{
	
	freopen("ordine.in","r",stdin);
	scanf("%s", &s); n = strlen(s);
}

void afisare()
{
	freopen("ordine.out","w",stdout);
	if(poz[1])
		printf("%c", c); 
	for(long i=1; i<=y; i++)
	{
		if(poz[i])
			printf("%c", c); 
		printf("%c", sout[i]);
	}
}

void init()
{
	for(long i=0; i<n; i++)
		q[int(s[i])-'a']++;
}

void solve()
{
	int ant=-1, p=0;
	long n = ::n;
	for(; n; n--)
	{
		for(short i=0; i<=26; i++)
			if(q[i] && i!=ant)
			{
				sout[++y] = char(i+'a');
				q[i]--;
				ant = i;
				break;
			}
	}
	for(short i=0; i<=26; i++)
		if(q[i])
			p = i;
	if(p)
	{
		c = char('a'+p);
		for(long i=y; i>1; i--)
		{
			if(sout[i]!=c && sout[i-1]!=c)
			{
				poz[i-1] = true;
				if(--q[p]==0)
					break;
			}
		}
		if(q[int(c)])
			sout[0] = c; 
	}
}

int main()
{
	citire();
	init();
	solve();
	afisare();
	return 0;
}