#P18084. Split Sticks
Split Sticks
Split Sticks
题目描述
有 根木棍从左到右排列,第 根的长度为正整数 。一次操作依次执行:
- 选择一根木棍,将其切成长度均为整数的左、右两部分,允许其中一部分长度为 。
- 把左半部分合并到原木棍左边紧邻的木棍上;如果左边没有木棍,则左半部分独立成为一根木棍。
- 把右半部分合并到原木棍右边紧邻的木棍上;如果右边没有木棍,则右半部分独立成为一根木棍。
- 删除所有长度为 的木棍。
求使剩余木棍长度全部相等的最少操作次数。剩余木棍的数量可以改变。可以证明总存在可行操作序列。
输入格式
第一行一个整数 ,表示测试组数。每组第一行一个整数 ,第二行 个整数 。
,,;所有组的 之和不超过 。
输出格式
每组输出一行一个整数,表示最少操作次数。
样例输入
3
3
1 5 4
4
1 4 2 5
5
3 3 3 3 3
样例输出
1
2
0