[AGC037C] Numbers on a Circle
题意翻译
一个环上有 $N$ 个正整数,一次操作可以把第 $i$ 个数 $A_i$ 变为它左边的数、它右边的数和它本身之和,即 $A_{i-1}+A_i+A_{i+1}$,$A_0$ 就是 $A_n$,$A_{n+1}$ 是 $A_1$。
初始时对每一个位置 $i$,第 $i$ 个位置上的数为 $A_i$,目标为对于每一个位置,将这个位置上的数变为 $B_i$。
求最少需要几次操作,可以达到目标位置。
题目描述
[problemUrl]: https://atcoder.jp/contests/agc037/tasks/agc037_c
円環状に $ N $ 個の正整数が並んでおり、それらには円環に沿った順に $ 1 $ から $ N $ の番号がついています。
今 $ i $ 番目の数は $ A_i $ です。高橋君は $ i $ 番目の正整数が $ B_i $ となるようにしたいです。 そこで、高橋君は以下の操作を繰り返し行うことにしました。
- $ 1\ \leqq\ i\ \leqq\ N $ なる整数 $ i $ を一つ選ぶ。
- $ i-1,i,i+1 $ 番目の数をそれぞれ $ a,b,c $ としたとき、$ i $ 番目の数を $ a+b+c $ に置き換える。
ただし、$ 0 $ 番目の数は $ N $ 番目の数を指し、$ N+1 $ 番目の数は $ 1 $ 番目の数を指すことに注意してください。
高橋君が条件をみたすように操作を行うことができるかどうか判定してください。 また可能である場合は、高橋君が行う必要のある操作回数として考えられる最小の値を求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $ $ B_1 $ $ B_2 $ $ ... $ $ B_N $
输出格式
高橋君が行う必要のある操作回数として考えられる最小の値を出力せよ。 ただし、高橋君が条件をみたすように操作を行うことができない場合は `-1` を出力せよ。
输入输出样例
输入样例 #1
3
1 1 1
13 5 7
输出样例 #1
4
输入样例 #2
4
1 2 3 4
2 3 4 5
输出样例 #2
-1
输入样例 #3
5
5 6 5 2 1
9817 1108 6890 4343 8704
输出样例 #3
25
说明
### 制約
- $ 3\ ≦\ N\ ≦\ 2\ \times\ 10^5 $
- $ 1\ ≦\ A_i,\ B_i\ ≦\ 10^9 $
- 入力中のすべての値は整数である
### Sample Explanation 1
例えば高橋君は以下のように操作を行うことができます。 - $ 2 $ 番目の数を $ 3 $ に置き換える。 - $ 2 $ 番目の数を $ 5 $ に置き換える。 - $ 3 $ 番目の数を $ 7 $ に置き換える。 - $ 1 $ 番目の数を $ 13 $ に置き換える。