菜单

ACM暑期培训题解 几道有趣的找规律题目

八月 2, 2018 - 算法
ACM暑期培训题解 几道有趣的找规律题目

前言

今天还做了几道找规律的题目,可能是因为我菜所以才没发现正确解法吧,不过通过递推关系得到规律也是很重要的解题方法。


HDU-1847

题目描述

大学英语四级考试就要来临了,你是不是在紧张的复习?也许紧张得连短学期的ACM都没工夫练习了,反正我知道的Kiki和Cici都是如此。当然,作为在考场浸润了十几载的当代大学生,Kiki和Cici更懂得考前的放松,所谓“张弛有道”就是这个意思。这不,Kiki和Cici在每天晚上休息之前都要玩一会儿扑克牌以放松神经。
“升级”?“双扣”?“红五”?还是“斗地主”?
当然都不是!那多俗啊~
作为计算机学院的学生,Kiki和Cici打牌的时候可没忘记专业,她们打牌的规则是这样的 :
1、 总共n张牌;
2、 双方轮流抓牌;
3、 每人每次抓牌的个数只能是2的幂次(即:1,2,4,8,16…)
4、 抓完牌,胜负结果也出来了:最后抓完牌的人为胜者;
假设Kiki和Cici都是足够聪明(其实不用假设,哪有不聪明的学生~),并且每次都是Kiki先抓牌,请问谁能赢呢?
当然,打牌无论谁赢都问题不大,重要的是马上到来的CET-4能有好的状态.
Good luck in CET-4 everybody!

Input

输入数据包含多个测试用例,每个测试用例占一行,包含一个整数n(1<=n<=1000)。

Output

如果Kiki能赢的话,请输出“Kiki”,否则请输出“Cici”,每个实例的输出占一行。

Sample Input

1
3

Sample Output

Kiki
Cici

题目分析

首先我们知道,如果在n=k的时候Cici必胜,那么我们又提议可以推出,k+1和k+2的情况下Kiki必胜,又因为最小的k的值为3,所以我们假设形如3k+1和3k+2的情况Kiki必胜,形如3k的情况Cici必胜,又因为2的幂次除了1之外全是偶数,所以我们可以证明所有形如3k的数加上这个2的幂次不会再是3的倍数,于是我们就可以递推下去得到这个结论是正确的。
有了这个结论,代码会变得很简单。

代码实现


HDU-3951

题目描述:

After hh has learned how to play Nim game, he begins to try another coin game which seems much easier.
The game goes like this:
Two players start the game with a circle of n coins.
They take coins from the circle in turn and every time they could take 1~K continuous coins.
(imagining that ten coins numbered from 1 to 10 and K equal to 3, since 1 and 10 are continuous, you could take away the continuous 10 , 1 , 2 , but if 2 was taken away, you couldn’t take 1, 3, 4, because 1 and 3 aren’t continuous)
The player who takes the last coin wins the game.
Suppose that those two players always take the best moves and never make mistakes.
Your job is to find out who will definitely win the game.

Input

The first line is a number T(1<=T<=100), represents the number of case. The next T blocks follow each indicates a case.
Each case contains two integers N(3<=N<=10 9,1<=K<=10).

Output

For each case, output the number of case and the winner “first” or “second”.(as shown in the sample output)

Sample Input

2
3 1
3 2

Sample Output

Case 1: first
Case 2: second

题目大意

有n个硬币,标号1~n,排成一个圆环,先手与后手可以分别从这些硬币里拿走 连续 的1~k枚,比如当k=3时,可以拿走10,1,2这三枚,也可以拿走1,2这两枚,以此类推,拿走最后一枚硬币的人获胜。

题目分析

这个题目严格意义上叫做对称博弈,不过因为比较小众我把它放在找规律的里面。
其实规律并不难找,只是需要一些脑洞
分为三种情况:
– k=1时,相当于两个人轮流拿硬币,一次一个,这样就显而易见有

n为技术时先手获胜
n为偶数时后手获胜

明确了这些规律,代码也很容易实现。

代码实现

HDU-1517 A Multiplication Game

题目描述

Stan and Ollie play the game of multiplication by multiplying an integer p by one of the numbers 2 to 9. Stan always starts with p = 1, does his multiplication, then Ollie multiplies the number, then Stan and so on. Before a game starts, they draw an integer 1 < n < 4294967295 and the winner is who first reaches p >= n.

Input

Each line of input contains one integer number n.

OUtput

For each line of input output one line either
Stan wins.
or
Ollie wins.
assuming that both of them play perfectly.

Sample Input

162
17
34012226

Sample OUtput

Stan wins.
Ollie wins.
Stan wins.

题目大意

一个乘法游戏,从1开始,先后手依次给这个数乘上2~9,谁先使得这个数超过n谁获得胜利。

题目分析

依据这个,我们可以利用给出的数不停的去除以18,看最终得到的小于18的数字落在1~9区间还是10~18区间,从而判断获胜情况。1~9是先手获胜,10~18是后手获胜

代码实现

后记

这几道找规律的题都是和博弈相关的,在做题的时候自己去分析几组数据,看看得到的结果的规律性,对我们解题很有帮助。

标签:, ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注