题目描述
有一个长度为 n 的整数数列 f,现在可以进行无限次操作,每次操作的要求如下:
选择一个长度不大于 k 的区间 [l,r],将这个区间中的每一个数减去 m。在减去 m 后的数列中,记:
-
a=max{fl,fl+1,⋯,fr};
-
b=min{fl,fl+1,⋯,fr};
这时候将区间 [l,r] 内的每一个数都加上 ∣a∣⊕∣b∣,其中 ⊕ 为按位异或(xor,即 C/C++ 的 ˆ
或 Pascal 的 xor
,如果您不知道什么是异或您可以查看这里)。请你求出最少进行多少次操作后,这个数列中最小的数小于等于 s。如果无论怎样操作也没有办法使这个数列中的最小的数小于等于 s,请输出 Impossible!
。
输入格式
输入包含多组测试数据。
第一行一个整数 T,表示数据组数。
接下来有 2×T 行,对于第 i 组数据:第 2×i 行四个整数 n,m,k,s。第 2×i+1 行有 n 个整数 fi(1≤i≤n),表示这个数列。
输出格式
共 T 行,对于每组数据,如果可以达到目标请输出最少需要的操作次数,否则输出 Impossible!
。
输入输出样例
3
4 4 4 9
6 7 6 7
4 2 3 7
8 9 8 9
4 0 2 5
7 8 7 8
0
1
Impossible!
说明/提示
子任务测试采用捆绑方式计分。
样例解释
对于输入 #1 中的第一组数据,
- 由于 6≤s,故不需要进行任何一次操作,输出
0
。
对于输入 #1 中的第二组数据,
- 可以选择区间 [1,3]。注意,选择区间 [1,4] 是不合法的,因为区间长度 4>k。
- 先将区间中的每一个数减去 m,[8,9,8,9]→[6,7,6,9]。
- 计算得此时 a=7,b=6,7⊕6=1。
- 这时候将区间内的每一个数都加上 1,[6,7,6,9]→[7,8,7,9]。
- 由于 7≤s,故只需要进行一次操作,输出
1
。
对于输入 #1 中的第三组数据,
- 无论进行多少次操作,都无法使最小值小于等于 s,故输出
Impossible!
。
数据范围
- Subtask 1(5 pts):即样例。
- Subtask 2(10 pts):m=0。
- Subtask 3(25 pts):1≤n≤100。
- Subtask 4(60 pts):无特殊限制。
对于 100% 的数据,1≤T≤103,1≤k≤n≤103,0≤m≤106,−106≤fi,s≤106。