#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int to_int(char c) {
if (c == 'R') return 0;
else if (c == 'G') return 1;
else return 2;
}
char to_char(int i) {
const string S = "RGB";
return S[i];
}
int base_one(int prv, int res) {
if ((prv+1)%3 != res) return (prv+1)%3;
else return (prv+2)%3;
}
int diff(int a, int b) {
//returns a number from 0~2 different from both a and b
if ((a+1)%3 == b) return (a+2)%3;
else return (a+1)%3;
}
int fib[30];
const int maxfib = 28;
}
void add_bit(std::vector<int> &ret, std::vector<int> &v, int bit) {
//add semantic bit, could be 0/1/2
int ind = ret.size();
if (ind >= v.size()) return;
for (int i = 0;i < bit*2;i++) {
ret.push_back(base_one(ret.back(), v[ind]));
ind++;
if (ind >= v.size()) return;
}
if (ret.back() != v[ind]) {
ret.push_back(ret.back()); //base 0
ind++;
} else {
if (ind+1 >= v.size()) {
ret.push_back(base_one(ret.back(), v[ind]));
return;
}
ret.push_back(base_one(ret.back(), v[ind+1]));
ret.push_back(ret.back());
ind+=2;
}
}
pair<string, int> anna(int N, string S) {
fib[0] = fib[1] = 1;
for (int i = 2;i < 29;i++) fib[i] = fib[i-1] + fib[i-2];
vector<int> v(N, 0), ret;
for (int i = 0;i < N;i++) v[i] = to_int(S[i]);
ret.push_back((v[0]+1)%3);
int maxlen = 0;
while (ret.size() < N) {
int pos = ret.size();
//try to encode pos
vector<int> bi;
for (int i = maxfib;i > 0;i--) {
if (pos >= fib[i]) bi.push_back(1), pos -= fib[i];
else bi.push_back(0);
}
reverse(bi.begin(), bi.end());
while (bi.size() && bi.back() == 0) bi.pop_back();
int len = 0;
for (int b:bi) {
len += (b+1)*2;
add_bit(ret, v, b);
}
maxlen = max(maxlen, len);
add_bit(ret, v, 2); //add separator
}
int L = min(N, maxlen*2+6);
string ans;
for (int i = 0;i < N;i++) {
ans.push_back(to_char(ret[i]));
}
debug(ans, S);
return make_pair(ans, L);
}
#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int N, L;
int to_int(char c) {
if (c == 'R') return 0;
else if (c == 'G') return 1;
else return 2;
}
char to_char(int i) {
const string S = "RGB";
return S[i];
}
int base_one(int prv, int res) {
if ((prv+1)%3 != res) return (prv+1)%3;
else return (prv+2)%3;
}
const int maxfib = 28;
int fib[30];
}
void init(int N, int l) {
::N = N;
::L = l;
debug("L", l);
fib[0] = fib[1] = 1;
for (int i = 2;i < 29;i++) fib[i] = fib[i-1] + fib[i-2];
}
int bruno(string s) {
if (N == L) return 1;
int len = s.size();
vector<int> v;
for (int i = 1;i < len;i++) {
if (s[i] == s[i-1]) v.push_back(0);
else v.push_back(1);
}
debug(s);
pary(v.begin(), v.end());
vector<int> bits, pref;
int count = 0;
for (int i = 0;i < v.size();i++) {
if (v[i] == 0) {
bits.push_back(count / 2);
pref.push_back(i - count);
count = 0;
} else {
count += 1;
}
}
if (count >= 4) {
bits.push_back(2);
pref.push_back(v.size() - count);
}
pary(bits.begin(), bits.end());
pary(pref.begin(), pref.end());
int ind = 1, num = 0;
for (int i = 0;i < bits.size();i++) {
if (bits[i] == 2) {
for (int j = i+1;j < bits.size();j++) {
if (bits[j] == 2) break;
num += bits[j] * fib[ind];
ind += 1;
}
debug(num);
num -= pref[i+1];
break;
}
}
debug("Answer", num);
return num;
}
