#include "Anna.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
namespace anna
{
const int nx=1e5, g=500, sz=35, base=(1<<10);
int a[nx+5], st=-1, nxt, cnt;
struct bignum
{
vector<int> v;
bignum(int x=0)
{
v.resize(sz, 0);
v[0]=x;
}
void add(bignum &o)
{
int carry=0;
for (int i=0; i<sz; i++)
{
this->v[i]+=o.v[i]+carry;
if (this->v[i]>=base) this->v[i]-=base, carry=1;
else carry=0;
}
}
void subtract(bignum &o)
{
int carry=0;
for (int i=0; i<sz; i++)
{
this->v[i]-=o.v[i]+carry;
if (this->v[i]<0) this->v[i]+=base, carry=1;
else carry=0;
}
}
} fib[g];
}
void Anna(int N, std::vector<char> S) {
using namespace anna;
while (S.size()<nx) S.push_back('X');
S.push_back('A');
for (int i=0; i<nx; i++)
{
if (S[i]=='X'&&st==-1) st=i, a[i]=1;
if (S[i]=='Z'&&st!=-1&&(S[i+1]!='Z')) a[i]=1;
}
for (int i=0; i<nx; i++)
{
if (a[i])
{
nxt=a[i+1];
a[i+1]=0;
break;
}
}
//for (int i=0; i<N; i++) cout<<"anna "<<i<<' '<<a[i]<<'\n';
fib[0]=bignum(1);
fib[1]=bignum(2);
for (int i=2; i<g; i++) fib[i]=fib[i-1], fib[i].add(fib[i-2]);
vector<int> snd;
for (int i=0; i<nx; i+=g)
{
//cout<<"debug "<<i<<' '<<cnt<<'\n';
bignum tmp=bignum(0);
for (int j=i; j<i+g; j++) if (a[j]) tmp.add(fib[j-i]); //cout<<"tmp "<<tmp.v[0]<<'\n';
for (int j=0; j<sz; j++) for (int k=0; k<10; k++) ++cnt, snd.push_back((tmp.v[j]>>k)&1);
}
snd.pop_back();
for (auto x:snd) Send(x);
Send(nxt);
}
/*
5
X Z Y Z Y
*/
#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;
namespace bruno
{
const int nx=1e5, g=500, sz=35, base=(1<<10);
int a[nx+5], st=-1, nxt, rem[nx];
struct bignum
{
vector<int> v;
bignum(int x=0)
{
v.resize(sz, 0);
v[0]=x;
}
void add(bignum &o)
{
int carry=0;
for (int i=0; i<sz; i++)
{
this->v[i]+=o.v[i]+carry;
if (this->v[i]>=base) this->v[i]-=base, carry=1;
else carry=0;
}
}
void subtract(bignum &o)
{
int carry=0;
for (int i=0; i<sz; i++)
{
this->v[i]-=o.v[i]+carry;
if (this->v[i]<0) this->v[i]+=base, carry=1;
else carry=0;
}
}
int greater(bignum &o)
{
for (int i=sz-1; i>=0; i--)
{
if (this->v[i]>o.v[i]) return 1;
if (this->v[i]<o.v[i]) return 0;
}
return 1;
}
} fib[g];
}
void Bruno(int N, int L, std::vector<int> A) {
using namespace bruno;
nxt=A.back();
A.pop_back();
A.push_back(0);
int cur=0;
fib[0]=bignum(1);
fib[1]=bignum(2);
for (int i=2; i<g; i++) fib[i]=fib[i-1], fib[i].add(fib[i-2]);
for (int i=0; i<nx; i+=g)
{
bignum x=bignum(0);
for (int j=0; j<sz; j++) for (int k=0; k<10; k++) if (A[cur++]) x.v[j]|=(1<<k); //cout<<"here "<<x.v[0]<<'\n';
for (int j=g-1; j>=0; j--) if (x.greater(fib[j])) x.subtract(fib[j]), a[i+j]=1;
}
for (int i=0; i<N; i++)
{
if (a[i])
{
a[i+1]=nxt;
break;
}
}
int st=-1, lst=-1;
for (int i=0; i<N; i++)
{
//cout<<"bruno "<<i<<' '<<a[i]<<'\n';
if (a[i])
{
if (st==-1) lst=st=i;
else
{
for (int j=i-1; j>lst; j--) rem[j]=1, Remove(j);
lst=i;
rem[i]=1, Remove(i);
}
}
}
for (int i=0; i<N; i++) if (!rem[i]) Remove(i);
}
