PKU 2844. Sum and Product. TLE -

PKU 2844. Sum and Product. TLE -_-

알 수 없는 사용자 2010. 6. 22. 13:03

#include <stdio.h>

__int64 multipoint[100000];
__int64 factors[100000];

int main()
{
	__int64 n, s, p, factnum, i, j, sum, prod, count;

while(~scanf("%d%d%d", &n, &s, &p))
	{
		/* initialize & input */
		factnum = 0;
		for (i = 1; i < s; i++)
		{
			if (p % i == 0)
			{
				factors[factnum] = i;
				factnum++;
			}
		}

for (i = 0; i < n; i++)
		{
			multipoint[i] = factnum - 1;
		}

/* calculating */
		while (multipoint[n - 1] != 0)
		{
			for (i = 0; i < n - 1; i++)
			{
				if (multipoint[i] > multipoint[i + 1])
				{
					multipoint[i] = multipoint[i + 1];
				}
			}

sum = 0;
			prod = 1;
			count = 0;
			for (i = 0; i < n; i++)
			{
				sum += factors[multipoint[i]];
				prod *= factors[multipoint[i]];
				count++;
				if (sum > s || prod > p)
				{
					break;
				}
			}

if (sum == s && prod == p)
			{
				break;
			}

multipoint[0]--;
			for (i = 0; i < n - 1; i++)
			{
				if (multipoint[i] < 0)
				{
					multipoint[i + 1]--;
					for (j = i; j >= 0; j--)
					{
						multipoint[j] = multipoint[j + 1];
					}
				}
			}
		}

/* for test */
		/*for (i = 0; i < n; i++)
		{
			printf("%d\n", factors[multipoint[i]]);
		}*/

if (s == sum && p == prod && n == count)
		{
			for (i = 0; i < n; i++)
			{
				printf("%d ", factors[multipoint[i]]);
			}
			printf("\n");
		}
		else
		{
			printf("No solution\n");
		}
		
		/* for clear */
		for (i = 0; i < n; i++)
		{
			multipoint[i] = 0;
		}
		for (i = 0; i < factnum; i++)
		{
			factors[i] = 0;
		}
	}

return 0;
}<SPAN id=tx_marker_caret></SPAN>

아오 씨바 빡쳐 -_-;; 이거도 TL이냐?;;;