编程

中原

语言要求：随便，但希望用C。。
要求：我百度不到一摸一样的答案
------------------
Description

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。
Input

输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。
Output

输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。
Sample Input

2 1
8 4
4 7
Sample Output

0
1
0
------------------------------------

题目来源：http://acm.pku.edu.cn/JudgeOnline/problem?id=1067 我很仁慈的没选英文题名

耿直007

有一个简便的公式：设题目中给定的两个数为An、Bn(Bn>An)，自设一个中间量n。n=Bn-An。
若An等于[sqrt（5）+1]*n/2的整数部分，则必输。

chenth3

这不是经典的博弈论题吗

耿直007

且让俺牛刀小试一下！



#include<stdio.h>
void main()
{int n,t,i,m,s=(sqrt(5)+1)/2;
printf("您想输入几组数:");
scanf("%d",&i);
int a,b,x;
for(m=0;m<i;m++)
     {scanf("%d%d",&a[m],&b[m]);
       if(a[m]>b[m])
         {t=a[m];a[m]=b[m];b[m]=t;}
       n=b[m]-a[m];
       if((int)(s*n)==a[m])
         x[m]=0;
       else
         x[m]=1;
      }
printf("结果是:")
for(m=0;m<i;m++)
     {printf("%d %d        %d\n",a[m],b[m],x[m]);
     }
}



没有验证，也不知道对不对

[ 本帖最后由 耿直007 于 2008-9-7 19:06 编辑 ]

中原

楼上的答案终于被我调对了，或许公式是对的。。。。sqrt需要函数库math.h（居然不提是错，而是给一个错答案，wintc果然垃圾），如果修改到不用输入i（估计这个你能搞定吧）奖励思想币1，不套用公式重新编程奖励思想币2

耿直007

不用公式，说实话，这一题我就不会做了（难道让计算机自己判断哪种取法是最优的吗？）


可以不用 i ，但即使不用 i 那也得有一个判断结束的标志啊！除非不用循环。（“若干”本身就是一个模糊性很强的词嘛！不具有可操作性）

[ 本帖最后由 耿直007 于 2008-9-8 13:23 编辑 ]

liota

那公式很知道了,有了那个公式只存在用C实现的问题,比较简单.
前年奥赛普及组的问题求解的延伸.老师给的公式,差不多就这样了但是一直都不会证明,现在也不会证明.
但可以很容易找到递推原理,生成数对表.
证明拿去给同学大家讨论了下,水平都不够,不过在此过程中找出了很多规律.

首先设其为F(M.N),不妨设M<N,现在主要是找出F(M,N)=0的情况.
过程中,满足基本条件,f(n,n)=1,f(0.n)=1.
由上述条件得如果F(m0,n0)=0,那么F(t+m0,t+n0)=1
如果F(m0,n0)=0,那么F(m0,N)=1,N>n0,对m0亦成立,通过上述条件,便可以得出数对表了.
下面是程序,因为我们这边竞赛用的是Devcpp,所以环境就用那个了.
再此之前,先有一个编程思路.
首先,以i为指示变量,因为当i=m0-n0确定时,只有一个F(m0,n0)=0成立.
再者,这个数对表里面一个数字只能出现一次.

#include<stdio.h>
#define max 5000/*数据规模,5000*/
int main()
{
    FILE *out=fopen("rocks.out","w");
    int a[max][2]={0},c[max]={0};/*a[][0]表示M,a[][1]表示N,c[]纪录数字是否重复出现*/
    int i,j,t;
    a[1][0]=1;
    a[1][1]=2;
    c[1]=1;
    c[2]=1;
    t=3;/*确定初始条件*/
    fprintf(out,"(1,2) ");
    for(i=2;i<=max;i++)
    {
        while(c[t]==1) t++;
        a[0]=t;
        a[1]=t+i;
        c[t]=1;c[t+i]=1;
        fprintf(out,"(%d,%d) ",a[0],a[1]);
        if(i%5==0)fprintf(out,"\n");
    }
    fclose(out);
    return 0;
}

Devcpp 4.9.9.0运行通过.

