4107701_ac_0ms_204k.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 93 行

#include <stdio.h>
#include <string.h>

int num[10], mark[10];

int a(int m, int n)
{
	int ret (1);

	for (int i = m - n + 1; i <= m; i++)
	{
		ret *= i;
	}
	return ret;
}

int get(int t)
{
	int i, c = 0;

	for (i = 0; i < 10; i++)
	{
		mark[i] == 0 && c++;
		if (c == t)
			break;
	}
	return i;
}

int main()
{
	int i, sum;
	int t = 1, p = 9;
	sum = 0;
	for (i = 1; sum <= 1000000; i++, p--)
	{
		num[i] = 9 * t;
		t *= p;
		sum += num[i];
	}
	while (scanf("%d", &t) == 1 && t)
	{
		if (t < 10)
		{
			printf("%d\n", t);
			continue;
		}
		i = 1;
		while (t > num[i])
			t -= num[i++];
		p = 9;
		sum = a(p, --i);
		memset(mark, 0, sizeof(mark));
		if (t % sum == 0)
		{
			printf("%d", t / sum);
			mark[t / sum] = 1;
			t = sum;
		}
		else
		{
			printf("%d", t / sum + 1);
			mark[t / sum + 1] = 1;
			t %= sum;
		}
		while (i)
		{
			if (i == 1)
			{
				printf("%d\n", get(t));
				break;
			}
			sum = a(--p, --i);
			int tmp;
			if (t % sum == 0)
			{
				tmp = get(t / sum);
				printf("%d", tmp);
				mark[tmp] = 1;
				t = sum;
			}
			else
			{
				tmp = get(t / sum + 1);
				printf("%d", tmp);
				mark[tmp] = 1;
				t %= sum;
			}
		}
	}
	return 0;
}