Hello, guys,
Could you help me to improve my program? I already posted this question on several online judges, but nobody answered. So I hope to receive an answer from you. Sorry for posting this directly to the problemset (not to my blog) :)
I don't remember the exact problem statement. But the input is 10 positive integers and I think that my program is correct. I get TLE (time limit exceeded). It might be ineffective but I don't know why.
Here is my program:
Could you submit your correct program which solves the problem correctly and effectively?
The first line contains the number of test cases T (1 ≤ T ≤ 104).
In the first line of every test case there are 11 integers a0, a1, ..., a9 (1 ≤ ai ≤ 109) and x (0 ≤ x ≤ 2·109).
For each test case output one line containing “_Case #tc: answer_” where tc is the number of the test case (starting from 1) and answer is the result of myFunction(x).
## Input
The first line contains the number of test cases T (1 ≤ T ≤ 104). In the first line of every test case there are 11 integers a0, a1, ..., a9 (1 ≤ ai ≤ 109) and x (0 ≤ x ≤ 2·109).
## Output
For each test case output one line containing “_Case #tc: answer_” where tc is the number of the test case (starting from 1) and answer is the result of myFunction(x).
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ V, H \in \mathbb{Z} $ denote the number of vertical and horizontal streets, respectively.
- Let $ \mathbf{VG} = (vg_1, vg_2, \dots, vg_{V-1}) \in \mathbb{R}^{V-1} $ be the distances between consecutive vertical streets, where $ vg_i $ is the distance between vertical street $ i $ and $ i+1 $.
- Let $ \mathbf{HG} = (hg_1, hg_2, \dots, hg_{H-1}) \in \mathbb{R}^{H-1} $ be the distances between consecutive horizontal streets, where $ hg_j $ is the distance between horizontal street $ j $ and $ j+1 $.
- Let $ \mathbf{VD} = (vd_1, vd_2, \dots, vd_V) \in \{N, S\}^V $ be the direction of each vertical street: $ vd_i = N $ means Northbound, $ S $ means Southbound.
- Let $ \mathbf{HD} = (hd_1, hd_2, \dots, hd_H) \in \{W, E\}^H $ be the direction of each horizontal street: $ hd_j = E $ means Eastbound, $ W $ means Westbound.
Define the grid coordinates:
- Vertical street $ i $ lies at $ x = \sum_{k=1}^{i-1} vg_k $, for $ i \in \{1, \dots, V\} $.
- Horizontal street $ j $ lies at $ y = \sum_{k=1}^{j-1} hg_k $, for $ j \in \{1, \dots, H\} $.
Let $ K \in \mathbb{Z} $ be the number of queries.
For each query $ q \in \{1, \dots, K\} $, given source $ (x_1, y_1) $ and target $ (x_2, y_2) $, both lying at intersections of streets.
**Constraints**
1. $ 1 \le T \le 20 $
2. $ 1 \le V, H \le 10^5 $
3. $ 1 \le vg_i, hg_j \le 10^4 $
4. $ 1 \le K \le 10^5 $
5. $ (x_1, y_1), (x_2, y_2) $ lie on intersections of the grid (i.e., $ x_1, x_2 \in \{ \sum_{k=1}^{i-1} vg_k \mid i \in [V] \} $, $ y_1, y_2 \in \{ \sum_{k=1}^{j-1} hg_k \mid j \in [H] \} $)
**Objective**
For each query $ q $, compute the shortest path distance from $ (x_1, y_1) $ to $ (x_2, y_2) $, moving only along streets in their designated directions.
If no valid path exists, output $ -1 $.
**Path Rules**
- Movement along vertical street $ i $ is only allowed in direction $ vd_i $:
- If $ vd_i = N $, movement is allowed from lower $ y $ to higher $ y $.
- If $ vd_i = S $, movement is allowed from higher $ y $ to lower $ y $.
- Movement along horizontal street $ j $ is only allowed in direction $ hd_j $:
- If $ hd_j = E $, movement is allowed from lower $ x $ to higher $ x $.
- If $ hd_j = W $, movement is allowed from higher $ x $ to lower $ x $.
- Transitions between streets are allowed only at intersections.
- The path must follow street directions; reversing direction is forbidden.