主题：第40次编程比赛第2题题目
neverPE [专家分：1620] 发布于 2006-09-01 02:28:00
取石子游戏的变种：有两堆石子，两个人轮流对这些石子进行操作。在每一次操作中，操作者需要拿走其中一堆石子，并且把另一堆石子分成两堆（可以不相等）留给对方操作。游戏如此进行下去，石子数会越来越少，最后必将出现这样一种情况：某人拿走一堆石子后发现另一堆里只剩1个石子不能再分了。游戏规定此时该操作者取胜。
这个游戏是不公平的。对于任意一种初始状态，总有一方有必胜策略。所谓有必胜策略是指，无论对方如何操作，自己总有办法取胜。现在给出两堆石子的数量，要求计算先操作的人是否存在必胜策略。
函数原型 bool Stone(char* a,char* b);
a，b是两堆数字的数目，用字符串保存。字符串长度不大于30，并且没有非法字符，没有前导0。
返回值：如果先操作的人存在必胜策略，返回true，否则返回false
内存限制：256M
时间限制：10S
样例：
a="1" b="1" true
a="100" b="1" true
a="2" b="1" true
a="2" b="3" false
a="5" b="2" true
提示：不要想太复杂了。
回复列表 （共17个回复）
沙发
jackin0627 [专家分：1270] 发布于 2006-08-31 21:53:00
先頂了
板凳
boxertony [专家分：23030] 发布于 2006-09-01 01:27:00
#include <string.h>
bool Stone(char* a,char* b)
{
char m = a[strlen(a)-1];
char n = b[strlen(b)-1];
if(m=='0' || m=='1' || m=='4' || m=='5' || m=='6' || m=='9'
|| n=='0' || n=='1' || n=='4' || n=='5' || n=='6' || n=='9')
return true;
else
return false;
}
3 楼
joekings [专家分：550] 发布于 2006-09-01 10:08:00
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
bool Stone(char* a,char* b);
void main()
{
bool bRet;
bRet=Stone("32424354645765787687987","12132435465787686");
printf("%s\n",bRet?"true":"false");
}
//函数实现
bool Stone(char *a,char *b)
{
char *p;
int iA,iB,len;
len=strlen(a);
p=a+len-1;
iA=atol(p);
len=strlen(b);
p=b+len-1;
iB=atol(p);
//printf("%d**%d\n",iA,iB);
if(iA%5==2||iA%5==3)
{if(iB%5==2||iB%5==3)
return false;
}
return true;
}
//{在分析了1~25之间的各种情况之后，我认为只有两个数同时满足被5除余2或3，先手的人才会输。}
//{实现是基于上面的结论的，如果上面的结论不对，结果也就不对了。0}
//{不过，我觉得我分析出的结论正确的可能性很大。哈哈！:)}
4 楼
joekings [专家分：550] 发布于 2006-09-01 11:21:00
//发错地方了，已经移动到第1题了。
5 楼
ITER [专家分：680] 发布于 2006-09-01 16:17:00
bool Stone(char* a,char* b)
{
int lena = strlen(a);
int lenb = strlen(b);
if(1==lena||1==lenb)
{
if('1'==*a||'1'==*b)
return true;
}
int la = *(a+lena-1)-'0'-2;
int lb = *(b+lenb-1)-'0'-2;
if(la<0)
la+=10;
if(lb<0)
lb+=10;
la%=5;
lb%=5;
if(la<=1&&lb<=1)
return false;
else return true;
}
6 楼
liyanguestc [专家分：90] 发布于 2006-09-01 16:45:00
/*不知道理解分析的对不
设n为选手取完一堆另一堆的个数，
先分析1-10,
n=1, 必胜
n=2,必输
n=3,必输
n=4,分为2,2 必胜
n=5,分为2，3 必胜
n=6，分为3，3必胜
n=7，必输
n=8，必输
n=9， 必胜
n=10， 必胜
可以分为两个必输的n1,n2的n为必胜n.否则为必输
可以分析的所有除5余2或3的n均为必输n(由数论知识很容易推出)
所以如果两堆如果均为必输n则，无必胜方法，否则有必胜方法！！
*/#include <iostream>
#include <string.h>
using namespace std;
bool Stone(char* a,char* b);
int main()
{
char ch1[30],ch2[30];
bool flag=0;
scanf("%s",ch1);
scanf("%s",ch2);
flag=Stone(ch1,ch2);
cout<<boolalpha<<flag<<endl;
return 0;
}
bool Stone(char* a,char* b)
{ char taila,tailb,tmp;
tmp=*a;
int i=0;
while(tmp!='\0')
{i++;
tmp=*(a+i);
taila=*(a+i-1);
}
i=0;
tmp=*b;
while(tmp!='\0')
{i++;
tmp=*(b+i);
tailb=*(b+i-1);
}
if((taila=='2'||taila=='3'||taila=='7'||taila=='8')
&&((tailb=='2'||tailb=='3'||tailb=='7'||tailb=='8')))
return 0;
return 1;
}
7 楼
BigCarrot [专家分：10] 发布于 2006-09-01 22:05:00
//It can be proved that if a given number = 5n + 2 or 5n + 3, the result is false
//if the given number = 5n or 5n+1 or 5n+4, then the result is true
bool result[10] = {true, true, false, false, true, true, true, false, false, true};
bool Stone(char* a,char* b)
{
while (*a) a++;
a--;
int numa = *a - '0';
while (*b) b++;
b--;
int numb = *b - '0';
return (result[numa] || result[numb]);
}
8 楼
孤独的猫 [专家分：3370] 发布于 2006-09-01 22:40:00
[color=0000FF]bool[/color] [color=8C0000]Stone[/color]([color=0000FF]char[/color] *a,[color=0000FF]char[/color] *b)
{
[color=0000FF]char[/color] [color=848284]EndOfa[/color]=*([color=848284]a[/color]+[color=8C0000]strlen[/color]([color=848284]a[/color])-1);
[color=0000FF]char[/color] [color=848284]EndOfb[/color]=*([color=848284]b[/color]+[color=8C0000]strlen[/color]([color=848284]b[/color])-1);
[color=0000FF]if[/color]([color=848284]EndOfa[/color]=='0'||[color=848284]EndOfa[/color]=='1'||[color=848284]EndOfa[/color]=='4'||[color=848284]EndOfa[/color]=='5'||[color=848284]EndOfa[/color]=='6'||[color=848284]EndOfa[/color]=='9'||
[color=848284]EndOfb[/color]=='0'||[color=848284]EndOfb[/color]=='1'||[color=848284]EndOfb[/color]=='4'||[color=848284]EndOfb[/color]=='5'||[color=848284]EndOfb[/color]=='6'||[color=848284]EndOfb[/color]=='9')
[color=0000FF]return true[/color];
[color=0000FF]return false[/color];
}
9 楼
wlsss [专家分：150] 发布于 2006-09-02 01:44:00
/*****************************************************
奇异局势(即遇这种状态必输)以及每种奇异局势两数之和
(2,2) 4 (2,12) 14 (2,17) 19 ......
(2,3) 5 (3,12) 15 (3,17) 20 ......
(3,3) 6 (7,12) 19 (7,17) 24 ......
(2,7) 9 (8,12) 20 (8,17) 25 ......
(3,7) 10 (12,12) 24 (12,17) 29 ......
(7,7) 14 (2,13) 15 (13,17) 30 ......
(2,8) 10 (3,13) 16 (17,17) 34 ......
(3,8) 11 (7,13) 20 (2,18) 20 ......
(7,8) 15 (8,13) 21 (3,18) 21 ......
(8,8) 16 (12,13) 25 (7,18) 25 ......
(3,12) 15 (13,13) 26 (8,18) 26 ......
(7,12) 19 (12,18) 30 ......
(8,12) 20 (13,18) 31 ......
(17,18) 35 ......
(18,18) 36 ......
可以看出在奇异局势中的只有一些数，即以下的数：
2,3,7,8,12,13,17,18,22,23,27,28,32,33,37,38,......
可以把他们叫成“奇异数”吧，其他的就叫“非奇异数”吧.
可以看出任何一个奇异数都不能写成两个奇异数的和，
而任意一个非奇异数都可以写成两个奇异数之和。
因此：
奇异局势由两个奇异数构成，假设对方遇到奇异局势，
则对方只可能分成两个非奇异数 或 一个奇异数和一个非奇异数，
无论怎么分，只需留下一个非奇异数，把它分成两个奇异数，
则对方又陷入奇异局势。
******************************************************/
/*************************************
从以上知：
末尾数字是2,3,7,8的都是奇异数，其他的都是非奇异数。
则：当两个数末尾都是2,3,7,8时必输，否则赢。
*************************************/
#include <iostream.h>
#include <string.h>
bool Stone(char* a,char* b)
{
char enda=a[strlen(a)-1];
char endb=b[strlen(b)-1];
if((enda=='2'||enda=='3'||enda=='7'||enda=='8') &&
(endb=='2'||endb=='3'||endb=='7'||endb=='8'))
return false;
return true;
}
void main()
{
char a[]="14586154234823951951235182423";
char b[]="876131513512352351235233138";
cout<<Stone(a,b)<<endl;
}
10 楼
hainanlion [专家分：0] 发布于 2006-09-02 02:13:00
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
bool Stone(char *a,char *b)
{
int length_a,length_b;
length_a=strlen(a);
length_b=strlen(b);
if((a[length_a-1]=='1'&&length_a==1)||(b[length_b-1]=='1'&&length_b==1))
return true;
else if(a[length_a-1]=='4'||a[length_a-1]=='5'||a[length_a-1]=='6'||a[length_a-1]=='9'||a[length_a-1]=='0')
return true;
else if(b[length_b-1]=='4'||b[length_b-1]=='5'||b[length_b-1]=='6'||b[length_b-1]=='9'||b[length_b-1]=='0')
return true;
return false;
}
int main(){
char a[30];
char b[30];
printf("a=");
scanf("%s",a);
getchar();
printf("b=");
scanf("%s",b);
getchar();
Stone(a,b);
if(Stone(a,b) == true) printf("true");
else if(Stone(a,b) == false) printf("false");
}
我来回复
您所在位置：