{"problem":{"name":"I. Teleportia","description":{"content":"You have moved to a city called teleportia and you are looking for a job.  This city has a network of streets such that every two streets are either parallel or perpendicular and the distance between","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":65536},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10088I"},"statements":[{"statement_type":"Markdown","content":"You have moved to a city called teleportia and you are looking for a job. \n\nThis city has a network of streets such that every two streets are either parallel or perpendicular and the distance between every two consecutive parallel streets is 1 meter. So you can consider the network of streets as an infinite 2D grid. The scientists in this city invented an advanced teleportation system , it consists of a set of teleportation stations, each station is located on an intersection of two streets the teleportation stations work as follows : \n\nEach teleportation station Si has a power Pi. We define targets of a teleportation station A with power PA as : all the teleportation stations which are inside or on the border of a circle centered at A with a radius of PA. \n\nOnce you enter a teleportation station you'll have to wait for 2 seconds until you are teleported to one of its target teleportation stations. \n\nThe government is planning to develop a system that finds the minimum time required to go from a starting point Xs, Ys to an ending point Xe, Ye considering an average person walks with a speed of 1 meter per second. since you are a programmer who is looking for a job , can you implement this system ? \n\n The input starts with T the number of test Cases. \n\nEach test case starts with a number n (0 ≤ n ≤ 100), the number of teleportation stations. \n\nThen n lines follow each describing a teleportation station Si. A teleportation station description consists of three integers Xi, Yi, Pi : the 2D coordinates of the teleportation station , and its power. The next line contains four integers: Xs, Ys, Xe, Ye : the 2d coordinates of a starting point and an ending point. \n\n - 109 ≤ Xi, Yi, Xs, Ys, Xe, Ye ≤ 109 \n\n0 ≤ Pi ≤ 109\n\nfor each test case you have to print the minimum time required to move from the starting point to the ending point \n\n## Input\n\n The input starts with T the number of test Cases. Each test case starts with a number n (0 ≤ n ≤ 100), the number of teleportation stations. Then n lines follow each describing a teleportation station Si. A teleportation station description consists of three integers Xi, Yi, Pi : the 2D coordinates of the teleportation station , and its power. The next line contains four integers: Xs, Ys, Xe, Ye : the 2d coordinates of a starting point and an ending point.  - 109 ≤ Xi, Yi, Xs, Ys, Xe, Ye ≤ 109 0 ≤ Pi ≤ 109\n\n## Output\n\nfor each test case you have to print the minimum time required to move from the starting point to the ending point \n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $, let $ s_k \\in \\Sigma^* $ be a string of length $ n_k $, where $ \\Sigma = \\{a, b, \\dots, z\\} $, and $ 1 \\leq n_k \\leq 10^5 $.\n\n**Constraints**  \n1. $ 1 \\leq T \\leq 5 $  \n2. For each $ k $, $ 1 \\leq n_k \\leq 10^5 $, and all characters in $ s_k $ are lowercase English letters.\n\n**Objective**  \nFor each string $ s_k $, define the set of operations:  \n- For each position $ i \\in \\{1, \\dots, n_k\\} $, and for each character $ c \\in \\Sigma $, let $ s_k^{(i,c)} $ denote the string obtained by replacing the character at position $ i $ with $ c $.  \n\nLet $ P(s) $ denote the number of distinct palindromic substrings in string $ s $.  \n\nFind:  \n1. $ M_k = \\max_{i \\in [n_k], c \\in \\Sigma} P(s_k^{(i,c)}) $  \n2. $ C_k = \\left| \\left\\{ (i, c) \\in [n_k] \\times \\Sigma \\mid P(s_k^{(i,c)}) = M_k \\right\\} \\right| $  \n\nOutput $ (M_k, C_k) $ for each test case $ k $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10088I","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}