{"problem":{"name":"B. Mice","description":{"content":"Modern researches has shown that a flock of hungry mice searching for a piece of cheese acts as follows: if there are several pieces of cheese then each mouse chooses the closest one. After that all m","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF76B"},"statements":[{"statement_type":"Markdown","content":"Modern researches has shown that a flock of hungry mice searching for a piece of cheese acts as follows: if there are several pieces of cheese then each mouse chooses the closest one. After that all mice start moving towards the chosen piece of cheese. When a mouse or several mice achieve the destination point and there is still a piece of cheese in it, they eat it and become well-fed. Each mice that reaches this point after that remains hungry. Moving speeds of all mice are equal.\n\nIf there are several ways to choose closest pieces then mice will choose it in a way that would minimize the number of hungry mice. To check this theory scientists decided to conduct an experiment. They located _N_ mice and _M_ pieces of cheese on a cartesian plane where all mice are located on the line _y_ = _Y_0 and all pieces of cheese — on another line _y_ = _Y_1. To check the results of the experiment the scientists need a program which simulates the behavior of a flock of hungry mice.\n\nWrite a program that computes the minimal number of mice which will remain hungry, i.e. without cheese.\n\n## Input\n\nThe first line of the input contains four integer numbers _N_ (1 ≤ _N_ ≤ 105), _M_ (0 ≤ _M_ ≤ 105), _Y_0 (0 ≤ _Y_0 ≤ 107), _Y_1 (0 ≤ _Y_1 ≤ 107, _Y_0 ≠ _Y_1). The second line contains a strictly increasing sequence of _N_ numbers — _x_ coordinates of mice. Third line contains a strictly increasing sequence of _M_ numbers — _x_ coordinates of cheese. All coordinates are integers and do not exceed 107 by absolute value.\n\n## Output\n\nThe only line of output should contain one number — the minimal number of mice which will remain without cheese.\n\n[samples]\n\n## Note\n\nAll the three mice will choose the first piece of cheese. Second and third mice will eat this piece. The first one will remain hungry, because it was running towards the same piece, but it was late. The second piece of cheese will remain uneaten.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"现代研究显示，一群饥饿的老鼠在寻找奶酪时的行为如下：如果有多个奶酪块，则每只老鼠会选择距离最近的一个。之后，所有老鼠开始向所选的奶酪块移动。当一只或若干只老鼠到达目标点且该奶酪块仍存在时，它们会吃掉它并变得饱足。此后到达该点的任何老鼠都会保持饥饿。所有老鼠的移动速度相同。\n\n如果存在多个最近的奶酪块选择方式，则老鼠会选择一种能最小化饥饿老鼠数量的方式。为了验证这一理论，科学家们决定进行一项实验。他们在笛卡尔平面上放置了 #cf_span[N] 只老鼠和 #cf_span[M] 块奶酪，所有老鼠位于直线 #cf_span[y = Y0] 上，所有奶酪位于另一条直线 #cf_span[y = Y1] 上。为了检查实验结果，科学家们需要一个程序来模拟这群饥饿老鼠的行为。\n\n请编写一个程序，计算最终保持饥饿（即没有吃到奶酪）的老鼠的最小数量。\n\n输入的第一行包含四个整数：#cf_span[N]（#cf_span[1 ≤ N ≤ 10^5]）、#cf_span[M]（#cf_span[0 ≤ M ≤ 10^5]）、#cf_span[Y0]（#cf_span[0 ≤ Y0 ≤ 10^7]）、#cf_span[Y1]（#cf_span[0 ≤ Y1 ≤ 10^7]，且 #cf_span[Y0 ≠ Y1]）。第二行包含一个严格递增的 #cf_span[N] 个数字序列——老鼠的 #cf_span[x] 坐标。第三行包含一个严格递增的 #cf_span[M] 个数字序列——奶酪的 #cf_span[x] 坐标。所有坐标均为整数，绝对值不超过 #cf_span[10^7]。\n\n输出仅一行，包含一个数字——保持饥饿的老鼠的最小数量。\n\n所有三只老鼠都会选择第一块奶酪。第二只和第三只老鼠会吃掉这块奶酪。第一只老鼠会保持饥饿，因为它也朝同一块奶酪奔跑，但到达得太晚。第二块奶酪将保持未被食用。\n\n## Input\n\n输入的第一行包含四个整数：#cf_span[N]（#cf_span[1 ≤ N ≤ 10^5]）、#cf_span[M]（#cf_span[0 ≤ M ≤ 10^5]）、#cf_span[Y0]（#cf_span[0 ≤ Y0 ≤ 10^7]）、#cf_span[Y1]（#cf_span[0 ≤ Y1 ≤ 10^7]，且 #cf_span[Y0 ≠ Y1]）。第二行包含一个严格递增的 #cf_span[N] 个数字序列——老鼠的 #cf_span[x] 坐标。第三行包含一个严格递增的 #cf_span[M] 个数字序列——奶酪的 #cf_span[x] 坐标。所有坐标均为整数，绝对值不超过 #cf_span[10^7]。\n\n## Output\n\n输出仅一行，包含一个数字——保持饥饿的老鼠的最小数量。\n\n[samples]\n\n## Note\n\n所有三只老鼠都会选择第一块奶酪。第二只和第三只老鼠会吃掉这块奶酪。第一只老鼠会保持饥饿，因为它也朝同一块奶酪奔跑，但到达得太晚。第二块奶酪将保持未被食用。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of mice.  \nLet $ M \\in \\mathbb{Z}_{\\geq 0} $ be the number of cheese pieces.  \nLet $ Y_0, Y_1 \\in \\mathbb{R} $, $ Y_0 \\ne Y_1 $, be the $ y $-coordinates of the lines on which mice and cheese lie, respectively.  \n\nLet $ A = (a_1, a_2, \\dots, a_N) $ be the strictly increasing sequence of $ x $-coordinates of the mice.  \nLet $ B = (b_1, b_2, \\dots, b_M) $ be the strictly increasing sequence of $ x $-coordinates of the cheese pieces.  \n\nThe Euclidean distance from mouse $ a_i $ to cheese $ b_j $ is:  \n$$ d(i,j) = \\sqrt{(a_i - b_j)^2 + (Y_0 - Y_1)^2} $$  \n\n**Constraints**  \n1. $ 1 \\le N \\le 10^5 $  \n2. $ 0 \\le M \\le 10^5 $  \n3. $ |a_i|, |b_j| \\le 10^7 $  \n4. All $ a_i $ are distinct and strictly increasing.  \n5. All $ b_j $ are distinct and strictly increasing.  \n\n**Objective**  \nAssign each mouse to at most one cheese piece such that:  \n- Each mouse chooses the cheese piece minimizing $ d(i,j) $ (closest in Euclidean distance).  \n- In case of ties in distance, the assignment must minimize the number of hungry mice.  \n- Each cheese piece can be eaten by at most one mouse (first mouse to arrive eats it; others are too late).  \n\nCompute the **minimal possible number of hungry mice**, i.e., the number of mice that cannot be assigned a unique cheese piece under the above rules.  \n\nEquivalently, find the **maximum number of mice that can be successfully fed**, then subtract from $ N $.  \n\nNote: Since $ Y_0 \\ne Y_1 $, the Euclidean distance is minimized when $ |a_i - b_j| $ is minimized. Thus, we can reduce the problem to matching mice to cheese based on minimal $ |a_i - b_j| $, with ties resolved to maximize matches.  \n\nThus, the problem reduces to:  \n> Given two sorted sequences $ A $ (mice) and $ B $ (cheese), find the maximum number of mice that can be matched to cheese such that each cheese is used at most once, and each mouse is matched to the cheese minimizing $ |a_i - b_j| $, with tie-breaking favoring maximum matches.  \n\nThis is equivalent to a **greedy bipartite matching** on the real line:  \n- For each mouse $ a_i $, consider the set of cheese $ b_j $ that are closest to it (in $ x $-distance).  \n- Due to sorted order and the fact that the optimal assignment under min-distance and tie-breaking for max matches is known to be solvable greedily, we can use a two-pointer or greedy matching algorithm on the sorted coordinates.  \n\n**Final Formal Objective**  \nCompute:  \n$$\n\\boxed{N - \\text{max\\_matching}}\n$$  \nwhere $ \\text{max\\_matching} $ is the size of the maximum matching from mice to cheese under the constraint that each mouse is matched to a cheese minimizing $ |a_i - b_j| $, and each cheese is matched to at most one mouse.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF76B","tags":["greedy","two pointers"],"sample_group":[["3 2 0 2\n0 1 3\n2 5","1"]],"created_at":"2026-03-03 11:00:39"}}