На числовой прямой расположено \(n\) роботов, \(i\)-й из них изначально занимает единичный отрезок \([x_i, x_i + 1]\). У каждого робота есть программа из \(k\) команд, которые он выполняет по циклу. Команды пронумерованы от \(1\) до \(k\). Каждая команда описывается одним целым числом. Обозначим число, соответствующее \(j\)-й команде \(i\)-го робота, за \(f_{i, j}\).
Изначальное положение роботов соответствует моменту времени \(0\). В течение одной секунды с момента времени \(t\) (\(0 \le t\)) до момента \(t + 1\) происходит следующий процесс:
- Каждый робот выполняет \((t \bmod k + 1)\)-ю команду из своего списка команд. Робот номер \(i\) берет число \(F = f_{i, (t \bmod k + 1)}\). Если это число отрицательное, робот пытается ехать влево с силой \(|F|\), если положительное — пытается ехать вправо с силой \(F\), иначе не делает ничего.
- Мысленно разобьем роботов на группы подряд идущих следующим алгоритмом:
- Изначально каждый робот принадлежит своей собственной группе.
- Просуммируем числа, соответствующие командам роботов, принадлежащих одной группе. Обратите внимание, что суммируются исходные числа, без взятия по модулю. Пусть сумма равна \(S\). Скажем, что вся группа двигается вместе, и делает это с силой \(S\), по тем же правилам, что и один робот. То есть, если \(S\) отрицательно, пытается ехать влево с силой \(|S|\), если \(S\) положительно — вправо с силой \(S\), иначе — не делает ничего.
- Если группа пытается двигаться в каком-то направлении, и в направлении движения касается другой группы, объединим их. Группа касается другой группы, если крайние роботы групп занимают соседние единичные отрезки.
- Продолжать процесс, пока группы не перестанут объединяться.
- Каждый робот перемещается на \(1\) в направлении движения его группы, либо остается на месте, если группа не двигается. Но есть одно исключение.
- Исключение — если есть две группы роботов, разделенные ровно одним единичным отрезком, такие, что левая группа пытается двигаться вправо, а правая группа пытается двигаться влево. Обозначим сумму в левой группе за \(S_l\), а в правой — за \(S_r\). Если \(|S_l| \le |S_r|\), перемещается только правая группа, иначе перемещается только левая группа.
- Обратите внимание, что роботы из одной группы не склеиваются друг с другом — в будущем они могут разъехаться. Разбиение на группы мысленное, и нужно только для того, чтобы понять, как роботы переместятся в течение одной секунды \([t, t + 1]\).
Иллюстрация процесса, происходящего в течение одной секунды:
Прямоугольники обозначают роботов, числа в прямоугольниках соответствуют командам роботов. Дугами выделено итоговое разбиение на группы. Снизу нарисованы позиции роботов после перемещения. Из двух самых правых групп переместилась только левая, потому что эти две группы пытались двигаться навстречу друг другу и были разделены ровно одним единичным отрезком.
Смотрите примеры для лучшего понимания процесса.
Вам требуется ответить на несколько вопросов: где находится \(a_i\)-й робот в момент времени \(t_i\).