{"problem":{"name":"8. Maximum Donut","description":{"content":"You have an $n$ by $n$ 2D grid of integers ranging from $-100$ to $100$. You define a _donut_ as a ring of numbers in the 2D grid, with a width of one. For example, this is an example of a donut (high","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF8"},"statements":[{"statement_type":"Markdown","content":"You have an $n$ by $n$ 2D grid of integers ranging from $-100$ to $100$. You define a _donut_ as a ring of numbers in the 2D grid, with a width of one. For example, this is an example of a donut (highlighted in green):\n\nNote that a donut must include a \"hole\", i.e. a $2$x$2$ square is *not* considered a donut. Note also that a donut does not have to be in a square shape.\n\nThe _value_ of a donut is defined as the sum of the numbers that it contains. For example, the donut pictured above has a value of 27. Given an $n$ by $n$ 2D grid, your task is to find the donut with the maximum value. \n\nThe first line of input contains a single positive integer $n$ ($n < = 400$): the width and height of the grid.\n\nThe next $n$ lines each contain $n$ space-separated integers, representing the elements of the grid. Each element will range from $-100$ to $100$, inclusive\n\nOutput the value of the maximum donut in the 2D grid.\n\nSubtask 1 (13 points): $n < = 80$\n\nSubtask 2 (34 points): no further constraints\n\n## Input\n\nThe first line of input contains a single positive integer $n$ ($n < = 400$): the width and height of the grid.The next $n$ lines each contain $n$ space-separated integers, representing the elements of the grid. Each element will range from $-100$ to $100$, inclusive\n\n## Output\n\nOutput the value of the maximum donut in the 2D grid.\n\n[samples]\n\n## Scoring\n\nSubtask 1 (13 points): $n < = 80$Subtask 2 (34 points): no further constraints","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"你有一栋由多个房间组成的房子，可以用一个 $n$ 行 $n$ 列的俯视平面图表示（显示房子中的墙壁和开放空间）。 \n\n你试图为房子中的每个开放空间分配一个数字。但为了防止重复，你决定：同一房间内的任意两个数字的最大公约数（GCD）必须为 1。\n\n在这些限制下，你的任务是找出在必须为每个开放空间分配一个数字的前提下，所能分配的数字的最小可能总和。\n\n输入的第一行包含一个正整数 $n$ $(1 \\le n \\le 800)$：房子的宽度和高度。\n\n接下来的 $n$ 行，每行包含一个 $n$ 字符的字符串，表示房子的平面图。字符 \"x\" 表示墙壁，字符 \".\" 表示开放空间。\n\n请输出一个正整数：根据上述规则，房子中所有开放空间所分配数字的最小可能总和。\n\n完整题目：58 分\n\n在第一个示例中，你可以在四个开放空间中放置数字 1、2、3 和 5。\n\n## Input\n\n输入的第一行包含一个正整数 $n$ $(1 \\le n \\le 800)$：房子的宽度和高度。接下来的 $n$ 行，每行包含一个 $n$ 字符的字符串，表示房子的平面图。字符 \"x\" 表示墙壁，字符 \".\" 表示开放空间。\n\n## Output\n\n输出一个正整数：根据上述规则，房子中所有开放空间所分配数字的最小可能总和。\n\n[samples]\n\n## Scoring\n\n完整题目：58 分\n\n## Note\n\n在第一个示例中，你可以在四个开放空间中放置数字 1、2、3 和 5。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 800 $, be the grid size.  \nLet $ G = (g_{i,j})_{i,j=1}^n $ be an $ n \\times n $ grid where $ g_{i,j} = \\text{`.`} $ denotes an open space and $ g_{i,j} = \\text{`x`} $ denotes a wall.  \nLet $ S \\subseteq \\{1, \\dots, n\\} \\times \\{1, \\dots, n\\} $ be the set of coordinates of open spaces:  \n$$ S = \\{ (i,j) \\mid g_{i,j} = \\text{`.`} \\} $$  \nLet $ \\mathcal{C} $ be the set of connected components of $ S $ under 4-directional adjacency (up, down, left, right); each component is a maximal connected region of open spaces.  \n\n**Constraints**  \nFor each connected component $ C \\in \\mathcal{C} $, assign a positive integer $ a_{i,j} \\in \\mathbb{Z}^+ $ to each $ (i,j) \\in C $ such that:  \n$$ \\gcd(a_{i,j}, a_{i',j'}) = 1 \\quad \\forall (i,j), (i',j') \\in C, \\ (i,j) \\neq (i',j') $$  \n\n**Objective**  \nMinimize the total sum:  \n$$ \\sum_{(i,j) \\in S} a_{i,j} $$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF8","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}