相邻和（简单版）(Adjacent Sums (easy))

题目描述

给定由 0 以上 M−1 以下的整数构成的整数列 A=(A₁,A₂,…,A_N)、B=(B₁,B₂,…,B_{N−1})。A、B 的长度分别为 N、N−1。

可以对 A 进行任意次以下操作：

• 选择一个满足 1≤i≤N 的整数 i，将 A_i 加 1。

求使以下条件成立所需的最小操作次数（可以证明在本题约束下条件一定能满足）：

• 对 i=1,2,…,N−1，A_i+A_{i+1} 除以 M 的余数等于 B_i。

本题约束下固定 M=2。

输入格式

N M
A1 A2 … AN
B1 B2 … BN−1

输出格式

一行输出答案。

样例输入 #1

3 2
1 1 1
1 1

样例输出 #1

1

第 1 次操作选择 i=2，得到 A=(1,2,1)。此时 A₁+A₂=3、A₂+A₃=3，满足条件。而 A=(1,1,1) 不满足条件，故答案为 1。

样例输入 #2

2 2
1 1
0

样例输出 #2

0

样例输入 #3

10 2
0 0 0 1 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0

样例输出 #3

4

数据范围

• 2 ≤ N ≤ 2×10⁵
• M = 2
• 0 ≤ A_i ≤ M−1
• 0 ≤ B_i ≤ M−1
• 输入值均为整数

知识点与难度

本题涉及的知识点从属于 GESP 3级，难度等级：⭐⭐。

测试点分布