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

3
-1 0
0 3
2 -1

Sample Output

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

#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' &amp;&amp; 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]) &amp; 1);
	for (int i = 1; i < n; ++i)
		if ((abs(x[i] + y[i]) &amp; 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');
	}
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据