[UVA] 11519 - Logo 2
Problem E: Logo 2
Logo is a programming language built around a turtle. Commands in the language cause the turtle to move. The turtle has a pen attached to it. As the turtle moves, it draw lines on the page. The turtle can be programmed to draw interesting pictures.We are interested in making the turtle draw a picture, then return to the point that it started from. For example, we could give the turtle the following program:
fd 100 lt 120 fd 100 lt 120 fd 100
The command fd causes the turtle to move forward by the specified number of units. The command lt causes the turtle to turn left by the specified number of degrees. Thus the above commands cause the turtle to draw an equilateral triangle with sides 100 units long. Notice that after executing the commands, the turtle ends up in the same place as it started. The turtle understands two additional commands. The command bk causes the turtle to move backward by the specified number of units. The command rt causes the turtle to turn right by the specified number of degrees. The distances and angles in all commands are always non-negative integers.
Unfortunately, we have been messy in writing the program down, and cannot read our own writing. One of the numbers in the program is missing. Assuming the turtle ends up at the place that it started at the end of its journey, can you find the missing number?
Input Specification
The first line of input contains one integer specifying the number of test cases to follow. Each test case starts with a line containing one integer, the number of commands to follow. The commands follow, one on each line. Each test case will contain no more than 1000 commands. The argument of each command is either an integer or a question mark (?). There will be exactly one question mark in each test case.Sample Input
1 5 fd 100 lt 120 fd ? lt 120 fd 100
Output Specification
For each test case, output line containing a single integer n such that when the question mark in the program is replaced by n, the turtle ends up at the same point that it started from once the program completes. If the question mark is the argument of an lt or rt command, the angle in the output must be between 0 and 359 degrees, inclusive. The correct answer will always be an integer, and we guarantee that for every test case, there will be only one correct answer.Output for Sample Input
100
Ondřej Lhoták
如果缺角度就直接窮舉，如果缺距離就忽略，最後算離圓心的距離。
假設從 (0, 0) 出發。
#include <stdio.h>
#include <math.h>
char cc[1005][10];
int cv[1005], n;
const double pi = acos(-1);
void getDegree(int pos) {
int i, j, ret = 0;
double dif = 0xffff;
for(i = 0; i < 360; i++) {
double theta = 0, x = 0, y = 0;
cv[pos] = i;
for(j = 0; j < n; j++) {
if(cc[j][0] == 'f') {//forward
x += cv[j]*cos(theta*pi/180);
y += cv[j]*sin(theta*pi/180);
} else if(cc[j][0] == 'b') {
x -= cv[j]*cos(theta*pi/180);
y -= cv[j]*sin(theta*pi/180);
} else if(cc[j][0] == 'l') {
theta += cv[j];
} else {
theta -= cv[j];
}
}
if(fabs(x)+fabs(y) < dif) {
dif = fabs(x)+fabs(y);
ret = i;
}
}
printf("%d\n", ret);
}
void getDist(int pos) {
int i, j;
double px = 0, py = 0, qx = 0, qy = 0;
double theta = 0;
for(i = 0; i < pos; i++) {
if(cc[i][0] == 'f') {//forward
px += cv[i]*cos(theta*pi/180);
py += cv[i]*sin(theta*pi/180);
} else if(cc[i][0] == 'b') {
px -= cv[i]*cos(theta*pi/180);
py -= cv[i]*sin(theta*pi/180);
} else if(cc[i][0] == 'l') {
theta += cv[i];
} else {
theta -= cv[i];
}
}
for(i = pos+1; i < n; i++) {
if(cc[i][0] == 'f') {//forward
qx += cv[i]*cos(theta*pi/180);
qy += cv[i]*sin(theta*pi/180);
} else if(cc[i][0] == 'b') {
qx -= cv[i]*cos(theta*pi/180);
qy -= cv[i]*sin(theta*pi/180);
} else if(cc[i][0] == 'l') {
theta += cv[i];
} else {
theta -= cv[i];
}
}
printf("%.0lf\n", hypot(px+qx, py+qy));
}
int main() {
int testcase, i;
scanf("%d", &testcase);
char foo[10];
while(testcase--) {
scanf("%d", &n);
int pos = 0;
for(i = 0; i < n; i++) {
scanf("%s %s", cc[i], foo);
if(foo[0] == '?') cv[i] = -1, pos = i;
else
sscanf(foo, "%d", &cv[i]);
}
if(cc[pos][0] != 'f' && cc[pos][0] != 'b')
getDegree(pos);
else
getDist(pos);
}
return 0;
}