12201: 【原2201】Marisa

题目

题目描述

author: 向子卿 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/2201

Description

初始状态

\({\bf a} \in {\bf Z}^n\).

目标状态

• \({\bf b} \in {\bf Z}^n\).
• \({\bf b} \geq {\bf 0}\).
• \({\bf b} \neq {\bf 0}\).

操作

把三个数\(a(i-1), a(i), a(i+1)\)其中\(a(i) \lt 0\), \(i\in {\bf Z}/n{\bf Z}\), 用三个新的数\(a(i-1)+a(i), -a(i), a(i+1)+a(i)\), 替换他们.

问题

最少需要多少次操作可以把\({\bf a}\)变爲\({\bf b}\)?

Input Format

第一行. 一个数\(m\). 共有\(m\)组数据.
第\(3k-1\)行. 第\(k\)个数据的初始状态与目标状态的\(n\).
第\(3k\)行. 第\(k\)个数据的初始状态. 用空格隔开.
第\(3k+1\)行. 第\(k\)个数据的目标状态. 用空格隔开.

Output Format

共\(m\)行，每行一个数，表示最少需要的操作次数从初始状态变爲目标状态.输出\(-1\)若不可能到达.

Sample Input

4
3
1 2 3
3 2 1
4
1 2 3 4
1 2 3 4
5
5 4 3 2 -1
4 4 3 1 1
4
3 -1 3 -1
1 1 1 1

Sample Output

-1
0
1
2

Level

\(m\leq 10\).
\(|a(i)|, |b(i)|\leq 2^{14}\).
Easy. \(1\leq n\lt 5\).
Normal. \(5\leq n\lt 10\).
Hard. \(10\leq n\lt 20\).
Lunatic. \(20\leq n\lt 40\).
Extra. \(40\leq n\lt 100\).
Phantasm. \(100\leq n\lt 1000\).
Answers are less than \(10^7\).

Hint

Trick.

Limitation

Time. \(1000\)ms.
Memory. \(65536\)KB.

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！