2017年8月12日提高組T1 YMW的杯子

NO IMAGE

Description


有一天YMW看見競賽室裡面放著n個正面向上的杯子,他隨手把所有的杯子翻轉成正面向下的杯子了。後來突然想起來自己有兩隻手,於是他嘗試同時翻轉兩隻杯子,看下最後能不能翻轉成為全部正面朝下。聰明的你看到了這一切,突然腦子裡面閃過一個問題,假如每次同時翻轉m只杯子,最後能全部翻轉成為正面朝下嗎?(初始時全部正面朝上)

Input


多組資料,每組資料兩個數n和m,以-1,-1結尾

Output


對於每組資料,如果可以輸出Yes,不能輸出No

Hint


Data Limit:
不少於5組資料,不超過20組資料
對於30%的資料n<=10,m<=5
對於70%的資料n<=100,m<=30
對於100%的資料n<=10000,m<=500

每個輸入檔案中n和m有一定梯度和差別,保證每個輸入中不全為Yes或No

Source


BY BPM

Solution


水題,可恥地因為大小寫問題wa了

暴力dfs,觀察到翻轉的順序無關,狀態只和正面/反面的數量有關,那麼搜尋 記憶化就可以了

考慮找規律。不難發現若要n個水杯全翻面,則每個杯子需要翻轉奇數次。對於偶數n任意m都能滿足,對於奇數n只有奇數m能滿足。

Code


#include <stdio.h>
#include <string.h>
#define rep(i, st, ed) for (int i = st; i <= ed; i  = 1)
#define min(x, y) (x)<(y)?(x):(y)
#define N 12001
int v[N];
bool flag;
inline void dfs(int z, int m, int n){
if (v[z]){return ;}
if (z == 0 || flag){
flag = true;
return ;
}
v[z] = 1;
int lim = min(z, m);
rep(i, 1, lim){
if (m - i <= n - z){
dfs(z - i   m - i, m, n);
}
}
lim = min(n - z, m);
rep(i, 1, lim){
if (m - i <= z){
dfs(z   i - m   i, m, n);
}
}
}
int main(void){
int n, m;
while (~scanf("%d %d", &n, &m)){
memset(v, 0, sizeof(v));
if (n == -1 && m == -1){break;}
if (n % m == 0){
puts("Yes");
continue;
}
flag = false;
dfs(n, m, n);
if (flag){
puts("Yes");
}else{
puts("No");
}
}
return 0;
}