「CF451A」Game With Sticks
After winning gold and silver in IOI 2014, Akshat and Malvika want to have some fun. Now they are playing a game on a grid made of nhorizontal and m vertical sticks.
An intersection point is any point on the grid which is formed by the intersection of one horizontal stick and one vertical stick.
In the grid shown below, n = 3 and m = 3. There are n + m = 6 sticks in total (horizontal sticks are shown in red and vertical sticks are shown in green). There are n·m = 9 intersection points, numbered from 1 to 9.
Assume that both players play optimally. Who will win the game?
The first line of input contains two space-separated integers, n and m (1 ≤ n, m ≤ 100).
Print a single line containing “Akshat” or “Malvika” (without the quotes), depending on the winner of the game.
1 |
2 2 |
1 |
Malvika |
1 |
2 3 |
1 |
Malvika |
1 |
3 3 |
1 |
Akshat |
Explanation of the first sample:
The grid has four intersection points, numbered from 1 to 4.
In the empty grid, Akshat cannot make any move, hence he will lose.
Since all 4 intersection points of the grid are equivalent, Akshat will lose no matter which one he picks.
题解
简单的博弈论,每次可以删去一整行以及一整列
那么根据n,m最小值的奇偶性就能判断胜负
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define ll long long #define inf 1000000000 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,ans; int main() { n=read();m=read(); int t=min(n,m); if(t&1)puts("Akshat"); else puts("Malvika"); return 0; } |