Order Splitter

Electronic exchanges are complex, real-time order processing systems. Today, electronic exchanges operate on the market, handling millions of orders every day. You have set up a small company that provides execution services for clients, and you are facing the problem of splitting large orders between exchanges. Since setting up a new exchange is very competitive, there is only a limited number of exchanges available to split an order: 1 \leq N \leq 30.

An order has a notional value (the projected amount to be executed on the exchanges) 1 \leq L \leq 10^9 and a price. In this problem, you only care about the notional. The price at which an order is sent to an exchange is provided by the client and forwarded as is to the exchange. The given order has to be split into multiple child orders, which are sent to the exchanges according to the given ratios R_i, for each 0 \leq i < N. However, each exchange has restrictions on the step size: each child notional must be divisible by its exchange's step size S_i. Each exchange can accept only orders of notional S_i, 2 \cdot S_i, 3 \cdot S_i, \ldots.

Because it is not always possible to split the client order notional precisely into child orders, you must write an algorithm to achieve the best possible allocation that minimizes D = |L - \sum_i C_i|, where C_i are the child order notionals allocated to corresponding exchanges. Clients prefer that each child order size is as close as possible to CR_i = L \cdot R_i / \sum_j R_j. To satisfy this, C_i can only be obtained by rounding CR_i either up or down to the nearest step size S_i. However, if CR_i is divisible by S_i, you must set C_i = CR_i. If rounding down yields a notional of $0$, you may choose not to send any order to that exchange.