seuOJ217 - 经典的传统题

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：夏季, 校赛, 2019

题目描述

根据套路，每年的东南大学的“华为杯”校赛都要出一个所需算法相同的题目，今年的夏季赛也不例外。4qwerty7 为此胡编了这样一道题：

NPM 曾经出现了这样一件事：一个开发者为表达对 NPM 的不满，unpublish 了一系列由他发行的包，其中包含一个 left-pad 包，这导致了诸多程序无法被正常运行。

left-pad 包中仅有一个函数，给出一个字符串 $s$，一个字符 $c$（严格的讲，它是长度为一的字符串），与一个长度 $l$，当 $l$ 不超过 $s$ 的长度（下文记作 $|s|$）时该函数返回 $s$ 本身；否则，返回由 $l-|s|$ 个字符 $c$ 与 $s$ 拼接而成的字符串。

当时它的代码是这样的：

function leftpad (str, len, ch) {
  str = String(str);

  var i = -1;

  if (!ch && ch !== 0) ch = " ";

  len = len - str.length;

  while (++i < len) {
    str = ch + str;
  }

  return str;
}

这并不高效，请给出一个足够高效的算法，使得字符串拼接操作不超过 $51$ 次。

输入格式

输入数据第一行一个整数 $T(1\leq T\leq 12)$，表示测试数据组数，接下来是各组测试数据的具体内容。

对于每组测试数据，给出一行两个整数 $|s|,\ l(0\leq |s|,\ l\leq 10^8)$，含义如题目描述中所示。

输出格式

我们提供 $M_i(i=0,1,2,\ldots,51)$ 可以存储字符串。

我们保证所有拼接操作开始前 $M_1=c,M_2=s,M_i=$""$(i\neq 1,2)$。

对于每组测试数据，输出第一行两个整数 $n,\ m$，表示你需要进行的字符串拼接次数以及最终结果存放在 $M_m$ 中。

接下来 $n$ 行每行请给出三个整数 $a,\ b,\ c$，表示将 $M_b$ 与 $M_c$ 的拼接结果放入 $M_a$，即 $M_a\leftarrow M_b+M_c$。

你的答案需要对任意满足输入中给出条件的 leftpad 函数调用参数都正确。

答案可能不唯一，输出任意一种即可。

样例

样例输入

1
5 7

样例输出

2 4
3 1 2
4 1 3