解题思路

我们从左到右遍历 $x$ 的各位数字。

• 如果当前位 $x_i$ 是 $0$ 或 $2$，我们可以设置 $a_i = b_i = 0$ 或 $a_i = b_i = 1$ 对应地（因为 $0+0=0$，$1+1=2$，模 $3$ 后符合要求）。没有更好的选择。
• 如果当前位 $x_i$ 是 $1$，最优的选择是设 $a_i = 1$，$b_i = 0$（这样 $a$ 会在这一位大于 $b$）。

一旦我们遇到了第一个 $1$，并按照上述方式分配，那么 $a$ 就已经大于 $b$（即使之后 $b$ 的所有位都取 $2$ 也无法反超）。因此，对于所有 $j > i$，我们直接设 $a_j = 0$，$b_j = x_j$ 即可，这样能保证 $\max(a,b)$ 尽可能小。

如果没有遇到 $1$（即 $x$ 全由 $0$ 和 $2$ 组成），则我们始终可以设 $a_i = b_i = x_i / 2$，这种情况也会被上述逻辑自动处理（因为永远不会触发 $a$ 大于 $b$ 的标记）。

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		string x;
		cin >> n >> x;
		string a(n, '0'), b(n, '0');
		for (int i = 0; i < n; ++i) {
			if (x[i] == '1') {
				a[i] = '1';
				b[i] = '0';
				for (int j = i + 1; j < n; ++j) {
					b[j] = x[j];
				}
				break;
			} else {
				a[i] = b[i] = '0' + (x[i] - '0') / 2;
			}
		}
		cout << a << endl << b << endl;
	}
	
	return 0;
}