#P18861. [Croatian CPC2025] Izgubljeni Input
[Croatian CPC2025] Izgubljeni Input
Izgubljeni Input
题目描述
原来的题目如下:每个场景开始时有一个空序列,依次执行 次操作。操作有两种:
1 X:向序列末尾加入非负整数 ,输出操作后整个序列的平均值。2 A B:向序列末尾加入某个整数(可以为负),使操作后整个序列的平均值为 ,输出刚加入的整数。
原题中 ,,,且 互质。第二种操作保证可以加入一个整数来满足要求。
两类操作的答案都以最简分数输出:分子和分母之间用空格分隔,分母为正数。如果答案为整数 ,则输出 Y 1。
现在原来的输入文件丢失了,只剩下输出文件,以及每个场景的操作次数。你需要根据这些信息,重建任意一份能够产生给定输出的合法输入。
为了方便重建,你输出的操作中, 和 的上限放宽为 ,其余要求不变。
输入格式
第一行包含整数 ,表示场景数。
每个场景的第一行包含整数 。
接下来 行,每行包含两个整数 ,表示原题第 次操作输出的最简分数。你不知道该答案由哪一种操作产生。由题目定义可知 。
给出的答案来自原题的一份合法输入。
输出格式
输出一份重建后的输入文件:
第一行输出 。
对于每个场景,先输出 ,然后输出 行操作,每行是以下两种形式之一:
1 X,其中 是整数且 。2 A B,其中 是整数,,,且 互质。执行该操作时,必须能够加入一个整数使平均值变为 。
重建的操作产生的每个答案必须与输入给出的对应答案相同。如果有多种方案,输出任意一种。
数据范围
- ,。
- 所有场景的 之和不超过 。
样例 1
输入
3
5
5 1
4 1
2 1
17 4
3 1
3
6 1
4 1
-9 1
3
6 1
4 1
10 3
输出
3
5
2 5 1
1 3
2 10 3
1 7
2 4 1
3
1 6
2 5 1
2 1 3
3
1 6
1 2
1 2