#P18262. Frogs
Frogs
Frogs
在一片很长、很窄的池塘里,青蛙妈妈产下了 个卵,第 个卵位于位置 。青蛙按照 的顺序孵化。所有青蛙每次跳跃的长度均为 。
对于每个 ,独立考虑前 只青蛙玩追逐游戏的情况:第 只追第 只,最后一只(第 只)追第1只。第 至 只不参与游戏。
游戏开始时,这些青蛙分别位于各自的初始位置 。此后每秒,所有参与的青蛙同时朝自己追逐的那只青蛙跳跃 个单位:
- 如果目标青蛙在右边,或者两只青蛙位置相同,就向右跳;
- 否则向左跳。
形式化地,令第 只的下一只为第1只。每秒根据这一秒开始时的位置,同时执行
$$a_i\gets\begin{cases}a_i+k,&a_{i+1}\ge a_i,\\a_i-k,&a_{i+1}<a_i.\end{cases}$$青蛙妈妈担心孩子们离初始位置太远,最终跳出池塘。对于每个 ,判断:如果游戏一直进行下去,是否会有至少一只参与的青蛙,在某个时刻距离它自己的初始位置至少
个单位。如果会,答案为1,否则为0。不同 的游戏分别从初始位置开始,互不影响。
输入格式
第一行包含两个整数 。
第二行包含 个整数 。
输出格式
输出一个长度为 的01串,不含空格,依次表示 的答案。
数据范围
- ;
- ;
- ;
- 初始位置可以相同,输入只有一组数据。
样例
6 2
4 3 -3 5 100 100
01011
样例解释
当 时,两只青蛙最初位于4和3,每两秒回到原位置,所以答案为0。下图为原题给出的最初几秒:

当 时,初始位置为 ,答案为1。下图显示最初几秒,之后会持续向左漂移:

当 时,初始位置为 ,答案为0。原题过程图如下:
