{"raw_statement":[{"iden":"statement","content":"Hello, guys,\n\nCould 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) :)\n\nI 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.\n\nHere is my program: \n\nCould you submit your correct program which solves the problem correctly and effectively?\n\nThe first line contains the number of test cases T (1 ≤ T ≤ 104). \n\nIn the first line of every test case there are 11 integers a0, a1, ..., a9 (1 ≤ ai ≤ 109) and x (0 ≤ x ≤ 2·109).\n\nFor 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).\n\n"},{"iden":"input","content":"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)."},{"iden":"output","content":"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)."},{"iden":"examples","content":"Input21 2 3 4 5 6 7 8 9 10 101 2 3 4 5 6 7 8 9 9 9OutputCase #1: 853943371Case #2: 9"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ V, H \\in \\mathbb{Z} $ denote the number of vertical and horizontal streets, respectively.  \n- 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 $.  \n- 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 $.  \n- 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.  \n- 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.  \n\nDefine the grid coordinates:  \n- Vertical street $ i $ lies at $ x = \\sum_{k=1}^{i-1} vg_k $, for $ i \\in \\{1, \\dots, V\\} $.  \n- Horizontal street $ j $ lies at $ y = \\sum_{k=1}^{j-1} hg_k $, for $ j \\in \\{1, \\dots, H\\} $.  \n\nLet $ K \\in \\mathbb{Z} $ be the number of queries.  \nFor 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.\n\n**Constraints**  \n1. $ 1 \\le T \\le 20 $  \n2. $ 1 \\le V, H \\le 10^5 $  \n3. $ 1 \\le vg_i, hg_j \\le 10^4 $  \n4. $ 1 \\le K \\le 10^5 $  \n5. $ (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] \\} $)\n\n**Objective**  \nFor 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.  \nIf no valid path exists, output $ -1 $.  \n\n**Path Rules**  \n- Movement along vertical street $ i $ is only allowed in direction $ vd_i $:  \n  - If $ vd_i = N $, movement is allowed from lower $ y $ to higher $ y $.  \n  - If $ vd_i = S $, movement is allowed from higher $ y $ to lower $ y $.  \n- Movement along horizontal street $ j $ is only allowed in direction $ hd_j $:  \n  - If $ hd_j = E $, movement is allowed from lower $ x $ to higher $ x $.  \n  - If $ hd_j = W $, movement is allowed from higher $ x $ to lower $ x $.  \n- Transitions between streets are allowed only at intersections.  \n- The path must follow street directions; reversing direction is forbidden.","simple_statement":"You're in a grid city with vertical and horizontal one-way streets.  \nVertical streets (left to right) go either North (N) or South (S).  \nHorizontal streets (bottom to top) go either East (E) or West (W).  \nYou’re given starting point (x1, y1) and target (x2, y2).  \nFind the shortest path distance, or -1 if impossible.","has_page_source":false}