liota

由于数据过多，就给出前500个满足先手败的数对.

(1,2) (3,5) (4,7) (6,10) (8,13)
(9,15) (11,18) (12,20) (14,23) (16,26)
(17,28) (19,31) (21,34) (22,36) (24,39)
(25,41) (27,44) (29,47) (30,49) (32,52)
(33,54) (35,57) (37,60) (38,62) (40,65)
(42,68) (43,70) (45,73) (46,75) (48,78)
(50,81) (51,83) (53,86) (55,89) (56,91)
(58,94) (59,96) (61,99) (63,102) (64,104)
(66,107) (67,109) (69,112) (71,115) (72,117)
(74,120) (76,123) (77,125) (79,128) (80,130)
(82,133) (84,136) (85,138) (87,141) (88,143)
(90,146) (92,149) (93,151) (95,154) (97,157)
(98,159) (100,162) (101,164) (103,167) (105,170)
(106,172) (108,175) (110,178) (111,180) (113,183)
(114,185) (116,188) (118,191) (119,193) (121,196)
(122,198) (124,201) (126,204) (127,206) (129,209)
(131,212) (132,214) (134,217) (135,219) (137,222)
(139,225) (140,227) (142,230) (144,233) (145,235)
(147,238) (148,240) (150,243) (152,246) (153,248)
(155,251) (156,253) (158,256) (160,259) (161,261)
(163,264) (165,267) (166,269) (168,272) (169,274)
(171,277) (173,280) (174,282) (176,285) (177,287)
(179,290) (181,293) (182,295) (184,298) (186,301)
(187,303) (189,306) (190,308) (192,311) (194,314)
(195,316) (197,319) (199,322) (200,324) (202,327)
(203,329) (205,332) (207,335) (208,337) (210,340)
(211,342) (213,345) (215,348) (216,350) (218,353)
(220,356) (221,358) (223,361) (224,363) (226,366)
(228,369) (229,371) (231,374) (232,376) (234,379)
(236,382) (237,384) (239,387) (241,390) (242,392)
(244,395) (245,397) (247,400) (249,403) (250,405)
(252,408) (254,411) (255,413) (257,416) (258,418)
(260,421) (262,424) (263,426) (265,429) (266,431)
(268,434) (270,437) (271,439) (273,442) (275,445)
(276,447) (278,450) (279,452) (281,455) (283,458)
(284,460) (286,463) (288,466) (289,468) (291,471)
(292,473) (294,476) (296,479) (297,481) (299,484)
(300,486) (302,489) (304,492) (305,494) (307,497)
(309,500) (310,502) (312,505) (313,507) (315,510)
(317,513) (318,515) (320,518) (321,520) (323,523)
(325,526) (326,528) (328,531) (330,534) (331,536)
(333,539) (334,541) (336,544) (338,547) (339,549)
(341,552) (343,555) (344,557) (346,560) (347,562)
(349,565) (351,568) (352,570) (354,573) (355,575)
(357,578) (359,581) (360,583) (362,586) (364,589)
(365,591) (367,594) (368,596) (370,599) (372,602)
(373,604) (375,607) (377,610) (378,612) (380,615)
(381,617) (383,620) (385,623) (386,625) (388,628)
(389,630) (391,633) (393,636) (394,638) (396,641)
(398,644) (399,646) (401,649) (402,651) (404,654)
(406,657) (407,659) (409,662) (410,664) (412,667)
(414,670) (415,672) (417,675) (419,678) (420,680)
(422,683) (423,685) (425,688) (427,691) (428,693)
(430,696) (432,699) (433,701) (435,704) (436,706)
(438,709) (440,712) (441,714) (443,717) (444,719)
(446,722) (448,725) (449,727) (451,730) (453,733)
(454,735) (456,738) (457,740) (459,743) (461,746)
(462,748) (464,751) (465,753) (467,756) (469,759)
(470,761) (472,764) (474,767) (475,769) (477,772)
(478,774) (480,777) (482,780) (483,782) (485,785)
(487,788) (488,790) (490,793) (491,795) (493,798)
(495,801) (496,803) (498,806) (499,808) (501,811)
(503,814) (504,816) (506,819) (508,822) (509,824)
(511,827) (512,829) (514,832) (516,835) (517,837)
(519,840) (521,843) (522,845) (524,848) (525,850)
(527,853) (529,856) (530,858) (532,861) (533,863)
(535,866) (537,869) (538,871) (540,874) (542,877)
(543,879) (545,882) (546,884) (548,887) (550,890)
(551,892) (553,895) (554,897) (556,900) (558,903)
(559,905) (561,908) (563,911) (564,913) (566,916)
(567,918) (569,921) (571,924) (572,926) (574,929)
(576,932) (577,934) (579,937) (580,939) (582,942)
(584,945) (585,947) (587,950) (588,952) (590,955)
(592,958) (593,960) (595,963) (597,966) (598,968)
(600,971) (601,973) (603,976) (605,979) (606,981)
(608,984) (609,986) (611,989) (613,992) (614,994)
(616,997) (618,1000) (619,1002) (621,1005) (622,1007)
(624,1010) (626,1013) (627,1015) (629,1018) (631,1021)
(632,1023) (634,1026) (635,1028) (637,1031) (639,1034)
(640,1036) (642,1039) (643,1041) (645,1044) (647,1047)
(648,1049) (650,1052) (652,1055) (653,1057) (655,1060)
(656,1062) (658,1065) (660,1068) (661,1070) (663,1073)
(665,1076) (666,1078) (668,1081) (669,1083) (671,1086)
(673,1089) (674,1091) (676,1094) (677,1096) (679,1099)
(681,1102) (682,1104) (684,1107) (686,1110) (687,1112)
(689,1115) (690,1117) (692,1120) (694,1123) (695,1125)
(697,1128) (698,1130) (700,1133) (702,1136) (703,1138)
(705,1141) (707,1144) (708,1146) (710,1149) (711,1151)
(713,1154) (715,1157) (716,1159) (718,1162) (720,1165)
(721,1167) (723,1170) (724,1172) (726,1175) (728,1178)
(729,1180) (731,1183) (732,1185) (734,1188) (736,1191)
(737,1193) (739,1196) (741,1199) (742,1201) (744,1204)
(745,1206) (747,1209) (749,1212) (750,1214) (752,1217)
(754,1220) (755,1222) (757,1225) (758,1227) (760,1230)
(762,1233) (763,1235) (765,1238) (766,1240) (768,1243)
(770,1246) (771,1248) (773,1251) (775,1254) (776,1256)
(778,1259) (779,1261) (781,1264) (783,1267) (784,1269)
(786,1272) (787,1274) (789,1277) (791,1280) (792,1282)
(794,1285) (796,1288) (797,1290) (799,1293) (800,1295)
(802,1298) (804,1301) (805,1303) (807,1306) (809,1309)

