Subtask solution

Let ~D~ equal ~\lfloor X \bmod \sum a \rfloor~.

If you focus on one color at a time, it is clearly optimal to place buses and stations in contiguous blocks with an offset. We can show that the number of visits for the ~i^\text{th}~ color is equal to ~\sum_{j=1}^D \max(0, 2a_i-\sum a, a_i-|n-j|)~, where ~n~ is the selected offset. This implies that an offset of ~\lfloor D/2 \rfloor~ works regardless of ~a_i~.

We can calculate the number of visits by simulating the buses' movement for the last ~D~ steps (evaluating the described sum), and then adding ~\lfloor X/\sum a_i \rfloor \times \sum a_i^2~ to account for the full rotations.

Time Complexity: ~\mathcal{O}(N+\sum a) = \mathcal{O}(\sum a)~

Note that this subtask is designed to allow ~\mathcal{O}((\sum a)^2)~ solutions to pass. This rewards people who make the observation about blocks, but simulate the buses' movement inefficiently.

Full solution

The only difference between the full solution and the subtask is how we calculate the number of visits. Instead of evaluating the sum iteratively, we break it into two arithmetic sums. The derivation is long, and left as an exercise to the reader.

Time Complexity: ~\mathcal{O}(N)~