HDU 5512 Pagodas 找规律 (2015ACM/ICPC亚洲区沈阳站)

本文主要是介绍HDU 5512 Pagodas 找规律 (2015ACM/ICPC亚洲区沈阳站)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目链接】：click here~~

Pagodas

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 15 Accepted Submission(s): 14

Problem Description

n pagodas were standing erect in Hong Jue Si between the Niushou Mountain and the Yuntai Mountain, labelled from

1 to

n . However, only two of them (labelled

a and

b , where

1≤a≠b≤n ) withstood the test of time.

Two monks, Yuwgna and Iaka, decide to make glories great again. They take turns to build pagodas and Yuwgna takes first. For each turn, one can rebuild a new pagodas labelled

i (i∉{a,b} and 1≤i≤n) if there exist two pagodas standing erect, labelled

j and

k respectively, such that

i=j+k or

i=j−k . Each pagoda can not be rebuilt twice.

This is a game for them. The monk who can not rebuild a new pagoda will lose the game.

Input

The first line contains an integer

t (1≤t≤500) which is the number of test cases.
For each test case, the first line provides the positive integer

n (2≤n≤20000) and two different integers

a and

b .

Output

For each test case, output the winner (``Yuwgna" or ``Iaka"). Both of them will make the best possible decision each time.

Sample Input

Sample Output

  Case #1: Iaka
Case #2: Yuwgna
Case #3: Yuwgna
Case #4: Iaka
Case #5: Iaka
Case #6: Iaka
Case #7: Yuwgna
Case #8: Yuwgna
Case #9: Iaka
Case #10: Iaka
Case #11: Yuwgna
Case #12: Yuwgna
Case #13: Iaka
Case #14: Yuwgna
Case #15: Iaka
Case #16: Iaka

【题目大意】：已更新：（本来说的造塔游戏，抽象成下面说更容易理解）

题意：给你三个数：n,a,b，一开始集合里面有两个数：a和b，然后两个人轮流往这个集合里面增加数字，增加的这个数字的原则是：这个集合里面任选两个数的和或差（a + b或a - b或b -a的中的任意一个没被选中的符合[1,n]的点），集合里面的数字不能重复，同时这个数字不能大于 n ，求最后哪个人选不了满足条件的数了。

【思路】(n/gcd(a,b)&1)即可，为什么这样说呢？思考一下：a + b或a - b或b -a这样的数次操作之后，无论怎样，最后得到的这个集合里面的数列，其实是一个等差数列，想到这这就简单了，由最开始的 a 和 b 来相减，不断地取最小的两个数相减，然后等到等差数列的差，这个差同时也是等差数列的首项（即为gcd(a,b)），然后拿 n 除以这个差就是在 n 的范围内可以得到的数字的个数了，然后因为分先手和后手，所以最后只要判断一下个数的奇偶数就可以得到答案了。

代码：

/***************************
* Problem: HDU No.5512
* Running time: 0MS  
* Complier: G++  
* Author: herongwei 
* Create Time: 17:30 2015/10/31 
*****************************/  
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;int main()
{int t,tot=1;scanf("%d",&t);while(t--){int n,a,b;scanf("%d%d%d",&n,&a,&b);int gcd=__gcd(a,b);int ans=n/gcd;printf("Case #%d: ",tot++);if(ans&1) puts("Yuwgna");else  puts("Iaka");}return 0;
}

这篇关于HDU 5512 Pagodas 找规律 (2015ACM/ICPC亚洲区沈阳站)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！