当前位置:网站首页>Alice and Bob (2021 Niuke summer multi school training camp 1)
Alice and Bob (2021 Niuke summer multi school training camp 1)
2022-07-06 16:02:00 【It's Xiao Zhang, ZSY】
Alice and Bob
2021 Niuke summer multi school training camp 1 The first question is , I didn't do it at that time , Read this blogger's blog , I understand instantly.
Topic link :https://ac.nowcoder.com/acm/contest/11166/A
source : Cattle from
Title Description
Alice and Bob like playing games. There are two piles of stones with numbers n and m. Alice and Bob take turns to operate, each operation can take away k(k>0) stones from one pile and take away s×k(s≥0) stones from another pile. Alice plays first. The person who cannot perform the operation loses the game.
Please determine who will win the game if both Alice and Bob play the game optimally.
Input description :
The first line contains an integer T(1≤T≤10^4 ) denotes the total number of test cases.
Each test case contains two integers n,m(1≤n,m≤5×10^ 3) in a line, indicating the number of two piles of stones.
Output description :
For each test case, print “Alice” if Alice will win the game, otherwise print “Bob”.
Example 1
Input
Copy
5
2 3
3 5
5 7
7 5
7 7
Output
Copy
Bob
Alice
Bob
Bob
Alice
The main idea of the topic :
A game of two , Each time one person takes one from the pile , At the same time, take it away from another pile k*s individual , Ask who can take it first ;
Ideas :
enumeration , violence , In fact, the idea is very simple , If you can take all the stones in one operation, you will win at this time , We use a two-dimensional array f[i][j] To indicate that the number of stones in the first pile is i The number of stones in the second pile is j The situation of ,f[i][j]=1 Indicates that the state faces two piles of stones, and the number is i,j You can take all the stones in one step ,f[i][j]=0 Indicates that the state faces two piles of stones, and the number is i,j You can't take all the stones at once . According to the title f[k][sk] or f[sk][k] It must be able to take it all at once , So enumeration s And k Find out the status of all the first to win
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;
bool f[5001][5001];
int main()
{
for(int i=0;i<=5000;i++)
{
for(int j=0;j<=5000;j++)
{
if(f[i][j]==0)
{
for(int k=1;k+i<=5000;k++)
{
for(int s=0;s*k+j<=5000;s++)
f[i+k][j+s*k]=1;
}
for(int k=1;k+j<=5000;k++)
{
for(int s=0;s*k+i<=5000;s++)
f[i+s*k][j+k]=1;
}
}
}
}
int t,n,m;
cin>>t;
while(t--)
{
scanf("%d%d",&n,&m);
if(f[n][m]==0)
cout<<"Bob"<<endl;
else
cout<<"Alice"<<endl;
}
}
边栏推荐
- 0 - 1 problème de sac à dos (1)
- 快速转 TypeScript 指南
- Opencv learning log 15 count the number of solder joints and output
- Perform general operations on iptables
- China exterior wall cladding (EWC) market trend report, technical dynamic innovation and market forecast
- 【练习-4】(Uva 11988)Broken Keyboard(破损的键盘) ==(链表)
- Determine the Photo Position
- Shell Scripting
- Opencv learning log 33 Gaussian mean filtering
- Penetration test (1) -- necessary tools, navigation
猜你喜欢
C语言数组的概念
[exercise-7] crossover answers
Gartner: five suggestions on best practices for zero trust network access
Penetration test (3) -- Metasploit framework (MSF)
快速转 TypeScript 指南
frida hook so层、protobuf 数据解析
Record of force deduction and question brushing
Information security - Epic vulnerability log4j vulnerability mechanism and preventive measures
Information security - threat detection - detailed design of NAT log access threat detection platform
TCP的三次握手与四次挥手
随机推荐
Ball Dropping
7-1 懂的都懂 (20 分)
渗透测试 ( 7 ) --- 漏洞扫描工具 Nessus
快速转 TypeScript 指南
socket通讯
[exercise 4-1] cake distribution
nodejs爬虫
Analyse du format protobuf du rideau en temps réel et du rideau historique de la station B
[exercise-6] (UVA 725) division = = violence
Research Report on market supply and demand and strategy of Chinese graphic screen printing equipment industry
CEP used by Flink
b站 實時彈幕和曆史彈幕 Protobuf 格式解析
Path problem before dynamic planning
Optimization method of path problem before dynamic planning
JS调用摄像头
树莓派CSI/USB摄像头使用mjpg实现网页摄像头监控
渗透测试 ( 3 ) --- Metasploit Framework ( MSF )
Flink 使用之 CEP
MySQL grants the user the operation permission of the specified content
TCP的三次握手与四次挥手