#P17157. 阅读计划

阅读计划

阅读计划

来源:洛谷 P17157([入门赛 #50] 阅读计划)

题目描述

小洛正在阅读一本书。她使用某阅读 App 为自己制订了一份阅读计划,每天的阅读目标都是 TT 页。

每天阅读结束后,App 会比较小洛当天的实际阅读量与阅读目标:

  • 如果两者恰好相同,小洛获得 22 颗星星;
  • 如果两者的差的绝对值为 11 页或 22 页,小洛获得 11 颗星星;
  • 如果相差更多,则不能获得星星。

现在给出小洛连续 NN 天的实际阅读量,请你计算她在这 NN 天中一共获得了多少颗星星。

输入格式

第一行输入两个整数 NNTT,分别表示阅读的天数以及每天的阅读目标。

第二行输入 NN 个整数 p1,p2,,pNp_1, p_2, \ldots, p_N,其中 pip_i 表示小洛第 ii 天的实际阅读页数。

输出格式

输出一个整数,表示小洛在这 NN 天中获得的星星总数。

样例 #1

样例输入 #1

5 6
4 5 8 7 4

样例输出 #1

5

样例解释

小洛每天的阅读目标都是 66 页。五天的实际阅读量与目标分别相差 2,1,2,1,22,1,2,1,2 页,因此每天都获得 11 颗星星。

综上所述,小洛一共获得了 1+1+1+1+1=51+1+1+1+1=5 颗星星。

提示

数据范围

  • 本题共有 1010 个测试点;
  • 对于测试点 1,21,2,满足 N=1N=1
  • 对于所有测试数据,保证 1N1051 \le N \le 10^50T1040 \le T \le 10^4,并且对于每个 1iN1 \le i \le N,都有 0pi1040 \le p_i \le 10^4

提示

  • 先算 d=piTd = |p_i - T|,再按 d=0d = 0d=1 或 2d = 1 \text{ 或 } 2、其余情况分三类累加即可。
  • 答案最大为 2N2×1052N \le 2 \times 10^5,用 int 即可;建议仍用 long long 累加。

测试点数据说明

测试点 规模/特点 说明
1 N=1N=1p=Tp=T 恰好完成,得 2 星
2 N=1N=1T=0T=0 差 2 页得 1 星,同时覆盖 T=0T=0
3 官方样例 T=6T=6p=4 5 8 7 4p=4\ 5\ 8\ 7\ 4,答案 5
4 N=10N=10 混合 2 星、1 星、0 星均有
5 T=0T=0 专项 覆盖 0、1、2、>2 页差分的全部分界
6 T=104T=10^4 上界 pp9997..100009997..10000,覆盖上界附近分界
7 N=105N=10^5 全部相等 答案达到最大值 2×1052 \times 10^5
8 N=105N=10^5 每天差 1/2 页 每天得 1 星,答案 10510^5
9 N=105N=10^5 分散取值 差 0 ~ 7 页混合分布,0、1、2 星与 0 星均出现
10 N=105N=10^5 全范围随机 TTpp 均在 0..1040..10^4 随机