题解-CF1026B

Codeforces1026B Make Product Equal One
time limit per test:1s
memory limit per test:256M
input:standard input
output:standard output

You are given n numbers a[1],a[2],…,a[n]. With a cost of one coin you can perform the following operation:

Choose one of these numbers and add or subtract 1 from it.

In particular, we can apply this operation to the same number several times.

We want to make the product of all these numbers equal to 1, in other words, we want a1⋅a2 … ⋅an=1.

For example, for n=3 and numbers [1,−3,0] we can make product equal to 1 in 3 coins: add 1 to second element, add 1 to second element again, subtract 1 from third element, so that array becomes [1,−1,−1]. And 1⋅(−1)⋅(−1)=1.

What is the minimum cost we will have to pay to do that?

Input

The first line contains a single integer n (1≤n≤10^5) — the number of numbers.

The second line contains n integers a1,a2,…,an (−10^9≤ai≤10^9) — the numbers.

Output

Output a single number — the minimal number of coins you need to pay to make the product equal to 1.

Examples

inputCopy

2
-1 1

outputCopy

inputCopy

4
0 0 0 0

outputCopy

inputCopy

5
-5 -3 5 3 0

outputCopy
13

Note
In the first example, you can change 1 to −1 or −1 to 1 in 2 coins.

In the second example, you have to apply at least 4 operations for the product not to be 0.

In the third example, you can change −5 to −1 in 4 coins, −3 to −1 in 2 coins, 5 to 1 in 4 coins, 3 to 1 in 2 coins, 0 to 1 in 1 coin.

题解：这个看上去就是一个最小环鸭，不过据我们所知，Floyd求最小环的复杂度是O(n^3)的，那么我们怎么办呢？

通过观察可以发现，把每一个数二进制分解以后，最多只有64位，当一个位置被占用了3次及以上，就说明一定存在一个长度为3的环。

这说明了什么呢？只要大于0的数大于等于64*2+1=129个，答案就一定为3。

现在，n的范围已经变成了n<=129了，这样O(n^3)就一点问题都没有了。

还有几个注意事项：

1.在用Floyd求最小环的时候不要忘了前面的循环不可以到k，不要写成了真的Floyd。

2.注意最大值的3倍不要爆int(或Long long)

3.CF有一个非常坑的点，很多人都栽了(100000个0)

接下来是代码时间！

//最小环是O(n^3)，1e5？？后来发现就是要莽 
//在最坏的情况下，给出了 n 个数，其中有超过 128 个不为 0 的数，那么答案一定是3（因为当有128个不为0的数时，64位每一位的个数都是2，只要再随便来个不为0的数，都会出现大于2的位数，构成 3 的环）
#include <bits/stdc++.h>
#define For(i,a,b) for(register int i=a;i<=b;i++)
#define int long long
using namespace std;
inline int read() {int x=0,f=0;char ch=getchar();while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();return f?-x:x;}
inline void write(int x) {if(x<0) x=-x,putchar('-');if(x>=10) write(x/10);putchar(x%10+'0');}
const int N=130;
int n,cnt,tot,a[120000],b[120000],ans=2000000,dis[N][N],w[N][N];
signed main() {
    n=read();a
    For(i,1,n) {a[i]=read();if(a[i]>0) tot++;}
    if(tot>=129) return puts("3"),0;
    For(i,1,n) if(a[i]>0) b[++b[0]]=a[i];
    n=b[0];
    For(i,1,n) For(j,1,n) dis[i][j]=w[i][j]=2000000;
    For(i,1,n) For(j,1,n) if((b[i]&b[j])>0 && i!=j) dis[i][j]=w[i][j]=1;
    For(k,1,n) {
        For(i,1,k-1) For(j,i+1,k-1) ans=min(ans,dis[i][j]+w[j][k]+w[k][i]);
        For(i,1,n) For(j,1,n) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);    
    }
    cout<<((ans>0 && ans<=1000000)?ans:-1);
    return 0;
}