All submissions for this problem are available.
Harappa has a thriving grain-trading market, but the traders have strong beliefs about the worth of grain and will not change the price they assign to the grain, no matter what the other traders are doing. Naturally, some people see opportunity here and decide to work as brokers—they buy grain from one trader and sell it to another, doing both transactions according to the respective traders’ prices.
The traders are also very secretive, and do not like to reveal their prices to outsiders. All that is known is that the prices (per kg) have to be integers from 1 to 1000. However, the brokers do have to reveal their profits to Tax-on-Food (TF) officials. TF manager Divyam is curious about the workings of the Harappan market and wonders how many possible assignments of prices exist. After each broker tells him the profit he made (this being prehistoric times, the brokers are all male), the trader he bought from and the trader he sold to, Divyam calculates the number of possible assignments modulo 1000000007.
The first line contains two integers N (the number of traders) and M (the number of broker reports). The next M lines contain 3 integers t1, t2, p. t1 and t2 are the indices (0-indexed) of the traders who the broker bought from and sold to, respectively. p is the profit the broker made.
Output M lines (one after receiving each new broker report), denoting the number of possible assignments modulo 1000000007.
1 <= N <= 100000
1 <= M <= 100000
0 <= p <= 999
0 1 700
2 1 100
0 2 450
Initially, we don’t know anything about the three traders’ prices other than that they lie between 1 and 1000. So there are 1000*1000*1000 = 1000000000 possible values their prices can take.
Now one broker comes up and says he bought from trader 0 and sold to trader 1, making a profit of 700 units per kg. So now, trader 0’s price can only be something from 1-300 units, and trader 1’s will be 700 more than his price. Trader 2’s price can still be anything from 1-1000. So, there are 300*1000 = 300000 possible values.
Now, another broker comes up to him and says he made a transaction from trader 2 to 1, making a profit of 100 units per kg. So, again, trader 0’s price can be anything from 1-300, trader 1’s will be 700 more than 0’s, and 2’s will be 600 more than 0’s (as it is 100 less than 1’s). So, number of possible assignments is 300.
Now, yet another broker comes up and says he bought from trader 0 and sold to three at a profit of 450 per kg. But this is inconsistent with the data so far, according to which buying from trader 0 and selling to 2 should have yielded a profit of 600 units. So, there are no possible (0) assignments.
|Time Limit:||1 - 2.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, PYTH 3.5|
Fetching successful submissions
If you are still having problems, see a sample solution here.