{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e由于现代化进程的加快,农场的养殖业也趋向机械化。\u003c/p\u003e\u003cp\u003elyz 决定购置若干台自动喂草机来减少自己每天的工作量。\u003c/p\u003e\u003cp\u003e为了简化问题,lyz 决定将草地建模成一条线段,总长为 $n$,即共有 $n$ 个单位长度,编号从左至右为 $1\\sim n$。\u003c/p\u003e\u003cp\u003elyz 可以在每个单位长度独立选择是否放置一台自动喂草机。由于场地的限制,喂草机一旦在 $i$ 处放下,它只能往左边延伸覆盖一个从 $i$ 开始的完整区间,且延伸的距离不能超过 $w_i$,即最多到编号为 $i-w_i+1$ 的单位长度。同时为了小草的健康着想,营养不能太丰富,因此每个单位长度只能被一台自动喂草机覆盖。\u003c/p\u003e\u003cp\u003elyz 想使得每台喂草机的覆盖大小达到一个最低标准以节省费用,若喂草机覆盖 $[l,r]$,那么覆盖大小为 $r-l+1$。他规定一台喂草机最小覆盖大小为 $size$。所以如果一台喂草机的覆盖大小 $\u0026lt;size$,说明这个位置不能放置喂草机。\u003c/p\u003e\u003cp\u003e现在,lyz 想知道,如果喂草机覆盖的总大小仅需达到草地总长的 $s\\%$,最小覆盖大小最大是多少?\u003c/p\u003e\u003ch3\u003e输入格式\u003c/h3\u003e\u003cp\u003e输入共三行。\u003c/p\u003e\u003cp\u003e第一行输入整数 $n$。\u003c/p\u003e\u003cp\u003e第二行输入 $n$ 个整数 $w_i$,表示第 $i$ 个位置的延伸距离不能达到 $w_i$。\u003c/p\u003e\u003cp\u003e最后一行给定整数 $s$,意义如上述所示。\u003c/p\u003e\u003ch3\u003e输出格式\u003c/h3\u003e\u003cp\u003e输出最大的 $size$,意义如上述所示。\u003c/p\u003e\u003ch3\u003e数据范围\u003c/h3\u003e\u003cp\u003e对于 $100\\%$ 的数据,$1\\leq s\\leq 100, 2\\leq i\\leq n,w_{i-1}\\geq w_i-1$。\u003c/p\u003e\u003ctable\u003e\u003ccolgroup\u003e\u003ccol width\u003d\"25%\"\u003e\u003ccol width\u003d\"25%\"\u003e\u003ccol width\u003d\"25%\"\u003e\u003ccol width\u003d\"25%\"\u003e\u003c/colgroup\u003e\u003cthead\u003e\u003ctr\u003e\u003cth align\u003d\"center\"\u003e部分分\u003c/th\u003e\u003cth align\u003d\"center\"\u003e$n$\u003c/th\u003e\u003cth align\u003d\"center\"\u003e$w_i$\u003c/th\u003e\u003cth\u003e$s$\u003c/th\u003e\u003c/tr\u003e\u003c/thead\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd\u003e对于 $30\\%$ 的数据\u003c/td\u003e\u003ctd\u003e$\\leq 2000$\u003c/td\u003e\u003ctd\u003e$\\leq n$\u003c/td\u003e\u003ctd\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e对于另外 $10\\%$ 的数据\u003c/td\u003e\u003ctd\u003e$\\leq 10^5$\u003c/td\u003e\u003ctd\u003e$\\leq n$\u003c/td\u003e\u003ctd\u003e$\u003d100$\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e对于另外 $10\\%$ 的数据\u003c/td\u003e\u003ctd\u003e$\\leq 10^5$\u003c/td\u003e\u003ctd\u003e$\\le 3$\u003c/td\u003e\u003ctd\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e对于 $100\\%$ 的数据\u003c/td\u003e\u003ctd\u003e$\\leq 5\\times 10^5$\u003c/td\u003e\u003ctd\u003e$\\le n$\u003c/td\u003e\u003ctd\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n1 2 3 4\n100\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e\u003cp\u003e最小覆盖最大值就为 $4$,在第四个位置放喂草机即可。\u003c/p\u003e"}},{"title":"Sample 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n5 4 2 3 2\n50\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e\u003cp\u003e在第四个位置放喂草机,可以覆盖 $3$ 个位置,覆盖率达到 $50\\%$ 以上。\u003c/p\u003e"}}]}