{"problem":{"name":"E. Числа","description":{"content":"Марина любит нечётные значения. Однажды она выписала на доске все от $A$ до $B$ включительно, а затем стерла те числа, сумма цифр которых чётна. Определите, сколько чисел осталось на доске. Программа","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CFE"},"statements":[{"statement_type":"Markdown","content":"Марина любит нечётные значения. Однажды она выписала на доске все от $A$ до $B$ включительно, а затем стерла те числа, сумма цифр которых чётна. Определите, сколько чисел осталось на доске.\n\nПрограмма получает на вход два натуральных числа $A$ и $B$, $A <=.slant B$.\n\nПрограмма должна вывести единственное число — количество чисел с нечётной суммой цифр из выписанных на доске.\n\nРешение правильно работающее для случая, когда числа $A$ и $B$ однозначные, будет оцениваться в 20 баллов.\n\nРешение, правильно работающее для случая, когда числа $A$ и $B$ не превосходят 100, будет оцениваться в 40 баллов.\n\nРешение, правильно работающее для случая, когда числа $A$ и $B$ не превосходят 10000, будет оцениваться в 60 баллов.\n\nВ 100 баллов оценивается решение, которое работает для случаев когда числа $A$ и $B$ не превосходят $10^9$.\n\n## Входные Данные\n\nПрограмма получает на вход два натуральных числа $A$ и $B$, $A <=.slant B$.\n\n## Выходные Данные\n\nПрограмма должна вывести единственное число — количество чисел с нечётной суммой цифр из выписанных на доске.\n\n## Примеры\n\nВходные данные10\n20\nВыходные данные5\nВходные данные20\n20\nВыходные данные0\n\n## Система Оценки\n\nРешение правильно работающее для случая, когда числа $A$ и $B$ однозначные, будет оцениваться в 20 баллов.Решение, правильно работающее для случая, когда числа $A$ и $B$ не превосходят 100, будет оцениваться в 40 баллов.Решение, правильно работающее для случая, когда числа $A$ и $B$ не превосходят 10000, будет оцениваться в 60 баллов.В 100 баллов оценивается решение, которое работает для случаев когда числа $A$ и $B$ не превосходят $10^9$.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"在一个王国中有 N 个人。第 i 个人居住在点 #cf_span[(xi, yi)]。你是一个怪物，需要在王国中游走并捕获所有 N 个人。\n\n你的旅程如下：\n\n你需要处理 Q 个查询，分为两种类型：\n\n在本题中，你将获得一个整数 BASE 和多个查询。你需要初始化 #cf_span[T = 0]。\n\n类型 0 的查询表示指定的人移动到点 #cf_span[((a1 * T + b1)%BASE, (a2 * T + b2)%BASE)]。\n\n对于类型 1 的查询，你需要输出从点 #cf_span[((a1 * T + b1)%BASE, (a2 * T + b2)%BASE)] 出发捕获所有人所需的最短时间。你应将 #cf_span[T] 的值更新为计算出的时间。\n\n输入的第一行包含三个整数 #cf_span[N], #cf_span[Q] 和 #cf_span[BASE]（#cf_span[0 ≤ N, Q ≤ 10^5], #cf_span[0 ≤ BASE ≤ 10^9]）。接下来的 N 行每行包含两个整数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[0 ≤ xi, yi ≤ BASE]），表示每个人的坐标。\n\n接下来的 #cf_span[Q] 行包含以下类型的查询：\n\n对于每个类型 1 的查询，输出一个整数——完成捕获所有人旅程所需的最短时间，每个答案占一行。\n\n## Input\n\n输入的第一行包含三个整数 #cf_span[N], #cf_span[Q] 和 #cf_span[BASE]（#cf_span[0 ≤ N, Q ≤ 10^5], #cf_span[0 ≤ BASE ≤ 10^9]）。接下来的 N 行每行包含两个整数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[0 ≤ xi, yi ≤ BASE]），表示每个人的坐标。接下来的 #cf_span[Q] 行包含以下类型的查询：\n\n#cf_span[0] #cf_span[i] #cf_span[a1] #cf_span[b1] #cf_span[a2] #cf_span[b2]\n#cf_span[1] #cf_span[a1] #cf_span[b1] #cf_span[a2] #cf_span[b2]\n\n其中 #cf_span[i] 是人的编号（#cf_span[1 ≤ i ≤ N]），#cf_span[a1], #cf_span[b1], #cf_span[a2], #cf_span[b2] 是前述的值（#cf_span[0 ≤ a1, b1, a2, b2 ≤ 10^9]）。\n\n## Output\n\n对于每个类型 1 的查询，输出一个整数——完成捕获所有人旅程所需的最短时间，每个答案占一行。\n\n[samples]\n\n## Note\n\n在样例测试用例中，你处理了四个查询：\n\n你计算从 (4, 5) 出发的旅程的最短时间，答案为 28。你输出该答案并将 T 更新为 28；\n第 3 个人移动到 (29, 199)；\n你计算从 (115, 62) 出发的旅程的最短时间，答案为 728。你输出该答案并将 T 更新为 728；\n第 2 个人移动到 (1463, 2913)。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N, Q, \\text{BASE} \\in \\mathbb{Z}_{\\geq 0} $ with $ N, Q \\leq 10^5 $, $ \\text{BASE} \\leq 10^9 $.  \nLet $ P = \\{(x_i, y_i) \\mid i \\in \\{1, \\dots, N\\}\\} \\subseteq [0, \\text{BASE})^2 $ be the initial set of person positions.  \nLet $ T \\in \\mathbb{Z}_{\\geq 0} $ be a global state variable, initialized to $ 0 $.  \nLet $ a_1, a_2, b_1, b_2 \\in \\mathbb{Z} $ be fixed parameters (implied by context).  \n\n**Constraints**  \n1. $ 0 \\leq N, Q \\leq 10^5 $  \n2. $ 0 \\leq \\text{BASE} \\leq 10^9 $  \n3. $ 0 \\leq x_i, y_i < \\text{BASE} $ for all $ i \\in \\{1, \\dots, N\\} $  \n4. For each query:  \n   - Type 0: Person moves to $ \\left( (a_1 \\cdot T + b_1) \\bmod \\text{BASE},\\ (a_2 \\cdot T + b_2) \\bmod \\text{BASE} \\right) $  \n   - Type 1: Compute minimum TSP tour length starting from $ \\left( (a_1 \\cdot T + b_1) \\bmod \\text{BASE},\\ (a_2 \\cdot T + b_2) \\bmod \\text{BASE} \\right) $, visiting all $ N $ points, using Manhattan distance: $ d((x_1,y_1), (x_2,y_2)) = |x_1 - x_2| + |y_1 - y_2| $. Update $ T \\leftarrow \\text{result} $.  \n\n**Objective**  \nFor each query of type 1, output:  \n$$\n\\min_{\\sigma \\in S_N} \\left( d\\left(S, P_{\\sigma(1)}\\right) + \\sum_{i=1}^{N-1} d\\left(P_{\\sigma(i)}, P_{\\sigma(i+1)}\\right) \\right)\n$$  \nwhere $ S = \\left( (a_1 \\cdot T + b_1) \\bmod \\text{BASE},\\ (a_2 \\cdot T + b_2) \\bmod \\text{BASE} \\right) $, and $ S_N $ is the set of all permutations of $ \\{1, \\dots, N\\} $.  \nThen update $ T \\leftarrow $ this minimum value.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CFE","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}