PKU 2844. Sum and Product. [판정:TLE]

Solutions/Mr.K's Solution

PKU 2844. Sum and Product. [판정:TLE]

Milkskin 2010. 5. 29. 01:13

으잌ㅋ

3초 안에 답이 안나오는 케이스가 있다닠ㅋㅋㅋ

나 안햌ㅋㅋㅋㅋㅋㅋㅋ

#include <iostream>
#include <list>
using namespace std;

#define PMAX 8 // maximum quantity of primes
#define FMAX 27 // maximum quantity of factors

class GSet // Given Set
{
public:
	int iN;
	int iS;
	int iP;
};

class CSet // Calculating Set
{
public:
	int iN;
	int iS;
	int iP;
	int iaPrimeSet[PMAX];
	int iaPrimeExp[PMAX];
	int iaFactorSet[FMAX];

CSet()
	{
		int iIterA;

for( iIterA = 0; iIterA < PMAX; iIterA++ )
		{
			iaPrimeSet[iIterA] = 0;
			iaPrimeExp[iIterA] = 0;
		}

for( iIterA = 0; iIterA < FMAX; iIterA++ )
		{
			iaFactorSet[iIterA] = 0;
		}
	}
	void minimal_setting();
	void pressure( int iRemoving );
	void refresh();
};

class SQSet // Sequence Set
{
public:
	int iaFactorSet[FMAX];

SQSet()
	{
		int iIterA;

for( iIterA = 0; iIterA < FMAX; iIterA++ )
		{
			iaFactorSet[iIterA] = 0;
		}
	}
	void assign( CSet sCal );
	void print();
};

void factorize( int iComposite, int *iaPSet, int *iaPExp );
void ones( int iNum, char *cpLastchar );
void sorting( int *iaSet, int iLength );
int extendable( CSet sCal, GSet sDes );
int unite( CSet &sCal, GSet sDes );
void separate( CSet &sCal );
void analyze( GSet sGiven );

////////////////////////////////////////////

int main()
{
	GSet sGiven;

scanf( "%d %d %d", &sGiven.iN, &sGiven.iS, &sGiven.iP );

analyze( sGiven );

return 0;
}

////////////////////////////////////////////

void CSet::minimal_setting()
{
	int iIterA;
	int iIterB;
	int iTemp = 0;

iN = 0;
	iS = 0;
	for( iIterA = 0; iaPrimeSet[iIterA] != 0; iIterA++ )
	{
		iN += iaPrimeExp[iIterA];
		iS += iaPrimeSet[iIterA] * iaPrimeExp[iIterA];
	}

for( iIterA = 0; iaPrimeSet[iIterA] != 0; iIterA++ )
	{
		for( iIterB = 0; iIterB < iaPrimeExp[iIterA]; iIterB++, iTemp++ )
		{
			iaFactorSet[iTemp] = iaPrimeSet[iIterA];
		}
	}
}

void CSet::pressure( int iRemoving )
{
	list<int> lTemp;
	int iIterA;
	int iTemp;

for( iIterA = 0; iIterA < iN; iIterA++ )
	{
		lTemp.push_back( iaFactorSet[iIterA] );
	}

for( iIterA = 0; iIterA < iRemoving; iIterA++, iN-- )
	{
		iTemp = lTemp.front();
		lTemp.pop_front();
		iTemp *= lTemp.front();
		lTemp.pop_front();
		lTemp.push_front( iTemp );
		lTemp.sort();
	}

for( iIterA = 0; iIterA < (iN + iRemoving); iIterA++ )
	{
		iaFactorSet[iIterA] = 0;
	}

iS = 0;
	for( iIterA = 0; iIterA < iN; iIterA++ )
	{
		iaFactorSet[iIterA] = lTemp.front();
		iS += iaFactorSet[iIterA];
		lTemp.pop_front();
	}
}

void CSet::refresh()
{
	int iIterA;

iS = 0;
	for( iIterA = 0; iIterA < FMAX; iIterA++ )
	{
		iS += iaFactorSet[iIterA];
	}
}

