C. Ciel and Robot
time limit per test
memory limit per test
input
output
s. Each character of s
- U': go up, (x, y) →
- D': go down, (x, y) →
- L': go left, (x, y) →
- R': go right, (x, y) →
s from left to right, and repeat it infinite times. Help Fox Ciel to determine if after some steps the robot will located in (a, b).
Input
a and b, (9 ≤ a, b ≤ 109). The second line contains a string s (1 ≤ |s| ≤ 100, s only contains characters 'U', 'D', 'L', 'R') — the command.
Output
Yes" if the robot will be located at (a, b), and "No" otherwise.
Examples
input
2 2 RU
output
Yes
input
1 2 RU
output
No
input
-1 1000000000 LRRLU
output
Yes
input
0 0 D
output
Yes
把robot沿着s串走一次称为一周期，一周期后走到(x, y)若x != 0 || y != 0则接下来每一周期结束后走到的点都在(0, 0)->(x, y)这条射线上.把(a, b)沿着s串逆方向走，观察是否在这条射线上
#include <bits/stdc++.h>
#define maxn 105
using namespace std;
typedef long long ll;
char s[maxn];
int a, b, x, y, p1, p2;
bool judge(int k1, int k2){
if(k1 == 0 && k2 == 0)
return true;
if(x == 0 && y == 0){
if(k1 == 0 && k2 == 0)
return true;
return false;
}
if(x == 0){
if(k1 == 0 && (ll)y * k2 > 0 && k2 % y == 0)
return true;
return false;
}
if(y == 0){
if(k2 == 0 && (ll)x * k1 > 0 && k1 % x == 0)
return true;
return false;
}
if((ll)x * k2 == (ll)y * k1 && (ll)x * k1 > 0 && (ll)y * k2 > 0 && k1 % x == 0 && k2 % y == 0)
return true;
return false;
}
int main(){
// freopen("in.txt", "r", stdin);
scanf("%d%d%s", &a, &b, s);
x = 0;
y = 0;
for(int i = 0; s[i]; i++){
if(s[i] == 'L')
x--;
else if(s[i] == 'R')
x++;
else if(s[i] == 'D')
y--;
else
y++;
}
if(judge(a, b)){
puts("Yes");
return 0;
}
int len = strlen(s);
for(int i = len-1; i >= 0; i--){
p1 = a, p2 = b;
for(int j = i; j >= 0; j--){
if(s[j] == 'L')
p1++;
else if(s[j] == 'R')
p1--;
else if(s[j] == 'D')
p2++;
else
p2--;
}
if(judge(p1, p2)){
puts("Yes");
return 0;
}
}
puts("No");
return 0;
}