Indian Computing Olympiad

Heaps→Race (CEOI 2003)

250,000 rockets racing in parallel tracks across space. Each rocket i has a starting position x_i and a constant velocity v_i (bounded by 100) with which it will move. Assume that the rockets are enumerated in order of their starting position.

Thus, initially the rockets are lined up as:

       -----x--------------------------------------------------------->
          (x1,v1)

       ---------x----------------------------------------------------->
              (x2,v2)

       ----------------x---------------------------------------------->
                    (x3,v3)

       ....

       ---------------------------x------------------------------------>
                         (x250000,v250000)

      

Constraints

• At any given time, no more two rockets are at the same position. This implies that all overtakings take place at distinct times.
• The race goes on forever. Eventually, faster rockets overtake slower rockets and beyond a point the rockets will become ordered in the order of their velocities.

Problems

1. Compute the number of overtakings (modulo 1000000, say) in the eventual race.
2. Print out the first 10,000 overtakings (in order).

Solution

---