话说我的习惯是一套题全部改完后才写题解，然而上次的题解停留在 \(20.1\) ，这足以看出近两日的颓废现状。
由于昨天晚上做了个噩梦，所以今天的题解先扯点别的。
目前初步鉴定噩梦是由 Fate Zero 中 Caster 的行为引起的。
比较显然 Caster 及其御主都是以他人的痛苦为乐的人。
在现代社会，我们是在反对这种行为的，我们提倡所有人以他人的幸福为幸福，让所有人获得幸福。
然而老虚的作品似乎在表达这终究不能实现。
在 Fate 中的体现是卫宫切嗣对战争的批判，从古至今所有人都在歌颂战场中的英雄，然而老虚的观点是：战场上从来不存在希望，只有无尽的绝望。
貌似魔圆的作者也是老虚，仔细思考魔圆中似乎也体现着这点：宇宙中希望和绝望是守恒的，在给他人带来希望时，却由不得不带来等量的绝望。
所以 B 站上很多评论表示，老虚是永远无法得到幸福的人。
我们每个人或许都是这样吧。
T1 地图编辑
比较显然的结论是一个合法图存在一个点使得删去这个点后，最短路不变或最短路减 \(2\) 。
因此我们可以不断删去这种点，然后判断整张图最短路是否为 \(D\) 。
考虑 \(O(1)\) 确定这个点，首先找到一个由墙壁组成的连通块，以其中任意点为起点求解连通块内每个墙壁到当前点的最短路，此时最短距离最大的点可以被删除。
简单证明：
由于最短距离最大，因此空白部分一定组成连通图；
假设不满足 pattern \(2\times 2\) 的限制，在这个 \(2\times 2\) 的方格中，设墙壁为 \(X, Y\) ，空白为 \(A, B\) ，其中 \(A\) 为上次删去的墙壁，由于 \(A, B\) 联通，因此 \(X, Y\) 此时不存在一条四联通的路径，也就是 \(X, Y\) 联通必然经过 \(A\) ，容易发现 \(X, Y\) 中一定存在一点最短路径大于 \(A\) 。
由于删去的墙壁越多，最短路越小，因此可以预处理删除序列，之后二分答案即可。
code
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int max1 = 1e3;
const int inf = 0x3f3f3f3f;
int n, m, d;
char mp[max1 + 5][max1 + 5];
struct Point
{
int x, y;
Point () {}
Point ( int __x, int __y )
{ x = __x, y = __y; }
bool operator == ( const Point &A ) const
{
return x == A.x && y == A.y;
}
};
Point seq[max1 * max1 + 5], que[max1 * max1 + 5], S, T;
int len, L, R;
bool vis[max1 + 5][max1 + 5];
int dis[max1 + 5][max1 + 5];
bool Check ( int x, int y )
{
if ( x == 1 || x == n || y == 1 || y == m )
return false;
if ( mp[x][y] != '#' )
return false;
if ( mp[x - 1][y] == '#' && mp[x][y - 1] == '#' && mp[x - 1][y - 1] != '#' )
return false;
if ( mp[x - 1][y] == '#' && mp[x][y + 1] == '#' && mp[x - 1][y + 1] != '#' )
return false;
if ( mp[x + 1][y] == '#' && mp[x][y - 1] == '#' && mp[x + 1][y - 1] != '#' )
return false;
if ( mp[x + 1][y] == '#' && mp[x][y + 1] == '#' && mp[x + 1][y + 1] != '#' )
return false;
if ( mp[x - 1][y] == '#' && mp[x + 1][y] == '#' )
return false;
if ( mp[x][y - 1] == '#' && mp[x][y + 1] == '#' )
return false;
return true;
}
int Bfs ()
{
for ( int i = 1; i <= n; i ++ )
memset(dis[i] + 1, 0x3f, sizeof(int) * m);
L = 1, R = 0; que[++R] = S; dis[S.x][S.y] = 0;
while ( L <= R )
{
Point now = que[L++];
if ( now == T )
return dis[now.x][now.y];
if ( mp[now.x - 1][now.y] != '#' && dis[now.x - 1][now.y] == inf )
{
dis[now.x - 1][now.y] = dis[now.x][now.y] + 1;
que[++R] = Point(now.x - 1, now.y);
}
if ( mp[now.x + 1][now.y] != '#' && dis[now.x + 1][now.y] == inf )
{
dis[now.x + 1][now.y] = dis[now.x][now.y] + 1;
que[++R] = Point(now.x + 1, now.y);
}
if ( mp[now.x][now.y - 1] != '#' && dis[now.x][now.y - 1] == inf )
{
dis[now.x][now.y - 1] = dis[now.x][now.y] + 1;
que[++R] = Point(now.x, now.y - 1);
}
if ( mp[now.x][now.y + 1] != '#' && dis[now.x][now.y + 1] == inf )
{
dis[now.x][now.y + 1] = dis[now.x][now.y] + 1;
que[++R] = Point(now.x, now.y + 1);
}
}
return inf;
}
bool Check ( int x )
{
for ( int i = 1; i <= x; i ++ )
mp[seq[i].x][seq[i].y] = '.';
for ( int i = x + 1; i <= len; i ++ )
mp[seq[i].x][seq[i].y] = '#';
return Bfs() <= d;
}
int main ()
{
freopen("map.in", "r", stdin);
freopen("map.out", "w", stdout);
scanf("%d%d%d", &n, &m, &d);
for ( int i = 1; i <= n; i ++ )
scanf("%s", mp[i] + 1);
L = 1, R = 0;
for ( int i = 1; i <= n; i ++ )
for ( int j = 1; j <= m; j ++ )
if ( Check(i, j) && !vis[i][j] )
seq[++R] = Point(i, j), mp[i][j] = '.', vis[i][j] = true;
while ( L <= R )
{
Point now = seq[L++];
if ( Check(now.x - 1, now.y) && !vis[now.x - 1][now.y] )
seq[++R] = Point(now.x - 1, now.y), mp[now.x - 1][now.y] = '.', vis[now.x - 1][now.y] = true;
if ( Check(now.x + 1, now.y) && !vis[now.x + 1][now.y] )
seq[++R] = Point(now.x + 1, now.y), mp[now.x + 1][now.y] = '.', vis[now.x + 1][now.y] = true;
if ( Check(now.x, now.y - 1) && !vis[now.x][now.y - 1] )
seq[++R] = Point(now.x, now.y - 1), mp[now.x][now.y - 1] = '.', vis[now.x][now.y - 1] = true;
if ( Check(now.x, now.y + 1) && !vis[now.x][now.y + 1] )
seq[++R] = Point(now.x, now.y + 1), mp[now.x][now.y + 1] = '.', vis[now.x][now.y + 1] = true;
}
len = R;
for ( int i = 1; i <= n; i ++ )
{
for ( int j = 1; j <= m; j ++ )
{
if ( mp[i][j] == 'S' )
S = Point(i, j);
if ( mp[i][j] == 'F' )
T = Point(i, j);
}
}
int L = 0, R = len, ans = 0;
while ( L <= R )
{
int mid = (L + R) >> 1;
if ( Check(mid) )
ans = mid, R = mid - 1;
else
L = mid + 1;
}
for ( int i = 1; i <= ans; i ++ )
mp[seq[i].x][seq[i].y] = '.';
for ( int i = ans + 1; i <= len; i ++ )
mp[seq[i].x][seq[i].y] = '#';
if ( Bfs() != d )
puts("No");
else
{
puts("Yes");
for ( int i = 1; i <= n; i ++ )
puts(mp[i] + 1);
}
return 0;
}
T2 摸底测试
考虑快速求解 \(g(S)\) ，由于题目限制为本质不同的子串，那么比较显然的想法是建立 SAM ，每个节点上维护最大和最小的 endpos ，容易发现当前节点所代表子串会对最小 endpos 到最大 endpos 之间的断点的 \(f\) 值造成贡献，由于每个节点的串长度是一段连续的区间，因此维护差分的差分便能快速求解。
于是直接二分答案，对于当前左端点，找到尽可能远的右端点使得 \(g(S)\le mid\) ，使用倍增 + 二分求解， Check 的复杂度为 \(O(n\log n)\) 。
不得不吐槽这题的大样例， SAM 中的 Extened 函数写挂，结果大样例全过，于是 \(100\) 分挂成 \(5\) 分。
code
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int max1 = 5e4;
int n, k;
char s[max1 + 5];
struct Suffix_Automaton
{
int trans[max1 * 2 + 5][26], link[max1 * 2 + 5];
int maxpos[max1 * 2 + 5], minpos[max1 * 2 + 5], maxlen[max1 * 2 + 5];
int last, total;
int bin[max1 + 5], seq[max1 * 2 + 5];
long long f[max1 + 5];
void Clear ()
{
memset(trans[0], 0, sizeof(trans[0])); link[0] = -1;
maxpos[0] = minpos[0] = maxlen[0] = 0;
last = total = 0;
return;
}
void Extend ( char c )
{
int now = ++total, p = last;
memset(trans[now], 0, sizeof(trans[now]));
maxpos[now] = minpos[now] = maxlen[now] = maxlen[p] + 1;
last = now;
while ( p != -1 && !trans[p][c - 'a'] )
trans[p][c - 'a'] = now, p = link[p];
if ( p == -1 )
link[now] = 0;
else
{
int q = trans[p][c - 'a'];
if ( maxlen[q] == maxlen[p] + 1 )
link[now] = q;
else
{
int clone = ++total;
memcpy(trans[clone], trans[q], sizeof(trans[q]));
link[clone] = link[q];
maxpos[clone] = 0, minpos[clone] = n + 1;
maxlen[clone] = maxlen[p] + 1;
link[q] = link[now] = clone;
while ( p != -1 && trans[p][c - 'a'] == q )
trans[p][c - 'a'] = clone, p = link[p];
}
}
return;
}
long long Calc ()
{
int lim = maxlen[last];
memset(bin, 0, sizeof(int) * (lim + 1));
memset(f, 0, sizeof(long long) * (lim + 1));
for ( int i = 0; i <= total; i ++ )
++bin[maxlen[i]];
for ( int i = 1; i <= lim; i ++ )
bin[i] += bin[i - 1];
for ( int i = total; i >= 0; i -- )
seq[--bin[maxlen[i]]] = i;
for ( int i = total; i >= 1; i -- )
{
int now = seq[i];
if ( minpos[now] != maxpos[now] )
{
int minL = maxlen[link[now]] + 1;
if ( maxpos[now] - minL >= minpos[now] )
{
int maxL = min(maxlen[now], maxpos[now] - minpos[now]);
f[minpos[now]] += maxL - minL + 1;
f[minpos[now] + 1] -= maxL - minL + 1;
--f[maxpos[now] - maxL + 1];
++f[maxpos[now] - minL + 2];
}
}
minpos[link[now]] = min(minpos[link[now]], minpos[now]);
maxpos[link[now]] = max(maxpos[link[now]], maxpos[now]);
}
for ( int i = 1; i <= lim - 1; i ++ )
f[i] += f[i - 1];
for ( int i = 1; i <= lim - 1; i ++ )
f[i] += f[i - 1];
long long res = 0;
for ( int i = 1; i <= lim - 1; i ++ )
res += 1LL * f[i] * f[i];
return res;
}
}SAM;
long long Calc ( int L, int R )
{
SAM.Clear();
for ( int i = L; i <= R; i ++ )
SAM.Extend(s[i]);
return SAM.Calc();
}
bool Check ( long long x )
{
int cnt = 0;
for ( int i = 1, j; i <= n; i = j + 1 )
{
int L = i, R = i;
for ( int len = 1; i + len - 1 <= n; len <<= 1 )
{
if ( Calc(i, i + len - 1) <= x )
L = i + len - 1, R = i + len + len - 1;
else
break;
}
R = min(R, n);
while ( L <= R )
{
int mid = (L + R) >> 1;
if ( Calc(i, mid) <= x )
j = mid, L = mid + 1;
else
R = mid - 1;
}
if ( (++cnt) > k )
return false;
}
return true;
}
int main ()
{
freopen("string.in", "r", stdin);
freopen("string.out", "w", stdout);
scanf("%d%d%s", &n, &k, s + 1);
long long L = 0, R = Calc(1, n), ans = 0;
while ( L <= R )
{
long long mid = (L + R) >> 1;
if ( Check(mid) )
ans = mid, R = mid - 1;
else
L = mid + 1;
}
printf("%lld\n", ans);
return 0;
}
T3 回文之和
根据某些奇怪的论文，我们知道任意正整数可以被拆分为不超过 \(3\) 个回文数相加的形式。
答案为 \(1\) 的情况是非常容易的；
答案为 \(2\) 的情况需要我们实现函数 \(f(x)\) 求解两个回文数相加等于 \(x\) 。
答案为 \(3\) 的情况，通过打表发现存在一种构造使得最小的回文数足够小，也就是最小的回文数可以直接暴力枚举。
只需要将一个数 \(x\) 表示为两个回文数相加。
设 \(Dfs(X, n, m)\) 可以返回 \(Y_1+Y_2=x\) ，满足 \(Y_1, Y_2\) 为回文数， \(Y_1\) 最高位为 \(n\) ， \(Y_2\) 最高位为 \(m\) ，且 \(n\ge m\) 。
如果 \(n\ne m\) ：
如果 \(X\) 的位数等于 \(n\) ，需要考虑 \(X\) 的最高位是否得到了下一位的进位，因此枚举 \(X\) 的最高位是否得到进位，我们可以确定 \(Y_1\) 的最高位和最低位，根据 \(X\) 最低位的数值，可以计算得到 \(Y_2\) 的最高位和最低位，发现确定 \(Y_1, Y_2\) 的其余位的过程构成一个子问题，可以直接递归求解。
如果 \(X\) 的位数不等于 \(n\) ，那么 \(X\) 的位数必须等于 \(n+1\) ，此时最高位必须为 \(1\) ，次高位必须为 \(0\) ， \(Y_1\) 的最高位和最低位必须等于 \(9\) ，简单计算仍然可以确定 \(Y_2\) 的最高位和最低位。
如果 \(n=m\) ：
如果 \(X\) 的位数等于 \(n\) ，容易发现此时 \(X\) 的最高位与最低位只能相差 \(1\) ，此时 \(Y_1, Y_2\) 最高位和最低位具体的数值不产生影响，只需要保证相加后满足 \(X\) 的最高位和最低位限制即可。
如果 \(X\) 的位数不等于 \(n\) ，仍然发现此时 \(X\) 的位数只能为 \(n+1\) ，仍然有 \(X\) 的最高位与最低位只能相差 \(1\) ， \(Y_1, Y_2\) 在这一位的具体数值仍然不产生影响。
基本情况就是上述两种，考虑处理边界：
如果 \(m=0\) ，检查 \(X\) 的前 \(n\) 位是否构成回文即可。
如果 \(m=1\) ，可以直接枚举 \(Y_2\) 这一位的数值，暴力求解 \(Y_1\) 并检查其是否为回文。
由于我们递归进行求解，因此第一层 Dfs 时， \(Y_1, Y_2\) 不能取前导零，其余 Dfs 均可以取前导零，简单特判即可。
递归过程中可能存在 \(X\) 的位数小于 \(n\) 的情况，这种情况难以归纳到 \(n\ne m\) 和 \(n=m\) 的求解中，需要进行特判。
考虑求解回文数 \(Y_1, Y_2\) 相加等于 \(X\) ，枚举 \(Y_1, Y_2\) 的位数并调用上述函数，容易发现 \(Y_1\) 的位数与 \(X\) 的位数只能相差 \(1\) ，因此只需要枚举 \(Y_2\) 的位数即可。
复杂度玄学。
code
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int max1 = 40;
const int base = 1e5, bit = 5, power[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };
int T, n;
char s[max1 + 5];
struct Great_Int
{
int num[max1 + 5], maxbit;
Great_Int ()
{
memset(num, 0, sizeof(num));
maxbit = 0;
}
int Kth_Bit ( int k ) const
{
return (num[k / bit] / power[k % bit]) % 10;
}
void Insert ( int k, int x )
{
num[k / bit] -= power[k % bit] * Kth_Bit(k);
num[k / bit] += power[k % bit] * x;
return;
}
int High_Bit () const
{
for ( int i = max1; i >= 0; i -- )
if ( Kth_Bit(i) )
return i + 1;
return 0;
}
Great_Int operator + ( const Great_Int &tmp ) const
{
Great_Int res; res.maxbit = max(maxbit, tmp.maxbit);
for ( int i = 0; i < res.maxbit; i ++ )
{
res.num[i] += num[i] + tmp.num[i];
if ( res.num[i] >= base )
{
res.num[i] -= base;
++res.num[i + 1];
}
}
if ( res.num[res.maxbit] )
++res.maxbit;
while ( res.maxbit && !res.num[res.maxbit - 1] )
--res.maxbit;
return res;
}
Great_Int operator - ( const Great_Int &tmp ) const
{
Great_Int res; res.maxbit = maxbit; int flag = 0;
for ( int i = 0; i < res.maxbit; i ++ )
{
res.num[i] = num[i] - tmp.num[i] - flag;
flag = 0;
if ( res.num[i] < 0 )
{
res.num[i] += base;
flag = 1;
}
}
while ( res.maxbit && !res.num[res.maxbit - 1] )
--res.maxbit;
return res;
}
Great_Int operator - ( const int &tmp ) const
{
Great_Int res; res.maxbit = maxbit; int flag = -tmp;
for ( int i = 0; i < res.maxbit; i ++ )
{
res.num[i] = num[i] + flag;
flag = 0;
if ( res.num[i] < 0 )
{
flag = (res.num[i] + 1) / base - 1;
res.num[i] += -flag * base;
}
}
while ( res.maxbit && !res.num[res.maxbit - 1] )
--res.maxbit;
return res;
}
Great_Int operator >> ( const int &tmp ) const
{
Great_Int res; res.maxbit = (max1 - 1) / bit + 1;
int high = High_Bit();
for ( int i = 0; i + tmp < high; i ++ )
res.Insert(i, Kth_Bit(i + tmp));
while ( res.maxbit && !res.num[res.maxbit - 1] )
--res.maxbit;
return res;
}
Great_Int operator << ( const int &tmp ) const
{
Great_Int res; res.maxbit = (max1 - 1) / bit + 1;
for ( int i = tmp; i < max1; i ++ )
res.Insert(i, Kth_Bit(i - tmp));
while ( res.maxbit && !res.num[res.maxbit - 1] )
--res.maxbit;
return res;
}
bool operator < ( const Great_Int &tmp ) const
{
for ( int i = max(maxbit, tmp.maxbit) - 1; i >= 0; i -- )
{
if ( num[i] < tmp.num[i] )
return true;
if ( num[i] > tmp.num[i] )
return false;
}
return false;
}
bool operator <= ( const Great_Int &tmp ) const
{
return !(tmp < *this);
}
bool Check () const
{
if ( !maxbit )
return true;
int high = High_Bit();
for ( int i = 0; i < high; i ++ )
if ( Kth_Bit(i) != Kth_Bit(high - i - 1) )
return false;
return true;
}
bool Check ( int high ) const
{
for ( int i = 0; i < high; i ++ )
if ( Kth_Bit(i) != Kth_Bit(high - i - 1) )
return false;
return true;
}
void Print () const
{
if ( !maxbit )
printf("0 ");
else
{
printf("%d", num[maxbit - 1]);
for ( int i = maxbit - 2; i >= 0; i -- )
printf("%05d", num[i]);
printf(" ");
}
return;
}
};
struct Data
{
bool flag;
Great_Int Y1, Y2;
};
bool Check ( int x, int maxbit )
{
for ( int i = 0; i < maxbit; i ++ )
if ( (x / power[i]) % 10 != (x / power[maxbit - i - 1]) % 10 )
return false;
return true;
}
Data Dfs ( Great_Int X, int n, int m, bool is_high )
{
Data res; res.flag = false;
if ( !m )
{
if ( X.High_Bit() <= n && X.Check(n) && !is_high )
{
res.flag = true;
res.Y1 = X;
}
return res;
}
if ( m == 1 )
{
for ( int i = 0; i < 10; i ++ )
{
res.Y2.maxbit = 1;
res.Y2.num[0] = i;
if ( res.Y2 <= X )
{
res.Y1 = X - res.Y2;
if ( res.Y1.High_Bit() <= n && res.Y1.Check(n) && (!is_high || (res.Y1.Kth_Bit(n - 1) && res.Y2.Kth_Bit(m - 1))) )
{
res.flag = true;
return res;
}
}
}
return res;
}
if ( n > X.High_Bit() )
{
if ( !X.High_Bit() )
{
if ( !is_high )
res.flag = true;
return res;
}
res.Y1.maxbit = (n - 1) / bit + 1;
res.Y2.maxbit = (m - 1) / bit + 1;
res.Y1.Insert(n - 1, 0);
res.Y1.Insert(0, 0);
res.Y2.Insert(m - 1, X.Kth_Bit(0));
res.Y2.Insert(0, X.Kth_Bit(0));
Great_Int sum = res.Y1 + res.Y2;
if ( sum <= X )
{
Data d = Dfs((X - sum) >> 1, n - 2, m - 2, 0);
if ( d.flag && (!is_high || (res.Y1.Kth_Bit(n - 1) && res.Y2.Kth_Bit(m - 1))) )
{
res.flag = true;
res.Y1 = res.Y1 + (d.Y1 << 1);
res.Y2 = res.Y2 + (d.Y2 << 1);
}
}
return res;
}
if ( n != m )
{
if ( X.High_Bit() == n )
{
res.Y1.maxbit = (n - 1) / bit + 1;
res.Y2.maxbit = (m - 1) / bit + 1;
res.Y1.Insert(n - 1, X.Kth_Bit(n - 1));
res.Y1.Insert(0, X.Kth_Bit(n - 1));
res.Y2.Insert(m - 1, (X.Kth_Bit(0) - res.Y1.Kth_Bit(0) + 10) % 10);
res.Y2.Insert(0, (X.Kth_Bit(0) - res.Y1.Kth_Bit(0) + 10) % 10);
Great_Int sum = res.Y1 + res.Y2;
if ( sum <= X )
{
Data d = Dfs((X - sum) >> 1, n - 2, m - 2, 0);
if ( d.flag && (!is_high || (res.Y1.Kth_Bit(n - 1) && res.Y2.Kth_Bit(m - 1))) )
{
res.flag = true;
res.Y1 = res.Y1 + (d.Y1 << 1);
res.Y2 = res.Y2 + (d.Y2 << 1);
return res;
}
}
res.Y1.Insert(n - 1, X.Kth_Bit(n - 1) - 1);
res.Y1.Insert(0, X.Kth_Bit(n - 1) - 1);
res.Y2.Insert(m - 1, (X.Kth_Bit(0) - res.Y1.Kth_Bit(0) + 10) % 10);
res.Y2.Insert(0, (X.Kth_Bit(0) - res.Y1.Kth_Bit(0) + 10) % 10);
sum = res.Y1 + res.Y2;
if ( sum <= X )
{
Data d = Dfs((X - sum) >> 1, n - 2, m - 2, 0);
if ( d.flag && (!is_high || (res.Y1.Kth_Bit(n - 1) && res.Y2.Kth_Bit(m - 1))) )
{
res.flag = true;
res.Y1 = res.Y1 + (d.Y1 << 1);
res.Y2 = res.Y2 + (d.Y2 << 1);
return res;
}
}
}
if ( X.High_Bit() == n + 1 )
{
if ( X.Kth_Bit(n) == 1 && X.Kth_Bit(n - 1) == 0 )
{
res.Y1.maxbit = (n - 1) / bit + 1;
res.Y2.maxbit = (m - 1) / bit + 1;
res.Y1.Insert(n - 1, 9);
res.Y1.Insert(0, 9);
res.Y2.Insert(m - 1, (X.Kth_Bit(0) - res.Y1.Kth_Bit(0) + 10) % 10);
res.Y2.Insert(0, (X.Kth_Bit(0) - res.Y1.Kth_Bit(0) + 10) % 10);
Great_Int sum = res.Y1 + res.Y2;
if ( sum <= X )
{
Data d = Dfs((X - sum) >> 1, n - 2, m - 2, 0);
if ( d.flag && (!is_high || (res.Y1.Kth_Bit(n - 1) && res.Y2.Kth_Bit(m - 1))) )
{
res.flag = true;
res.Y1 = res.Y1 + (d.Y1 << 1);
res.Y2 = res.Y2 + (d.Y2 << 1);
return res;
}
}
}
}
}
else
{
if ( X.High_Bit() == n )
{
if ( X.Kth_Bit(n - 1) == X.Kth_Bit(0) )
{
res.Y1.maxbit = (n - 1) / bit + 1;
res.Y2.maxbit = (m - 1) / bit + 1;
res.Y1.Insert(n - 1, is_high);
res.Y1.Insert(0, is_high);
res.Y2.Insert(n - 1, (X.Kth_Bit(n - 1) - is_high + 10) % 10);
res.Y2.Insert(0, (X.Kth_Bit(n - 1) - is_high + 10) % 10);
Great_Int sum = res.Y1 + res.Y2;
if ( sum <= X )
{
Data d = Dfs((X - sum) >> 1, n - 2, m - 2, 0);
if ( d.flag && (!is_high || (res.Y1.Kth_Bit(n - 1) && res.Y2.Kth_Bit(m - 1))) )
{
res.flag = true;
res.Y1 = res.Y1 + (d.Y1 << 1);
res.Y2 = res.Y2 + (d.Y2 << 1);
return res;
}
}
}
if ( X.Kth_Bit(n - 1) == X.Kth_Bit(0) + 1 )
{
res.Y1.maxbit = (n - 1) / bit + 1;
res.Y2.maxbit = (m - 1) / bit + 1;
res.Y1.Insert(n - 1, is_high);
res.Y1.Insert(0, is_high);
res.Y2.Insert(n - 1, (X.Kth_Bit(0) - is_high + 10) % 10);
res.Y2.Insert(0, (X.Kth_Bit(0) - is_high + 10) % 10);
Great_Int sum = res.Y1 + res.Y2;
if ( sum <= X )
{
Data d = Dfs((X - sum) >> 1, n - 2, m - 2, 0);
if ( d.flag && (!is_high || (res.Y1.Kth_Bit(n - 1) && res.Y2.Kth_Bit(m - 1))) )
{
res.flag = true;
res.Y1 = res.Y1 + (d.Y1 << 1);
res.Y2 = res.Y2 + (d.Y2 << 1);
return res;
}
}
}
}
if ( X.High_Bit() == n + 1 )
{
if ( X.Kth_Bit(n - 1) == X.Kth_Bit(0) )
{
res.Y1.maxbit = (n - 1) / bit + 1;
res.Y2.maxbit = (m - 1) / bit + 1;
res.Y1.Insert(n - 1, X.Kth_Bit(n - 1) + 1);
res.Y1.Insert(0, X.Kth_Bit(n - 1) + 1);
res.Y2.Insert(n - 1, 9);
res.Y2.Insert(0, 9);
Great_Int sum = res.Y1 + res.Y2;
if ( sum <= X )
{
Data d = Dfs((X - sum) >> 1, n - 2, m - 2, 0);
if ( d.flag && (!is_high || (res.Y1.Kth_Bit(n - 1) && res.Y2.Kth_Bit(m - 1))) )
{
res.flag = true;
res.Y1 = res.Y1 + (d.Y1 << 1);
res.Y2 = res.Y2 + (d.Y2 << 1);
return res;
}
}
}
if ( X.Kth_Bit(n - 1) == X.Kth_Bit(0) + 1 )
{
res.Y1.maxbit = (n - 1) / bit + 1;
res.Y2.maxbit = (m - 1) / bit + 1;
res.Y1.Insert(n - 1, X.Kth_Bit(0) + 1);
res.Y1.Insert(0, X.Kth_Bit(0) + 1);
res.Y2.Insert(n - 1, 9);
res.Y2.Insert(0, 9);
Great_Int sum = res.Y1 + res.Y2;
if ( sum <= X )
{
Data d = Dfs((X - sum) >> 1, n - 2, m - 2, 0);
if ( d.flag && (!is_high || (res.Y1.Kth_Bit(n - 1) && res.Y2.Kth_Bit(m - 1))) )
{
res.flag = true;
res.Y1 = res.Y1 + (d.Y1 << 1);
res.Y2 = res.Y2 + (d.Y2 << 1);
return res;
}
}
}
}
}
return res;
}
Data Solve ( const Great_Int &X )
{
Data d; d.flag = false;
for ( int i = X.High_Bit(); i >= max(X.High_Bit() - 1, 1); i -- )
{
for ( int j = i; j >= 1; j -- )
{
d = Dfs(X, i, j, 1);
if ( !d.Y1.Check() || !d.Y2.Check() )
d.flag = false;
if ( d.flag )
break;
}
if ( d.flag )
break;
}
return d;
}
void Work ()
{
scanf("%s", s); n = strlen(s);
Great_Int X; X.maxbit = (n - 1) / bit + 1;
for ( int i = 0; i < n; i ++ )
X.Insert(i, s[n - i - 1] - '0');
if ( X.Check() )
{
printf("1\n");
X.Print();
printf("\n");
}
else
{
Data d = Solve(X);
if ( d.flag )
{
printf("2\n");
d.Y1.Print();
d.Y2.Print();
printf("\n");
}
else
{
for ( int i = 1, power = 1; ; i ++, power *= 10 )
{
for ( int k = power; k < power * 10; k ++ )
{
if ( Check(k, i) )
{
Great_Int Z = X - k;
d = Solve(Z);
if ( d.flag )
{
printf("3\n");
d.Y1.Print();
d.Y2.Print();
printf("%d\n", k);
return;
}
}
}
}
}
}
return;
}
int main ()
{
freopen("sum.in", "r", stdin);
freopen("sum.out", "w", stdout);
scanf("%d", &T);
while ( T -- )
Work();
return 0;
}