summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--broken_bits.cpp167
-rw-r--r--pie_packages.cpp240
-rw-r--r--sluggish_security.cpp203
-rw-r--r--steadfast_snakes.cpp215
4 files changed, 825 insertions, 0 deletions
diff --git a/broken_bits.cpp b/broken_bits.cpp
new file mode 100644
index 0000000..de08d4d
--- /dev/null
+++ b/broken_bits.cpp
@@ -0,0 +1,167 @@
+// 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);
+} \ No newline at end of file
diff --git a/pie_packages.cpp b/pie_packages.cpp
new file mode 100644
index 0000000..1224328
--- /dev/null
+++ b/pie_packages.cpp
@@ -0,0 +1,240 @@
+// Hacker Cup 2017
+// Round 3
+// Pie Packages
+// 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);
+}
+
+#define LIM 2000001
+#define MOD 1000000007
+#define DIV2 500000004
+
+int Add(int a,int b)
+{
+ a+=b;
+ if (a>=MOD)
+ a-=MOD;
+ return(a);
+}
+
+int Sub(int a,int b)
+{
+ a-=b;
+ if (a<0)
+ a+=MOD;
+ return(a);
+}
+
+int Mult(int a,int b)
+{
+ return((LL)a*b%MOD);
+}
+
+int main()
+{
+ // vars
+ int T,t;
+ int N;
+ int O,Ao,Bo,Co,Do;
+ int C,Ac,Bc,Cc,Dc;
+ int i,j,k,d,d2,ans;
+ int r1,r2,m;
+ LL a,b,c;
+ static int E[LIM],dist[LIM],sum[LIM];
+ static LL D1[LIM],D2[LIM],S1[LIM],S2[LIM];
+ static vector<PR> con[LIM];
+ priority_queue<PR> Q;
+ // testcase loop
+ Read(T);
+ Fox1(t,T)
+ {
+ // input
+ Read(N);
+ Fox(i,N+1)
+ con[i].clear();
+ Read(O),Read(Ao),Read(Bo),Read(Co),Read(Do);
+ Fox(i,N)
+ {
+ E[i]=O;
+ j=(i+1)%N;
+ con[i].pb(mp(j,O));
+ con[j].pb(mp(i,O));
+ O=((LL)Ao*O+Bo)%Co+Do;
+ }
+ Read(C),Read(Ac),Read(Bc),Read(Cc),Read(Dc);
+ Fox(i,N)
+ {
+ con[N].pb(mp(i,C));
+ con[i].pb(mp(N,C));
+ C=((LL)Ac*C+Bc)%Cc+Dc;
+ }
+ // precompute outer distances/sums
+ D1[0]=D2[0]=S1[0]=S2[0]=0;
+ Fox(i,N*2)
+ {
+ D1[i+1]=D1[i]+E[i%N];
+ D2[i+1]=D2[i]+E[(N*2-i-1)%N];
+ S1[i+1]=Add(S1[i],D1[i+1]%MOD);
+ S2[i+1]=Add(S2[i],D2[i+1]%MOD);
+ }
+ // dijkstra's from center
+ Fill(dist,60);
+ Q.push(mp(0,N)),dist[N]=0;
+ while (!Q.empty())
+ {
+ d=-Q.top().x;
+ i=Q.top().y;
+ Q.pop();
+ if (d!=dist[i])
+ continue;
+ Fox(j,Sz(con[i]))
+ {
+ k=con[i][j].x;
+ d2=d+con[i][j].y;
+ if (d2<dist[k])
+ Q.push(mp(-d2,k)),dist[k]=d2;
+ }
+ }
+ // precompute center distance sums
+ sum[0]=0;
+ Fox(i,N*2)
+ sum[i+1]=Add(sum[i],dist[i%N]);
+ // process outer points
+ j=ans=0;
+ Fox(i,N)
+ {
+ // advance j to furthest node from i (along outside only)
+ for(;;)
+ {
+ c=D1[j]-D1[i];
+ a=min(c,D1[N]-c);
+ c=D1[j+1]-D1[i];
+ b=min(c,D1[N]-c);
+ if (b<=a)
+ break;
+ j++;
+ }
+ // binary search for furthest node in i..j which is closer along the ouside
+ r1=i,r2=j;
+ while (r2>r1)
+ {
+ m=(r1+r2+1)>>1;
+ if (D1[m]-D1[i]<dist[i]+dist[m%N])
+ r1=m;
+ else
+ r2=m-1;
+ }
+ a=r1;
+ // binary search for furthest node in j..(i+N) which is closer along the ouside
+ r1=j,r2=i+N;
+ while (r2>r1)
+ {
+ m=(r1+r2)>>1;
+ if (D1[i+N]-D1[m]<dist[i]+dist[m%N])
+ r2=m;
+ else
+ r1=m+1;
+ }
+ b=r1;
+ if (a==b)
+ {
+ c=D1[a]-D1[i];
+ if (c<D1[N]-c)
+ b++;
+ else
+ a--;
+ }
+ // add outer distances i -> i..a
+ ans=Add(ans,Sub(S1[a],S1[i]));
+ ans=Sub(ans,Mult(D1[i]%MOD,a-i));
+ // add outer distances i -> b..(i+N)
+ ans=Add(ans,Sub(S2[N*2-b],S2[N*2-(i+N)]));
+ ans=Sub(ans,Mult(D2[N*2-(i+N)]%MOD,i+N-b));
+ // add distances through center i -> (a+1)..(b-1)
+ if (a+1<=b-1)
+ {
+ ans=Add(ans,Mult(dist[i],b-a-1));
+ ans=Add(ans,Sub(sum[b],sum[a+1]));
+ }
+ }
+ // add center distances
+ ans=Mult(ans,DIV2);
+ ans=Add(ans,sum[N]);
+ // output
+ printf("Case #%d: %d\n",t,ans);
+ }
+ return(0);
+} \ No newline at end of file
diff --git a/sluggish_security.cpp b/sluggish_security.cpp
new file mode 100644
index 0000000..33f30b0
--- /dev/null
+++ b/sluggish_security.cpp
@@ -0,0 +1,203 @@
+// Hacker Cup 2017
+// Round 3
+// Sluggish Security
+// 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);
+}
+
+#define LIM 2000005
+#define MOD 1000000007
+
+int A[LIM],B[LIM],S[LIM];
+LL fct[LIM],ifct[LIM];
+
+PR gcd(int a,int b)
+{
+ if (!b)
+ return(mp(1,0));
+ PR p=gcd(b,a%b);
+ return(mp(p.y,p.x-p.y*(a/b)));
+}
+
+int Ch(int n,int k)
+{
+ return(fct[n]*ifct[k]%MOD*ifct[n-k]%MOD);
+}
+
+int main()
+{
+ // vars
+ int T,t;
+ int N,Ka,Kb;
+ int i,j,a,b;
+ int ans;
+ // precompute factorials and their modular inverses
+ Fox(i,LIM)
+ {
+ fct[i]=i ? fct[i-1]*i%MOD : 1;
+ ifct[i]=gcd(fct[i],MOD).x;
+ if (ifct[i]<0)
+ ifct[i]+=MOD;
+ }
+ // testcase loop
+ Read(T);
+ Fox1(t,T)
+ {
+ // input
+ Read(N);
+ Read(A[0]),Read(Ka),N=1;
+ while (Ka--)
+ {
+ Read(a),Read(b);
+ Fox(i,b)
+ Read(S[i]);
+ while (a--)
+ Fox(i,b) {
+ A[N]=A[N-1]+S[i];
+ N++;
+ }
+ }
+ Read(B[0]),Read(Kb),N=1;
+ while (Kb--)
+ {
+ Read(a),Read(b);
+ Fox(i,b)
+ Read(S[i]);
+ while (a--)
+ Fox(i,b) {
+ B[N]=B[N-1]+S[i];
+ N++;
+ }
+ }
+ // pad arrays
+ a=-1;
+ Fox(j,4)
+ {
+ A[N+j]=a--;
+ B[N+j]=a--;
+ }
+ // iterate through
+ ans=1;
+ i=j=a=b=0;
+ while ((i<N) || (j<N))
+ if (
+ (A[i]==B[j]) ||
+ (A[i]==B[j+1]) && (A[i+1]==B[j]) ||
+ (A[i]==A[i+2]) && (A[i+1]==B[j]) ||
+ (B[j]==B[j+2]) && (B[j+1]==A[i])
+ ) {
+ // cross pattern, must end current streaks
+ ans=(LL)ans*Ch(a+b,a)%MOD;
+ a=b=0;
+ if (A[i]==B[j])
+ i++,j++;
+ else
+ {
+ ans=(ans<<1)%MOD;
+ if (A[i]==A[i+2])
+ i+=3,j++;
+ else
+ if (B[j]==B[j+2])
+ j+=3,i++;
+ else
+ i+=2,j+=2;
+ }
+ }
+ else
+ // continue one of the current streaks?
+ if (A[i]==A[i+1])
+ i+=2,a++;
+ else
+ if (B[j]==B[j+1])
+ j+=2,b++;
+ else
+ if ((A[i]==A[i+2]) && (A[i+1]==A[i+3]))
+ i+=4,a++;
+ else
+ if ((B[j]==B[j+2]) && (B[j+1]==B[j+3]))
+ j+=4,b++;
+ else
+ {
+ // impossible pattern
+ ans=0;
+ break;
+ }
+ ans=(LL)ans*Ch(a+b,a)%MOD;
+ // output
+ printf("Case #%d: %d\n",t,ans);
+ }
+ return(0);
+} \ No newline at end of file
diff --git a/steadfast_snakes.cpp b/steadfast_snakes.cpp
new file mode 100644
index 0000000..51e3d1e
--- /dev/null
+++ b/steadfast_snakes.cpp
@@ -0,0 +1,215 @@
+// Hacker Cup 2017
+// Round 3
+// Steadfast Snakes
+// 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);
+}
+
+#define LIM 800008
+
+int L[2];
+LL BLT[2][2][LIM];
+
+void Update(int a,int b,int i,int v)
+{
+ for(i++;i<=L[a];i+=(i&-i))
+ BLT[a][b][i]+=v;
+}
+
+LL Query(int a,int b,int i)
+{
+ LL v=0;
+ for(i++;i>0;i-=(i&-i))
+ v+=BLT[a][b][i];
+ return(v);
+}
+
+int main()
+{
+ // vars
+ int T,t;
+ int N,A,B,C;
+ LL K;
+ int i,j,c,v,ans;
+ int r1,r2,m;
+ LL s;
+ static int H[LIM];
+ static int n1,n2,c1[LIM],c2[LIM],v1[LIM],v2[LIM],vc1[LIM],vc2[LIM];
+ // testcase loop
+ Read(T);
+ Fox1(t,T)
+ {
+ // input
+ scanf("%d%lld",&N,&K);
+ Read(v),Read(A),Read(B),Read(C);
+ Fox(i,N)
+ {
+ H[i]=v;
+ v=((LL)A*v+B)%C+1;
+ }
+ // check if there's a single dominating ladder
+ j=0;
+ Fox(i,N)
+ if (H[i]>H[j])
+ j=i;
+ Fox(i,N)
+ if ((i!=j) && (H[i]>H[j]-K-abs(i-j)))
+ break;
+ if (i==N)
+ {
+ // special case - only shorten the dominating ladder
+ ans=0;
+ Fox(i,N)
+ if (i!=j)
+ Max(ans,H[j]-(int)K+H[i]+abs(i-j));
+ goto Done;
+ }
+ // compress diagonal coordinates
+ n1=n2=0;
+ Fox(i,N)
+ {
+ c1[n1++]=v1[i]=i-H[i];
+ c2[n2++]=v2[i]=-i-H[i];
+ }
+ sort(c1,c1+n1);
+ sort(c2,c2+n2);
+ L[0]=n1=unique(c1,c1+n1)-c1;
+ L[1]=n2=unique(c2,c2+n2)-c2;
+ Fox(i,N)
+ {
+ vc1[i]=lower_bound(c1,c1+n1,v1[i])-c1;
+ vc2[i]=lower_bound(c2,c2+n2,v2[i])-c2;
+ }
+ // init BLTs
+ Fill(BLT,0);
+ Fox(i,N)
+ {
+ Update(1,0,vc2[i],1);
+ Update(1,1,vc2[i],v2[i]);
+ }
+ // try every possible pyramid center x-coordinate
+ ans=2*INF+N;
+ Fox(i,N)
+ {
+ // move ladder i from right to left BLT
+ Update(0,0,vc1[i],1);
+ Update(0,1,vc1[i],v1[i]);
+ Update(1,0,vc2[i],-1);
+ Update(1,1,vc2[i],-v2[i]);
+ // centered on i
+ r1=max(i+1,N-i),r2=INF+N;
+ while (r2>=r1)
+ {
+ m=(r1+r2)>>1;
+ // left
+ v=i-m;
+ c=lower_bound(c1,c1+n1,v)-c1-1;
+ s=Query(0,0,c)*v-Query(0,1,c);
+ // right
+ v=-i-m;
+ c=lower_bound(c2,c2+n2,v)-c2-1;
+ s+=Query(1,0,c)*v-Query(1,1,c);
+ if (s<=K)
+ r2=m-1,Min(ans,2*m);
+ else
+ r1=m+1;
+ }
+ // centered on i+0.5
+ if (i==N-1)
+ break;
+ r1=max(i+1,N-i-1),r2=INF+N;
+ while (r2>=r1)
+ {
+ m=(r1+r2)>>1;
+ // left
+ v=i-m;
+ c=lower_bound(c1,c1+n1,v)-c1-1;
+ s=Query(0,0,c)*v-Query(0,1,c);
+ // right
+ v=-(i+1)-m;
+ c=lower_bound(c2,c2+n2,v)-c2-1;
+ s+=Query(1,0,c)*v-Query(1,1,c);
+ if (s<=K)
+ r2=m-1,Min(ans,2*m+1);
+ else
+ r1=m+1;
+ }
+ }
+Done:;
+ printf("Case #%d: %d\n",t,ans);
+ }
+ return(0);
+}