I have been trying to solve this problem, but I don’t know how should I approach this problem. I think this is a graph problem, then again I am not sure what algorithm should I use here. Can someone give me a hint or point me in the right direction which algorithm should I use?
One day in the year 3019, a high school student named Moreno is going to school as usual. The town he lives in can be represented as a straight line stretching from east to west. Moreno’s house is at coordinate 0, and his school is at S. There are N stores and M teleport stations between the house and the school. Counting from the westernmost point, the i th (1 ≤ i ≤ N) store is at coordinate ai, and the j th (1 ≤ j ≤ M) teleport station is at bj. He can move between any two teleport stations in zero seconds.
When he walks, it takes one second to walk one coordinate.
Moreno is leaving home at time 0, measured in seconds.
(Note that the unit of time is always ‘seconds’ in this problem.)
He has to get to school no later than the time T.
If he gets to school at time T + 1 or later, it will be treated as being late for school, and he will be kicked out of school.
However, he really likes taking side trips, so he wants to shop at as many stores as possible on the way to school.
He can only shop at a store if he is at the same coordinate as the store.
It takes one second to shop at each store.
Calculate the maximum number of stores P that Moreno can shop at without being late for school.
Also calculate the minimum time Q it will take for Moreno to get to school when he shops at P stores along the way.
The format of the standard input is as below:
N M S T
a1 a2 … aN
b1 b2 … bM
- 1 ≤ N ≤ 2000, Integer
- 2 ≤ M ≤ 2000, Integer
- 1 ≤ S ≤ 109, Integer
- 1 ≤ T ≤ 109, Integer
- 1 ≤ a1 < a2 < a3 < … < aN < S, Integer
- 1 ≤ b1 < b2 < b3 < … < bM < S, Integer
- b1 < a1 and aN < bM
- The maximum number of buildings (houses, schools, stores, teleport stations) on the same coordinate is 1.
- No inputs in which Moreno will be late for school no matter which way he moves are given.
The format of the standard output is as below:
- P: The maximum number of stores Moreno can shop at without being late for school.
- Q: The minimum time for Moreno to get to school when he shops at P stores along the way.
Input & Output samples
Sample Input 1
3 3 20 16
3 6 11
2 7 15
Sample Output 1
The best series of movements is as follows.
- Walk to the first store, shop there, then walk back to the first teleport station. (time: 5)
- Teleport to the second teleport station. (time: 5)
- Walk to the second store, shop there, then walk back to the second teleport station. (time: 8)
- Teleport to the third teleport station. (time: 8)
- Walk to the school. (time: 13)
If he shops at the third store, neither of the other two stores can be visited.
Sample Input 2
2 2 10 14
Sample Output 2
It is optimal for him to walk straight to the school, shopping at all the stores as he passes by.
Sample Input 3
7 2 10 2
2 3 4 5 6 7 8
Sample Output 3
There are many stores, but unfortunately he has no time to shop.