AtCoder ARC 103 D - Robot Arms

Problem Statement

Snuke is introducing a robot arm with the following properties to his factory:

The robot arm consists of m sections and m+1 joints. The sections are numbered 1, 2, …, m, and the joints are numbered 0, 1, …, m. Section i connects Joint i−1 and Joint i. The length of Section i is di. For each section, its mode can be specified individually. There are four modes: L, R, D and U. The mode of a section decides the direction of that section. If we consider the factory as a coordinate plane, the position of Joint i will be determined as follows (we denote its coordinates as \((x_i,y_i)\)): \((x_0,y_0)=(0,0)\).

If the mode of Section i is L, \((x_i,y_i)=(x_i−1−d_i,y_i−1)\).
If the mode of Section i is R, \((x_i,y_i)=(x_i−1+d_i,y_i−1)\).
If the mode of Section i is D, \((x_i,y_i)=(x_i−1,y_i−1−d_i)\).
If the mode of Section i is U, \((x_i,y_i)=(x_i−1,y_i−1+d_i)\).

Snuke would like to introduce a robot arm so that the position of Joint m can be matched with all of the N points \((X_1,Y_1),(X_2,Y_2),…,(X_N,Y_N)\) by properly specifying the modes of the sections. Is this possible? If so, find such a robot arm and how to bring Joint m to each point \((X_j,Y_j)\).

Constraints

All values in input are integers. \(1≤N \le 1000\) \(−10^9 \le X_i \le 10^9\) \(−10^9 \le Y_i \le 10^9\) Partial Score In the test cases worth 300 points, \(−10 \le Xi \le 10\) and \(−10 \le Y_i \le 10\) hold.

Sample Input

Sample Output

1
2
3
4
5
2
1 2
RL
UU
DR

Solution

考虑由{1,2,4,…,2^k}组成的机器人臂长，通过所述操作一定能走到(x,y)，|x|+|y|<2^{k+1}且(x+y)为奇数。

证明可以考虑数学归纳法。

考虑如何添加正负号？

从后往前做，{1,2,4,…,2^k}，2^{k+1}（从后往前走一步） → {1,2,4,…,2^{k-1}}，2^k。

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <cstdio>
#include <algorithm>
typedef long long LL;
typedef unsigned long long ULL;
const int MAXN = 100005;
const int P = 1000000007;
const double eps = 1e-6;
using namespace std;
inline int getint() {
    int r = 0; bool b = true; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') b = false; c = getchar(); }
    while (c >= '0' && c <= '9') { r = (r<<1)+(r<<3) + c - '0'; c = getchar(); }
    return b ? r : -r;
}
int n;
int x[MAXN], y[MAXN];
int cnt, mx[MAXN];
char dst[MAXN];
int main() {
    n = getint();
	for (int i = 0; i < n; ++i) {
		x[i] = getint();
		y[i] = getint();
	}
	int b = (abs(x[0] + y[0]) & 1);
	for (int i = 1; i < n; ++i)
		if ((abs(x[i] + y[i]) & 1) != b) {
			puts("-1");
			return 0;
		}
	printf("%d\n", 32 - b);
	dst[0] = 1;
	if (b == 0) printf("1 ");
	mx[0] = 0;
	for (int i = 1; i < 31; ++i)
		mx[i] = mx[i-1] * 2 + 1;
	for (int i = 0; i < 31; ++i)
		printf("%d ", (1<<i));
	putchar('\n');
	for (int i = 0; i < n; ++i) {
		int X = x[i], Y = y[i];
		if (b == 0) {
			putchar('R');
			--X;
		}
		cnt = 0;
		for (int j = 30; j >= 0; --j) {
			if ((LL) abs(X + (1<<j)) + abs(Y) <= (LL) mx[j]) {
				dst[++cnt] = 'L';
				X += (1<<j);
				continue;
			}
			if ((LL) abs(X - (1<<j)) + abs(Y) <= (LL) mx[j]) {
				dst[++cnt] = 'R';
				X -= (1<<j);
				continue;
			}
			if ((LL) abs(X) + abs(Y + (1<<j)) <= (LL) mx[j]) {
				dst[++cnt] = 'D';
				Y += (1<<j);
				continue;
			}
			if ((LL) abs(X) + abs(Y - (1<<j)) <= (LL) mx[j]) {
				dst[++cnt] = 'U';
				Y -= (1<<j);
				continue;
			}
		}
		for (int j = cnt; j >= 1; --j) putchar(dst[j]);
		putchar('\n');
	}
}