void SQSet::assign( CSet sCal )
{
	int iIterA;

for( iIterA = 0; iIterA < FMAX; iIterA++ )
	{
		iaFactorSet[iIterA] = sCal.iaFactorSet[iIterA];
	}
}

void SQSet::print()
{
	int iIterA;

for( iIterA = 0; iaFactorSet[iIterA] == 0; iIterA++ ) { ; }

for( ; (iaFactorSet[iIterA + 1] != 0) && (iIterA < FMAX - 1); iIterA++ )
	{
		printf( "%d ", iaFactorSet[iIterA] );
	}

printf( "%d\n", iaFactorSet[iIterA] );
}

////////////////////////////////////////////

void factorize( int iComposite, int *iaPSet, int *iaPExp )
{
	int iIterA = 0;
	int iTemp;

if( iComposite % 2 == 0 )
	{
		iaPSet[0] = 2;

while( iComposite % 2 == 0 )
		{
			iComposite /= 2;
			iaPExp[0]++;
		}

iIterA++;
	}

iTemp = 3;
	while( iComposite > 1 )
	{
		if( iComposite % iTemp == 0 )
		{
			iaPSet[iIterA] = iTemp;

while( iComposite % iTemp == 0 )
			{
				iComposite /= iTemp;
				iaPExp[iIterA]++;
			}

iIterA++;
		}

iTemp += 2;
	}
}

void ones( int iNum, char *cpLastchar )
{
	int iIterA;

// print "1" iNum-1 times
	for( iIterA = 1; iIterA < iNum; iIterA++ ) { printf( "1 " ); }

// print last "1"
	if( iNum > 0 ) { printf( "1%s", cpLastchar ); }
}

void sorting( int *iaSet, int iLength )
{
	list<int> lTemp;
	int iIterA;

for( iIterA = 0; iIterA < iLength; iIterA++ )
	{
		lTemp.push_back( iaSet[iIterA] );
	}

lTemp.sort();

for( iIterA = 0; iIterA < iLength; iIterA++ )
	{
		iaSet[iIterA] = lTemp.front();
		lTemp.pop_front();
	}
}

int extendable( CSet sCal, GSet sDes )
{
	// whether or not sCal becomes to sDes by extending {1, 1, 1}
	// if possible, then return number of {1, 1, 1}
	// if impossible, then return -1
	int iDiffN;
	int iDiffS;

iDiffN = sDes.iN - sCal.iN;

iDiffS = sDes.iS - sCal.iS;

if( (iDiffN >= 0) && (iDiffS >= 0) && (iDiffN == iDiffS) ) { return iDiffN; }
	else { return -1; }
}

int unite( CSet &sCal, GSet sDes )
{
	const int iMaxTrial = 8;
	static int iCallingU = 0; // number of calling unite()
	int iRemainDiffs = sDes.iS - (sDes.iN - sCal.iN) - sCal.iS;
	int iTemp;
	int iIterA;
	int iIterB;

iCallingU++;

// iRemainDiffs is odd
	if( iRemainDiffs % 2 == 1 )
	{
		if( (sCal.iaPrimeSet[0] == 2) && (sCal.iaPrimeExp[0] >= 2) )
		{
			iRemainDiffs--;
			sCal.iaPrimeExp[0] -= 2;
			sCal.iaFactorSet[0] = 1;
			sCal.iaFactorSet[1] = 4;

sorting( sCal.iaFactorSet, sCal.iN );
		}
	}

REP:
	// iRemainDiffs is even
	if( iRemainDiffs > 0 )
	{
		iIterB = FMAX - 1;
		for( ; sCal.iaFactorSet[iIterB] == 0; iIterB-- ) { ; }

if( iIterB == 0 ) { return -1; }

for( ; iIterB >= 1; iIterB-- )
		{
			for( iIterA = iIterB - 1; iIterA >= 0; iIterA-- )
			{
				iTemp = (sCal.iaFactorSet[iIterA] - 1) * (sCal.iaFactorSet[iIterB] - 1);

if( (iTemp > 0) && (iTemp <= iRemainDiffs) )
				{
					iRemainDiffs -= iTemp;
					sCal.iaFactorSet[iIterB] *= sCal.iaFactorSet[iIterA];
					sCal.iaFactorSet[iIterA] = 1;
					sorting( sCal.iaFactorSet, sCal.iN );

goto REP;
				}
			}
		}
	}

if( (iRemainDiffs > 0) && (iCallingU == iMaxTrial) ) { return -1; }
	else { return iRemainDiffs; }
}

