Problem: brokenbits (2017 round3)

You're looking at a sort of clock which has a row of **N** lights. Each light
is either on or off, and their states can be read as an **N**-digit binary
number. The first light represents the most significant (leftmost) digit while
the **N**th light represents the least significant digit. A light that's on
corresponds to a 1, and a light that's off corresponds to a 0.

You've just started looking at the clock, and you know that every second from
now on, it will count upwards by 1, with its lights turning on or off to
display the next number in binary. Once the clock displays 2**N** \- 1 (with
all **N** lights on), it will wrap around to display 0 (with all lights off)
on the following second, and then continue counting up again.

However, 0 or more of the clock's lights may be permanently broken. You don't
know which ones those are, but you know that they'll always appear to be off,
even when they should be on.

Currently, the _i_th light appears to be on if **Li** = 1, and otherwise
appears to be off (if **Li** = 0). You have also received insider information
that exactly **K** of the lights are currently supposed to be on. It's
guaranteed that **K** is at least as large as the number of lights which
appear to be on.

Assuming you stand around and look at this clock for a while, what's the
maximum amount of time you might have to wait before you can be completely
sure of what state every single light is currently supposed to be in? It's
possible that you can be sure immediately, after 0 seconds. On the other hand,
it's also possible that you might never be sure, no matter how long you wait.

### Input

Input begins with an integer **T**, the number of different clocks you own.
For each clock, there is first a line containing the two space-separated
integers, **N** and **K**. Then there is a line containing **N** space-
separated integers, the _i_th of which is **Li**.

### Output

For the _i_th clock, print a line containing "Case #**i**: " followed by the
maximum number of seconds which might go by before you know the true current
state of each light, or -1 if you might never know.

### Constraints

1 ≤ **T** ≤ 5,000  
1 ≤ **N** ≤ 60  
0 ≤ **K** ≤ **N**  
0 ≤ **Li** ≤ 1  

### Explanation of Sample

In the first case, exactly one of the two rightmost lights is initially
supposed to be on, so the clock is either supposed to be showing 101 (5) or
110 (6). After one second, the clock will be supposed to show either 110 (6)
or 111 (7). Supposing that the two rightmost lights are both broken, both of
these values will still look like 100 to you, so you won't be able to tell
which one is correct. After one more second, the clock will be supposed to
show either 111 (7) or 000 (0). At that point, by observing the functioning
leftmost light, you can determine whether all three lights are supposed to be
on or off at that moment.

In the second case, you'll never be able to tell which of the two leftmost
lights are supposed to be on if they're both broken.



Sample input:
5
3 2
1 0 0
3 2
0 0 1
7 4
0 1 0 0 1 0 0
20 15
1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 1
20 19
0 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0 1 0 1 0


Sample output:
Case #1: 2
Case #2: -1
Case #3: 19
Case #4: 217601
Case #5: 8193



Code: // Hacker Cup 2017
// Round 3
// Broken Bits
// Jacob Plachta

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }

const int INF = (int)1e9;
const LD EPS = 1e-9;
const LD PI = acos(-1.0);

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=getchar();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

int main()
{
	// vars
	int T,t;
	int N,K;
	int i,a,b,ones,origOnes,forceZero;
	bool allOnes;
	LL v1,v2,ans;
	int origL[60],L[60];
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			Read(N),Read(K);
			ones=0;
				Fox(i,N)
					Read(L[i]),ones+=L[i];
			origOnes=ones=K-ones;
			memcpy(origL,L,sizeof(L));
			// all unknowns must be 0 or 1?
				if ((!ones) || (N==K))
				{
					ans=0;
					goto Done;
				}
			// 2 leading 0s (can never differentiate them)?
				if (L[0]+L[1]==0)
				{
					ans=-1;
					goto Done;
				}
			// try all possible key 0 sequences
			ans=0;
				Fox1(a,N-1)
					if ((!origL[a]) && (origL[a-1]))
						Fox(forceZero,2)
						{
							// find end of key 0 sequence
							memcpy(L,origL,sizeof(L));
							ones=origOnes;
								FoxI(i,a,N-1)
									if (L[i])
										break;
							b=i-1;
							// allocate as many 1s on the left of the key sequence as possible
							// (but leaving at least 1, and optionally forcing one of them to be 0)
							allOnes=1;
								Fox(i,a)
									if (!L[i])
										if ((ones>1) && ((!allOnes) || (!forceZero)))
											L[i]=1,ones--;
										else
											allOnes=0;
							// allocate as many 1s as close to the end as possible (but leaving at least 1)
								FoxRI(i,b+1,N-1)
									if ((!L[i]) && (ones>1))
										L[i]=1,ones--;
							// in key sequence, use smallest possible allocation
								if (!ones)
									continue;
								FoxRI(i,a,b)
									if (ones)
										L[i]=1,ones--;
								if (ones)
									continue;
							// if left of key sequence is all 1s, use 2nd-smallest allocation instead
								if (allOnes)
									if (!next_permutation(L+a,L+b+1))
										continue;
							v1=0;
								Fox(i,N)
									v1=v1*2+L[i];
							// state will be known once key sequence wraps around
								FoxI(i,a,N-1)
									L[i]=1;
							v2=0;
								Fox(i,N)
									v2=v2*2+L[i];
							Max(ans,v2-v1+1);
						}
			// output
Done:;
			printf("Case #%d: %lld\n",t,ans);
		}
	return(0);
}