2014
04-04

Temperature

Many people like summer as summer has a lot of advantages, but on the other hand, sometimes summer is also boring. As a student, Tom has complained with summer for many days. Because when having lunch, Tom has a habit of drinking soup. But the temperature of the soup is too high, so Tom need wait for a long time to drink. One day, Tom bought a bowl of soup again, he measured the temperature of the environment is ua and the temperature of the soup is u0, after t1 minutes, he measured the soup again and the temperature is u1, but he did not want to measure the temperature all the time until he could drink it. Now Tom asks you for help. Could you help Tom calculate what the temperature of the soup is after t2 minutes and how long he need to wait for until the temperature of the soup becomes u2 according to the data which he had measured? You could assume that the temperature of the environment is invariable.

The first line of the input contains a single integer T (1 <= T <= 10), the number of test cases. Then T cases follow.
The first line of each case contains 5 integers, ua(0<ua<100), u0(ua<=u0<=100), u1(ua<=u1<=u0), t1(t1>0), n(1<=n<=10), indicating the temperature of the environment ua, the original temperature of the soup u0 and the later temperature of the soup u1 after t1 minutes, n indicates that there are n options in the following. Each line of the n lines contains two integers, p and s, p is the kind of the option and can only be 0 or 1. If p is 0, you should calculate the time Tom need to wait for until the temperature of the soup becomes s(ua<=s<=u0)(it is guaranteed that temperature s is reachable), or you should calculate the temperature of the soup after s(0<s<=100) minutes from original time t=0.

The first line of the input contains a single integer T (1 <= T <= 10), the number of test cases. Then T cases follow.
The first line of each case contains 5 integers, ua(0<ua<100), u0(ua<=u0<=100), u1(ua<=u1<=u0), t1(t1>0), n(1<=n<=10), indicating the temperature of the environment ua, the original temperature of the soup u0 and the later temperature of the soup u1 after t1 minutes, n indicates that there are n options in the following. Each line of the n lines contains two integers, p and s, p is the kind of the option and can only be 0 or 1. If p is 0, you should calculate the time Tom need to wait for until the temperature of the soup becomes s(ua<=s<=u0)(it is guaranteed that temperature s is reachable), or you should calculate the temperature of the soup after s(0<s<=100) minutes from original time t=0.

1
24 100 90 10 2
0 80
1 20

Case 1:
21.65
81.32
HintAccording to Newton’s law of cooling, in a certain temperature range, the rate of change of an object’s
temperature is proportional to the temperature difference of the object’s temperature and the environment temperature. 

1. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
O(n) = O(n-1) + O(n-2) + ….
O(n-1) = O(n-2) + O(n-3)+ …
O(n) – O(n-1) = O(n-1)
O(n) = 2O(n-1)

2. for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
dp = dp [j-1] + 1;
if(s1.charAt(i-1) == s3.charAt(i+j-1))
dp = dp[i-1] + 1;
if(s2.charAt(j-1) == s3.charAt(i+j-1))
dp = Math.max(dp [j - 1] + 1, dp );
}
}
这里的代码似乎有点问题？ dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

3. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

4. L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-1]）这个地方也也有笔误
应改为L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-2]）