English · Original
Chinese · Translation
Formal · Original
Забор состоит из $N$ одинаковых вертикальных досок. Некоторые из досок сгнили и нуждаются в замене, для каждой доски известно, нужно ли её заменить. Для ремонта забора можно использовать продающиеся в магазине щиты, которые бывают $L$ разных видов: шириной в 1 доску, в 2 доски, ... , в $L$ досок. Щит нельзя разрезать на части, то есть одним щитом можно заменить не более $L$ подряд идущих досок. При этом можно менять не только сгнившие доски, но и хорошие. Оказалось, что все щиты стоят одинаково, независимо от размера щита. Определите, какие наименьшее число щитов необходимо приобрести, чтобы починить весь забор.
Первая строка входных данных содержит целое число $L$ ($L > 0$) — максимальный размер щита. Во второй строке входных данных записано целое число $N$ ($N > 0$) — количество досок в заборе. Следующие $N$ строк содержать по одному числу 0 или 1. Число 1 означает, что соответствующая доска в заборе нуждается в замене, число 0 — что доска может быть сохранена.
Программа должна вывести одно целое число — минимальное число щитов, которое необходимо приобрести для ремонта всего забора.
Решение, правильно работающее только для случаем когда числа $L$ и $N$ не превосходят 1000, будет оцениваться в 60 баллов.
В 100 баллов оценивается решение, правильно работающее для чисел, не превосходящих $10^5$.
Максимальная ширина одного щита равна 3. Забор состоит из 8 досок, нужно заменить доски с номерами 3, 5 и 7. Для этого достаточно двух щитов. Например, одним щитом меняет доски с номерами 3, 4, 5, а другим доску с номером 7.
## Входные Данные
Первая строка входных данных содержит целое число $L$ ($L > 0$) — максимальный размер щита. Во второй строке входных данных записано целое число $N$ ($N > 0$) — количество досок в заборе. Следующие $N$ строк содержать по одному числу 0 или 1. Число 1 означает, что соответствующая доска в заборе нуждается в замене, число 0 — что доска может быть сохранена.
## Выходные Данные
Программа должна вывести одно целое число — минимальное число щитов, которое необходимо приобрести для ремонта всего забора.
## Пример
Входные данные3
8
0
0
1
0
1
0
1
0
Выходные данные2
## Примечание
Максимальная ширина одного щита равна 3. Забор состоит из 8 досок, нужно заменить доски с номерами 3, 5 и 7. Для этого достаточно двух щитов. Например, одним щитом меняет доски с номерами 3, 4, 5, а другим доску с номером 7.
## Система Оценки
Решение, правильно работающее только для случаем когда числа $L$ и $N$ не превосходят 1000, будет оцениваться в 60 баллов. В 100 баллов оценивается решение, правильно работающее для чисел, не превосходящих $10^5$.
[samples]
Tom 最近喜欢玩一款电子游戏。该游戏的规则如下：游戏在一条 $x$-轴上进行。游戏中共有 $n + 1$ 个柱子，从左到右排成一行，柱子编号为 $0$ 到 $n$，编号为 $i$ 的柱子坐标为 $x = i$。此外，游戏中还有一个无限延伸的平台，覆盖范围为 $[ n + 1, + \infty)$。玩家只要跳到该范围内的任意位置即可 *获胜*。
玩家从编号为 $0$ 的柱子出发，只能向右跳跃（即坐标必须递增），且只能落在柱子或平台上，否则会掉入虚空而 *失败*。此外，玩家的跳跃能力有限，每次跳跃的距离不超过 $p$。
除了编号为 $0$ 的柱子外，其余每个柱子上都有一宝箱。编号为 $i$ 的柱子上的宝箱包含 $a_i$ 枚金币。但有些是陷阱宝箱（$a_i < 0$），玩家会失去 $| a_i |$ 枚金币。
该游戏共有 $n$ 个关卡。在第 $i$ 个关卡中，Tom 只能跳到编号为 $i$ 的倍数的柱子上。现在有 $q$ 个查询，每个查询给出一个数 $x$，要求计算 Tom 在第 $x$ 个关卡中 *获胜* 时能获得的最大金币数。可能 Tom 在途中打开了太多陷阱宝箱，导致最终金币数为负。
第一行包含三个整数 $n$、$q$ 和 $p$（$2 \leq p \leq n \leq 10^6$，$1 \leq q \leq 10^6$），分别表示柱子数量、查询数量和最大跳跃距离。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$| a_i | \leq 10^9$），表示编号为 $i$ 的柱子上宝箱的金币数量。
接下来 $q$ 行，每行包含一个整数 $x$（$1 \leq x \leq n$），表示一个查询，要求计算在第 $x$ 个关卡中能获得的最大金币数。
对每个查询，输出一行一个整数表示答案。如果无法获胜，请输出 _Noob_。
## Input
第一行包含三个整数 $n$、$q$ 和 $p$（$2 \leq p \leq n \leq 10^6$，$1 \leq q \leq 10^6$），表示柱子数量、查询数量和最大跳跃距离。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$| a_i | \leq 10^9$），表示编号为 $i$ 的柱子上宝箱的金币数量。接下来 $q$ 行，每行包含一个整数 $x$（$1 \leq x \leq n$），表示一个查询，要求计算在第 $x$ 个关卡中能获得的最大金币数。
## Output
对每个查询，输出一行一个整数表示答案。如果无法获胜，请输出 _Noob_。
[samples]
**Definitions**
Let $ n, q, p \in \mathbb{Z} $ with $ 2 \leq p \leq n \leq 10^6 $, $ 1 \leq q \leq 10^6 $.
Let $ A = (a_1, a_2, \dots, a_n) \in \mathbb{Z}^n $, where $ a_i $ is the gold coin value at pillar $ i $.
Let $ \mathcal{P} = \{0, 1, 2, \dots, n\} $ be the set of pillar positions.
Let $ \mathcal{F} = [n+1, +\infty) $ be the winning platform.
**Constraints**
1. Player starts at pillar $ 0 $.
2. Player may only jump rightward (increasing $ x $-coordinate).
3. Each jump has length $ \leq p $.
4. In level $ x $, player may only land on pillars at positions $ i $ where $ x \mid i $, or the platform.
5. Player wins by reaching any position in $ \mathcal{F} $.
**Objective**
For each query $ x \in \{1, \dots, n\} $, compute the maximum total gold coins collectible along a valid path from pillar $ 0 $ to $ \mathcal{F} $, where allowed landing positions are $ \{0\} \cup \{ i \in \{1, \dots, n\} \mid x \mid i \} \cup \mathcal{F} $, and each jump $ \leq p $.
If no such path exists, output `Noob`.
Otherwise, output:
$$
\max \left\{ \sum_{\substack{i \in \{1,\dots,n\} \\ x \mid i \\ \text{visited}}} a_i \,\middle|\, \text{valid path from } 0 \text{ to } \mathcal{F} \right\}
$$
API Response (JSON)
{
"problem": {
"name": "C. Ремонт забора",
"description": {
"content": "Забор состоит из $N$ одинаковых вертикальных досок. Некоторые из досок сгнили и нуждаются в замене, для каждой доски известно, нужно ли её заменить. Для ремонта забора можно использовать продающиеся в",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CFC"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Забор состоит из $N$ одинаковых вертикальных досок. Некоторые из досок сгнили и нуждаются в замене, для каждой доски известно, нужно ли её заменить. Для ремонта забора можно использовать продающиеся в...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Tom 最近喜欢玩一款电子游戏。该游戏的规则如下：游戏在一条 $x$-轴上进行。游戏中共有 $n + 1$ 个柱子，从左到右排成一行，柱子编号为 $0$ 到 $n$，编号为 $i$ 的柱子坐标为 $x = i$。此外，游戏中还有一个无限延伸的平台，覆盖范围为 $[ n + 1, + \\infty)$。玩家只要跳到该范围内的任意位置即可 *获胜*。\n\n玩家从编号为 $0$ 的柱子出发，只能向右跳跃（...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, q, p \\in \\mathbb{Z} $ with $ 2 \\leq p \\leq n \\leq 10^6 $, $ 1 \\leq q \\leq 10^6 $. \nLet $ A = (a_1, a_2, \\dots, a_n) \\in \\mathbb{Z}^n $, where $ a_i $ is the gold coin value...",
"is_translate": false,
"language": "Formal"
}
]
}