2015年广州市队选拔题目-广州市青少年科技中心.doc

2015年广东省青少年信息学竞赛广州市选拔赛 第 PAGE 四页，共四页 2015年广东省青少年信息学竞赛广州市选拔赛 2015年3月28日，答题时间13:30-17:30 注意事项： 严格按照题目所要求的格式进行输入、输出，否则严重影响得分。 题目测试数据有严格的时间限制，超时不得分。 输入文件格式不用判错；输入输出文件名均已给定，不用键盘输入。 源程序保存在以“序号+姓名”命名的文件夹下，按题目要求命名。评测以源程序为准。 四个小时完成。 内存限制：256MB，代码长度限制32KB。 本次竞赛的最终解释权归GDOI评委会所有。 试题名称石子游戏找回密码约瑟夫问题字符消除提交文件名stone.pas/c/cpppwd.pas/c/cppjosephus.pas/c/cppstring.pas/c/cpp输入文件名stone.inpwd.injosephus.instring.in输出文件名stone.outpwd.outjosephus.outstring.out满分100100100100 第一题 石子游戏 提交文件：stone.pas/c/cpp 输入文件：stone.in 输出文件：stone.out 问题描述 Alice 和 Bob 总喜欢聚在一起玩游戏（T_T），今天他（她）们玩的是一款新型的取石子游戏。游戏一开始有N堆石子，Alice 和 Bob 轮流取出石子。在每次操作中，游戏者必须选择其中的一堆石子，并作出下列的其中一种操作： 移去整堆石子 假设石子堆中有X颗石子，取出Y颗石子，其中1=YX,并且X和Y的最大公约数是1。 游戏结束的条件是：取出最后一颗石子的人胜出。众所周知，Alice和Bob都是绝顶聪明的，假设他们在游戏中都采取最优的策略，问最后谁会胜出游戏呢？ 输入格式 第一行包含一个整数T，表示测试数据的组数。 接下来T组测试数据，在每组数据中，第一行包含一个整数N，表示有多少堆石子。第二行N个正整数，分别表示每堆有多少颗石子。 输出格式 每组测试数据输出一行，表示获胜者的名字（Alice 或者 Bob）。 输入样例：输出样例：3 3 3 5 6 4 2 3 6 9 5 3 2 1 1000000 999999Alice Bob Alice 数据范围 20%的数据，N=5，每堆石子数量少于10 100%的数据，T=100，N=100，每堆石子数量不大于1,000,000 第二题 找回密码 提交文件：pwd.pas/c/cpp 输入文件：pwd.in 输出文件：pwd.out 问题描述 Kevin是一个热爱字符串的小孩。有一天，他把自己的微信登录密码给忘记了，万般无奈之下只好点“找回密码”。 这时候，网页上出现了当初设定的密保问题：在字符串st中，有若干个内容不同的子串，请问其中字典序第k小的子串是什么？ 很可惜的是，Kevin现在已经不会写程序了，所以，他找到了睿智的你来帮忙。 输入格式 输入数据包括两行：第一行为字符串st，第二行为正整数k，定义如题目描述。 其中字符串st的长度不超过100,000且只由大小写英文字母组成 输出格式 一行，为第k小的字符串，如果字符串st中不足k个不同的子串，则输出字典序最大的一个。 输入样例：输出样例：AAB 2AA 数据范围 50%的数据，|st| =1000 100%的数据，|st|=100,000，K 2^63 第三题 约瑟夫问题 提交文件：josephus.pas/c/cpp 输入文件：josephus.in 输出文件：josephus.out 问题描述 现有N*(N+1)/2 个人围成一圈，编号从1到N*(N+1)/2，其中编号i与编号i+1的人相邻，编号N*(N+1)/2与编号1相邻。如今，我们要执行N-1个阶段的杀人仪式，在第一个阶段开始前，从编号为1的人开始报数。在第i阶段中，报到n+1-i这个数的人要被杀害，之后从被杀害者的下一个相邻的人开始从1开始报数，在第i个阶段里需要杀死i个人，随后即可进入下一个阶段，更具体地说： 在第1个阶段中，报数为N的人会被杀害，在这个阶段中需要杀死N个人； 在第2个阶段中，报数为N-1的人会被杀害，在这个阶段中需要杀死N-1个人； . . . 在第n-1个阶段中，报数为2的人会被杀害，在这个阶段中需要杀死2个人。 仪式结束后，会剩下一个幸存者，请问这位幸存者的编号是多少？ 输入格式 第一行一个整数T，表示数据的组数。 接下来T行，每行一个整数N，N定义如题目所述。 输出格式 输出一个整数，表示幸存者的编号 输入样例：输出样例：3 1 2 31 3 2 数据范围 20%数据，1=n=100，T =10