void separate( CSet &sCal )
{
	static int iCallingS = 0; // number of calling separate()
	int iaPSetS[PMAX] = {0}; // PrimeSet of small number
	int iaPExpS[PMAX] = {0}; // PrimeExp of small number
	int iaPSetL[PMAX] = {0}; // PrimeSet of large number
	int iaPExpL[PMAX] = {0}; // PrimeExp of large number
	int iIterA;
	int iIterB;
	int iTempS;
	int iTempL;
	int iSeparate;

iCallingS++;

for( iIterB = sCal.iN - 1; iIterB >= 1; iIterB-- )
	{
		iSeparate = 0;
		if( iCallingS % 2 )
		{
			for( iIterA = iIterB - 1; iIterA >= 0; iIterA-- )
			{
				if( sCal.iaFactorSet[iIterA] != 1 )
				{
					iTempS = sCal.iaFactorSet[iIterA];
					iTempL = sCal.iaFactorSet[iIterB];
					factorize( iTempS, iaPSetS, iaPExpS );
					factorize( iTempL, iaPSetL, iaPExpL );
					iSeparate = 1;

break;
				}
			}
		}
		else
		{
			for( iIterA = 0; iIterA < iIterB; iIterA++ )
			{
				if( sCal.iaFactorSet[iIterA] != 1 )
				{
					iTempS = sCal.iaFactorSet[iIterA];
					iTempL = sCal.iaFactorSet[iIterB];
					factorize( iTempS, iaPSetS, iaPExpS );
					factorize( iTempL, iaPSetL, iaPExpL );
					iSeparate = 1;

break;
				}
			}
		}

if( (iSeparate == 1) && (iaPSetS[0] < iaPSetL[0]) )
		{
			iTempS = iTempS / iaPSetS[0] * iaPSetL[0];
			iTempL = iTempL / iaPSetL[0] * iaPSetS[0];
			sCal.iaFactorSet[iIterA] = iTempS;
			sCal.iaFactorSet[iIterB] = iTempL;
			sorting( sCal.iaFactorSet, sCal.iN );
		}
	}
}

void analyze( GSet sGiven )
{
	CSet sCal;
	int iTemp;
	SQSet sRes;

if( sGiven.iP == 1 )
	{
		if( sGiven.iN == sGiven.iS ) { ones( sGiven.iN, "\n" ); }
		else { printf( "No solution\n" ); }
	}
	else
	{
		sCal.iP = sGiven.iP;
		factorize( sCal.iP, sCal.iaPrimeSet, sCal.iaPrimeExp );
		sCal.minimal_setting();

if( sGiven.iN < sCal.iN )
		{
			sCal.pressure( sCal.iN - sGiven.iN );
		}
		else
		{
			if( sGiven.iS - (sGiven.iN - sCal.iN) < sCal.iS )
			{
				printf( "No solution\n" );

return;
			}
		}

REP:
		iTemp = unite( sCal, sGiven );

if( iTemp == -1 ) { printf( "No solution\n" ); }
		else if( iTemp > 0 )
		{
			separate( sCal );
			sCal.refresh();

goto REP;
		}
		else
		{
			sRes.assign( sCal );
			sCal.refresh();
			iTemp = extendable( sCal, sGiven );
			ones( iTemp, " " );
			sRes.print();
		}
	}
}