3371849_ac_63ms_288k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>

int ans[151];

int check(int n, int k, int m)
{
	int i, t, now, num;
	int prev[151], next[151];

	for(i = 1; i <= n; i++)
	{
		next[i] = i+1;
		prev[i] = i-1;
	}
	prev[1] = n;
	next[n] = 1;
	next[prev[m]] = next[m];
	prev[next[m]] = prev[m];
	num = n-1;
	now = next[m];
	for(i = 1; i < n-1; i++, num--)
	{
		t = k;
		if(t > num)
			t %= num;
		if(t==0)
			t = num;
		t--;
		while(t > 0)
		{
			now = next[now];
			t--;
		}
		next[prev[now]] = next[now];
		prev[next[now]] = prev[now];
		now = next[now];
	}
	for(i = 1; i <= n; i++)
	{
		if(next[i]==i)
		{
			return i;
		}
	}
}

void init()
{
	for (int i = 3; i < 151; i++)
	{
		for (int j = 2; ; j++)
		{
			if (check(i, j, 1) == 2)
			{
				ans[i] = j;
				break;
			}
		}
	}
}

void solve()
{
	int n;

	while (scanf("%d", &n) && n)
	{
		printf("%d\n", ans[n]);
	}
}

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