Below, we only consider the case there are more Rs than Ls. (The case there are more Ls than Rs can be reduced to this one by a horizontal flip. In the case there are equal numbers of Ls and Rs, it can be seen that the people only change direction at \(t=0.5\) from an argument similar to [1] and [2] below.)

Let us expand \(S\) to a length of \(NK\), and change \(S\) according to the people changing direction.

---

[1] The change at \(t=0.5\)

Let us consider the changes at \(t=0.5,\ 1.5,\ 2.5,\ \dots\) by using \(f_i=\) (The number of Rs in \(S_0,\ S_1,\ \dots,\ S_i\)) \(-\) (The number of Ls in \(S_0,\ S_1,\ \dots,\ S_i\)) (let \(f_{-1}=0\) for convenience). Then, the condition for person \(i\) to change direction can be described as follows.

• When \(S_i\)=L, person \(i\) changes direction if \(0\leq f_i\).
• When \(S_i\)=L, person \(i\) changes direction if \(f_{NK-1} < f_i\).

Particularly, if \(f_{NK-1} \leq \min(f_i,\ f_{i-1})\), person \(i\) always changes direction regardless of \(S_i\).

The figure below shows a graph whose horizontal axis represents \(i\) and whose vertical axis represents \(f_i\) when \(N=15,\ K=1,\ S=\)RRRLRLLLLRRRLLR. A red segment corresponds to a person changing direction with \(f_{NK-1} \leq \min(f_i,\ f_{i-1})\) and \(S_i=\)R, and a blue segment corresponds to a person changing direction with \(f_{NK-1} \leq \min(f_i,\ f_{i-1})\) and \(S_i=\)L.

As seen here, all parts of the graph at or above \(f_{NK-1}\) fold down by the change at \(t=0.5\) so that \(\displaystyle f_{NK-1}=\max_{0 \le i \le NK-1}f_i\) always hold after the change. (Some people with \(S_i\)=L, shown as yellow segments, change direction even if \(f_i < f_{NK-1}\), but these changes contribute only positively to the fact that \(f_{NK-1}\) is the maximum.)

---

[2] The changes at \(1 < t\)

Since \(f_{NK-1}\) becomes the maximum of \(f_i\) at \(t=0.5\), people with \(S_i=\)R do not change direction at \(t=1.5\). Thus, \(f_{NK-1}\) will still be the maximum after the change at \(t=1.5\). It can also be inductively seen that \(f_{NK-1}\) will continue to be the maximum and people with \(S_i=\)R do not change direction through the subsequent changes.

Thus, regarding the changes at \(1 < t\), it is enough to consider whether people with \(S_i=\)L eventually become \(S_i=\)R.

---

[3] Observation on the final \(S\)

Consider what \(S\) will look like eventually at \(1 < t\).

Let \(k\) be the smallest \(i\) such that \(0 < f_i\). First, \(f_i\) for \(i\) with \(i < k\) always satisfies \(f_i \leq 0\), so \(S_i\) does not change from the initial state.

Next, consider person \(i\) with \(k\leq i\). We begin by noting that \(S_k\) is always R.

If, to the right of person \(k\), there are \(n\) people \((1\leq n)\) facing left at some time, there will be at most \(n-1\) people facing left after the next change.

Proof

Let \(m\) be the smallest such \(i\). Consider \(f_{m}=f_{m-1}-1\). We have \(f_{m-1} \geq f_k=1\) from the minimality of \(m\), so \(0 \leq f_m\).

Thus, the condition stated in [1] is satisfied, so this person will definitely change direction and face right.

As stated in [2], people with \(S_i=\)R do not change direction, so there will be at most \(n-1\) people facing left after the change.

Therefore, to the right of person \(k\), the number of people facing left will be \(0\) at time \(t=O(NK)\). (A more accurate evaluation reveals that it will be \(0\) at \(t=O(\log N)\).)

---

[4] Summary

The observations above lead to the following conclusion.

• Person \(i\) with \(k \leq i\) satisfying \(f_{NK-1} < f_{i}\) and \(S_i=\)R at \(t=0\) will change direction twice: R \(\rightarrow\) L \(\rightarrow\) R.
• Person \(i\) with \(k \leq i\) satisfying \(S_i=\)L at \(t=0\) will change direction once: L \(\rightarrow\) R.
• The other people never change direction.

Now, it is enough to find \(k\) and count the numbers of people satisfying the first and second conditions. By using \(f_{i}=\lfloor \frac{i}{N}\rfloor f_{N-1} + f_{i \bmod N}\), they can be found in \(O(N)\) time.