Home > Old Blog Posts > URAL 1023

URAL 1023


Background

  Yekaterinburg获得了2032年夏季奥运会的举办权。由于允许举办国对竞赛项目进行一些小的修改。现
打算修改“Button”这个新项目的规则。规则很简单,在2个对手前有一堆扣子(k个),2人轮流取走扣
子,同一时间,某人能取走1至L个扣子。取走最后一个扣子的为胜者。作为奥运会项目,规则应该比通常
玩的要难一点。先走者可以设定数K(就是总共有k个扣子),3<=K<=100 000 000.后走者可以设定数
L,2 <= L < K

[编辑] Problem

  现在要紧的问题是,请你写一个程序,帮助后走者做出抉择。换言之,当给出K后,你的程序
能给出数L,使到后走者能获胜。例如, 如果只有3个扣子,后走者把L定为2,有必胜把握。事实
上,如果先走者取了1个扣子,那么后走者可以取剩下的2个扣子,后走者胜。如果先走者取了2个
扣子,那么后走者取1个,也是后走者胜。

Input

输入只包含一个整数K,扣子的总数。

Output

输出L。每次最多能取走的扣子总数,要求保证后走者必胜。假如有多个答案,输出最小的。如果 不存在保证能必胜的L,则输出0。

Sample Input

3

Sample Output

2

可以证明,一定存在这样的L,使后走者胜
事实上,若设L=K-1,则当先走者取完后,剩下的扣子数<=K-1,这样后走者一定能取完,从而得胜
另外,我们可以得到L的一个充分条件:(L+1)|K且L>=2。证明:若先走者取x个棋子,则后走者取L+1-x个棋子,这样循环进行下去,后走者一定取胜。
事实上,这也是一个必要条件,若(L+1)不能整除K,设m = K mod (L+1),第一步先走者取m个棋子,以后后走者若取x个棋子,则先走者取L+1-x个棋子,先走者一定取胜。
综上所述,这道题就转化为:求出K的大于2的最小因数,减1输出。另外对于偶数需要特判。

#include<stdio.h>
#include<math.h>
int main()
{
	int k;
	scanf("%d",&k);
	for(int i=3;i<=sqrt((double)k)*2;++i)
		if(!(k%i))
		{
			printf("%d\n",i-1);
			return 0;
		}
	if(k&1) printf("%d\n",k-1);
	else printf("%d\n",(k>>1)-1);
	return 0;
}
Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: