Recently i am solving a problem.But there is constraint like this:
the question is:
Earth is now infested by Predators. These predators are of Insect species. These insects are trying to overcome human beings on earth. However since they are very small in size, they are failing to overpower humans. But now, one kind of insect is getting bigger in size in a very strange way.
Initially there are 2 categories of insects. In first category each insect has size ‘x’ and second ‘y’.
Initially there are infinite numbers of insect of each category.
An insect with size ‘s’ can eat any other insect of size less than ‘s’ in one minute. After eating, it’s size will increase and it will mutate into an insect of another category of another size. E.g. If there is an insect of size ‘s’ and it eats an insect of size ‘w’, where w < s. Then the new category insect will be of size s+w.
Irrespective of its category, any bigger sized insect can eat at most 1 other insect of smaller size, in 1 minute.
But there is one exception. Categories of insect with largest size can eat at most 2 insect in 1 minute. As noted previously, all others can eat only 1 insect in that minute.
Refer example for more details.
Humans are ready for the war. But they need just one help from you. They need to know the maximum size the insect can grow to, within t minutes.
First line contains total number of test cases, denoted by N
Next N lines, contain a tuple <x, y, t> containing 3 values delimited by space, where
x denotes the size of each insect in first category.
y denotes the size of each insect in second category.
t denotes the time in minutes.
For each test case print one integer which denotes the maximum size of the insect after t minutes. As this number can be very large, print its remainder after dividing it by 1000000007.
1<= x < y <= 10000000 (10 million)
2*x <= y
1<= t <= 1000000000000 (1 trillion)
where t is time in minute.I have to do a calculation for every minute .I have submittesd my solution but getting time limit exceed.Can any one suggest how to achieve such a large constraint.Thanks