#P18428. Alea Iacta Est
Alea Iacta Est
Alea Iacta Est
SSerxhs 有两枚骰子,分别有 个面和 个面,面上的数字分别为 和 。他对同时掷这两枚骰子所得数字之和的概率分布很感兴趣。请找到另一对与原来不同的骰子,使它们所得数字之和服从相同的概率分布。
由于面数很多的骰子难以制作,你需要使新骰子的面数之和最小。假设每枚骰子的各个面出现的概率相等。
当且仅当存在一个数字 ,它在两枚骰子的面上出现的次数不同,称这两枚骰子不同。当且仅当一对骰子中存在一枚骰子,与另一对中的任意一枚都不同,称这两对骰子不同。也就是说,骰子按面上数字的多重集合比较,一对骰子不区分先后顺序。
当且仅当对所有整数 都有 ,两个随机变量 服从相同的概率分布。
输入格式
第一行包含整数 (),表示测试用例数。
每个测试用例仅一行,包含两个整数 (),表示原来的两枚骰子的面数。
保证全部测试用例的 之和不超过 。
输出格式
每个测试用例输出两行,分别描述两枚新骰子。第 行的第一个整数 表示对应骰子的面数,随后输出 个整数 (),表示各面上的数字。允许不同面上的数字相同。
输出的骰子对必须不同于原来的骰子对,和的概率分布相同,并且面数和最小。有多种最优方案时可以输出任意一种。
特别地,若不存在解,则两行分别输出一个 0。原题还规定,所有测试用例输出的 之和不超过 。
原样例在不同测试用例之间增加了空行以便阅读;输出中是否包含这些空行均可。
原样例
3
2 8
1 9
2 9
4 1 2 3 4
4 1 2 5 6
3 1 2 3
3 1 4 7
6 1 2 4 5 7 8
3 1 2 3