{"problem":{"name":"E. Equality Control","description":{"content":"In programming contest circles, one of the most important roles is that of the Chief Equality Officer (CEO). This person is responsible for making sure that every team has an equal chance of winning t","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10248E"},"statements":[{"statement_type":"Markdown","content":"In programming contest circles, one of the most important roles is that of the Chief Equality Officer (CEO). This person is responsible for making sure that every team has an equal chance of winning the contest. Since last year's NWERC the current CEO, Gregor, has thought at length about how to make the contest even more fair and equal.\n\nHis answer is to introduce a new programming language as the only one allowed for submissions. This way, no team will be disadvantaged by not having mastered any of the allowed languages. This language is called #cf_span(class=[tex-font-style-sc], body=[Balloon]), short for Building A Long List Of Ordinary Numbers. Its only data type is the list of integers. To keep the language fast, it contains only four instructions: \n\nNaturally, we cannot use byte-by-byte output comparison any more when teams submit their solutions in #cf_span(class=[tex-font-style-sc], body=[Balloon]), as its output is probabilistic. The judge server instead has to check whether a submitted program is equivalent to the sample solution created by the judges. Two programs are equivalent if for any list $L$ of integers, both programs have an equal probability of returning $L$.\n\nIt is your task to determine whether two given #cf_span(class=[tex-font-style-sc], body=[Balloon]) programs are equivalent.\n\nThe input consists of: \n\nEach integer in each program is greater than $0$ and less than $10^9$.\n\nIf the two programs are equivalent, output \"_equal_\", otherwise output \"_not equal_\".\n\n## Input\n\nThe input consists of:   One line containing a string _A_, the first program.  One line containing a string _B_, the second program.  Each program is a syntactically valid #cf_span(class=[tex-font-style-sc], body=[Balloon]) program with between $3$ and $10^6$ characters, and contains neither spacing nor empty lists (i.e., the strings \"_ _\" or \"_[]_\" do not occur in the input).Each integer in each program is greater than $0$ and less than $10^9$.\n\n## Output\n\nIf the two programs are equivalent, output \"_equal_\", otherwise output \"_not equal_\".\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ d_x, d_y \\in \\mathbb{Z}^+ $ be the grid dimensions.  \nLet $ w \\in \\mathbb{R}^+ $ be the width of each building block (in meters).  \nLet $ v \\in \\mathbb{R}^+ $ be Robin’s constant takeoff speed (in m/s).  \nLet $ g = 9.80665 \\, \\text{m/s}^2 $ be gravitational acceleration.  \nLet $ (l_x, l_y) \\in \\{1, \\dots, d_x\\} \\times \\{1, \\dots, d_y\\} $ be the coordinates of the secret hideout.  \n\nLet $ H = (h_{i,j}) \\in \\mathbb{R}^{d_x \\times d_y}_{\\geq 0} $ be the height matrix, where $ h_{i,j} $ is the height of the building at grid position $ (i,j) $.  \n\nThe center of the roof of building $ (i,j) $ is at position:  \n$$\n(x_{i,j}, y_{i,j}, z_{i,j}) = \\left( (i - 0.5)w, (j - 0.5)w, h_{i,j} \\right)\n$$\n\n**Constraints**  \n1. $ 1 \\leq d_x, d_y \\leq 20 $  \n2. $ 1 \\leq w \\leq 10^3 $  \n3. $ 1 \\leq v \\leq 10^3 $  \n4. $ 1 \\leq l_x \\leq d_x, \\, 1 \\leq l_y \\leq d_y $  \n5. $ 0 \\leq h_{i,j} \\leq 10^3 $ for all $ i,j $  \n\n**Jump Physics**  \nA jump from $ P_1 = (x_1, y_1, z_1) $ to $ P_2 = (x_2, y_2, z_2) $ has:  \n- Horizontal displacement: $ \\Delta x = x_2 - x_1 $, $ \\Delta y = y_2 - y_1 $  \n- Horizontal speed: $ v_d = \\sqrt{v^2 - v_h^2} $, with $ v_h > 0 $  \n- Flight time: $ t = \\frac{\\sqrt{(\\Delta x)^2 + (\\Delta y)^2}}{v_d} $  \n- Vertical motion: $ z(t) = z_1 + v_h t - \\frac{1}{2} g t^2 $  \n\nThe trajectory must satisfy $ z(t) \\geq h_{i,j} $ for all buildings $ (i,j) $ whose roof centers lie within the projection of the jump path (i.e., in the axis-aligned bounding box of the jump), **and** if the jump passes over a grid point where four buildings meet, then $ z(t) $ must exceed the maximum of the four adjacent building heights at that point.\n\n**Objective**  \nCompute the minimum number of jumps required to reach each building roof $ (i,j) $ from the hideout $ (l_x, l_y) $, using only valid jumps (no collisions).  \n\nLet $ D[i][j] \\in \\mathbb{Z}_{\\geq 0} \\cup \\{\\infty\\} $ be the minimum number of jumps to reach $ (i,j) $.  \nInitialize:  \n- $ D[l_x][l_y] = 0 $  \n- $ D[i][j] = \\infty $ for all $ (i,j) \\neq (l_x, l_y) $  \n\nFor every pair of building centers $ (i_1, j_1), (i_2, j_2) $, determine if a direct jump from $ (i_1, j_1) $ to $ (i_2, j_2) $ is physically possible under the constraints above.  \n\nUse BFS over the grid graph where an edge exists between $ (i_1, j_1) $ and $ (i_2, j_2) $ iff a valid jump connects them.  \n\nOutput:  \nFor each $ j = 1 $ to $ d_y $, and for each $ i = 1 $ to $ d_x $:  \n- Print $ D[i][j] $ if finite, otherwise print \"X\".","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10248E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}