liota

嗯,这个数对表的时间复杂度T(n)=O(1),虽然是1000W,但是是属于常数级别的.
所以只要生成了数对表,再加一行
while(scanf("%ld%ld",&m,&n)!=EOF)之类的控制命令就可以了,应该不会超过0.1秒的.

liota

公式应该是正确的,用公式当然是最快的啦.

中原

我也觉得用公式才方便，似乎想不出什么好算法了。。。

咱的思想币还没发出去呢，谁第一个交出可以在pku上提交成功的程序就给喽~~

liota

嘿嘿,今天有点空,那就把公式法完善吧.

1. #include <stdio.h>
   
2. #include <math.h>
   
3. #define M (sqrt(5)+1)/2
   
4. int main()
   
5. {
   
6. int m,n,t;
   
7. while( scanf("%d%d",&m,&n) != EOF)
   
8. {
   
9. int temp;
   
10. if(n<m){temp=m;m=n;n=temp;}
    
11. t=n-m;   
    
12. if((int)(t*M)==m)printf("0\n");
    
13. else printf("1\n");
    
14. }
    
15. return 0;
    
16. }

复制代码

正空体

条件编译：void mainCRTStartup(void)
{
int mainret;

/* Get the full Win32 version */
_osver = GetVersion();
_winminor = (_osver >> 8) & 0x00FF ;
_winmajor = _osver & 0x00FF ;
_winver = (_winmajor << 8) + _winminor;
_osver = (_osver >> 16) & 0x00FFFF ;

#ifdef _MT
if ( !_heap_init(1) ) /* initialize heap */
#else /* _MT */
if ( !_heap_init(0) ) /* initialize heap */
#endif /* _MT */
fast_error_exit(_RT_HEAPINIT); /* write message and die */

#ifdef _MT
if( !_mtinit() ) /* initialize multi-thread */
fast_error_exit(_RT_THREAD); /* write message and die */
#endif /* _MT */

__try {
_ioinit(); /* initialize lowio */
_acmdln = (char *)GetCommandLineA(); /* get cmd line info */
_aenvptr = (char *)__crtGetEnvironmentStringsA(); /* get environ info */
_setargv();
_setenvp();
__initenv = _environ;
mainret = main(__argc, __argv, _environ);
exit(mainret);
}
__except ( _XcptFilter(GetExceptionCode(), GetExceptionInformation()) )
{

正空体

subsystem和可执行文件的启动
LINK的时候需要指定/subsystem，这个链接选项告诉Windows如何运行可执行文件。
控制台程序是/subsystem:"console"
其它程序一般都是/subsystem:"windows "

将 subsystem 选成"console"后，Windows在进入可执行文件的代码前（如mainCRTStartup），就会产生一个控制台窗口。
如果选择"windows"，操作系统就不产生console窗口,该类型应用程序的窗口由用户自己创建。

可执行文件都有一个Entry Point，LINK时可以用/entry指定。缺省情况下，如果subsystem是“console”，Entry Point是 mainCRTStartup(ANSI)或wmainCRTStartuup(UNICODE)，即：
/subsystem:"console" /entry:"mainCRTStartup" (ANSI)
/subsystem:"console" /entry:"wmainCRTStartuup" (UNICODE)
mainCRTStartup 或 wmainCRTStartuup 会调用main或wmain。
值得一提的是，在进入应用程序的Entry Point前，Windows的装载器已经做过C变量的初始化，有初值的全局变量拥有了它们的初值，没有初值的变量被设为0。

如果subsystem是“windows”，Entry Point是WinMain(ANSI)或wWinMain(UINCODE)，即：
/subsystem:"windows" /entry:"WinMainCRTStartup" (ANSI)
/sbusystem:"windows" /entry:"wWinMainCRTStartup" (UINCODE)
WinMainCRTStartup 或 wWinMainCRTStartup 会调用 WinMain 或 wWinMain。

这些入口点函数，在CRT目录都可以看到源代码，例如（为了简洁，我删除了原代码的一些条件编译）：

正空体

例如（为了简洁，我删除了原代码的一些条件编译）： 便是上文中的内容；不知有C/C++高手没；人也只是菜鸟

中原

我想问一下这个代码是关于这个题目的？

从结尾来看，至少有一个语法错误

这个函数也用的太多了吧~~

benmandy

不是很理解题目，说两个人都使用了最好的策略！是都使用同意策略呢还是相对各自最好的策略？？


我看你们提到了效率。。两堆石头得数目是用户输入的吧，然后怎么“liota”列出了先手败的对数？？？

是用户输入若干行的石头对数然后由程序计算嘛？？还是计算初所有先手败的可能排列的石头对？？？

benmandy

不用公式是很麻烦。。不过可以用递归。。这道题用递归的话要看当时脑袋的清醒程度了

liota

生成数对表就是递推,递归还要回溯,时间复杂度太大了.

benmandy

时间复杂度不高啊！只是可读性差些~不要紧。。。

liota

嗯,一般般啦.时间复杂度我前面也解释了下.

达芬奇的晚餐

这些题目简直是欺负咱文科生，编程能不能算还没有认真看，倒是N多条代码弄到人们昏头转向。
话说中原也无怎么给出公式啊？

liota

那公式还找不到证明啊,是从网上搜到的 ..

王其洲