Merge branch 'master' of https://github.com/dunkerC/esercizi

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);

+}