2019 BUAA Summer Training 8 题解

Solved A B C D E F G H I J K
8/11 O . O O . . O O O O O
  • O for passing during the contest
  • Ø for passing after the contest
  • ! for attempted but failed
  • · for having not attempted yet

题目来源:2013长沙区域赛

比赛链接

A Alice’s Print Service

题目描述

分段收电费,求要买$s$度电最少花费是多少。

解题思路

签到题,从后到前更新一下后面的最小值即可。

AC代码

点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<stdio.h>
#include<algorithm>
typedef long long ll;
using namespace std;
int t,n;
ll s[100010],p[100010],mn[100010];
int main(){
int i,n,m;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)scanf("%lld%lld",&s[i],&p[i]),mn[i]=s[i]*p[i];
mn[n]=1e18;
for(i=n-2;i>=0;i--)mn[i]=min(mn[i],mn[i+1]);
while(m--){
int x;
scanf("%d",&x);
int pos=upper_bound(s,s+n,x)-s-1;
printf("%lld\n",min(1LL*p[pos]*x,mn[pos+1]));
}
}
return 0;
}

B Bob’s new toy

题目描述

解题思路

AC代码

点击
1
2


C Collision

题目描述

有个固定住的质量视作无限大的大硬币(半径$R_m$),有个小硬币(半径$r$)在$(x,y)$,沿着$(v_x,v_y)$方向移动,如果碰到大硬币就完全弹性碰撞弹回,问小硬币任何一块位于$x^2+y^2\leq R^2$的总时间。

解题思路

解出与大小圆分别相切的坐标,分类讨论一下即可。

AC代码

点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;

double Rm,R,r,x,y,vx,vy;
const double eps=1e-7;


double getdis(double x1,double y1,double x2,double y2)
{
return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}

bool cross(double &X1,double &Y1,double &X2,double &Y2,double R)
{
double A=(vx*vx+vy*vy),B=2*(x*vx+y*vy),C=x*x+y*y-(R+r)*(r+R);
double delta=B*B-4*A*C;
if(delta<eps) return false;
delta=sqrt(delta);

double k=(-B+delta)/(2*A);
if(k<-eps){
X1=X2=x;Y1=Y2=y;
return false;
}
else{
X2=k*vx+x,Y2=k*vy+y;
}
k=(-B-delta)/(2*A);
X1=k*vx+x,Y1=k*vy+y;
//printf("%.3f %.3f %.3f\n",X1,Y1,k);
return true;
}


int main()
{
while(cin>>Rm>>R>>r>>x>>y>>vx>>vy){
double x1,y1,x2,y2;
double ans=0;
double v=sqrt(vx*vx+vy*vy);
if(cross(x1,y1,x2,y2,Rm)){
//printf("%.3f %.3f %.3f %.3f ",x1,y1,x2,y2);
double dis=min(getdis(x1,y1,x,y),getdis(x2,y2,x,y));
ans+=dis/sqrt(vx*vx+vy*vy);
cross(x1,y1,x2,y2,R);
double d=min(getdis(x1,y1,x,y),getdis(x2,y2,x,y));
ans+=(dis+d)/sqrt(vx*vx+vy*vy);
if(getdis(x,y,0,0)>R+r) ans-=(3*d)/sqrt(vx*vx+vy*vy);
}
else if(cross(x1,y1,x2,y2,R)){

if(getdis(x,y,0,0)>R+r){
ans+=getdis(x1,y1,x2,y2)/v;
}
else{
if((x1-x)*vx>eps||(y1-y)*vy>eps){
ans+=getdis(x,y,x1,y1)/v;
}
else if((x2-x)*vx>eps||(y2-y)*vy>eps) ans+=getdis(x,y,x2,y2)/v;
}
}
printf("%.3f\n",ans);
}
}

D Arnold

题目描述

有一个$n\times n$的矩阵,$(i,j)$坐标处的值为$pair(i,j)$,每次操作将整个矩阵每个位置处的$pair(x,y)$改变为$pair((x+y)\ %n,(x+2y)\ %n)$,问改变多少次回到初始状态。

解题思路

发现这就是斐波那契数列的相邻两项,只需要求出斐波那契数列的循环节$ans$,如果$ans$是$2$的整数倍那么答案显然为$\frac{ans}2$;否则答案为$ans$。

现在考虑怎么求出模$n$意义下的循环节。由于模质数意义下的循环节比较好求,考虑将$n$质因数分解。设$n=p_1^{k_1}p_2^{k_2}…p_l^{k_l}$。我们假设已经求出来模$p_i$意义下斐波那契数列的循环节为$cir_i$,那么模$p_i^{k_i}$意义下的循环节显然可以设置为$len_i=cir_i\times p_i^{k_i-1}$。于是模$n$意义下的循环节就是$lcm(len_i)$。

现在要考虑求模$p$意义下的循环节。很容易写出转移方程:

设$A=\left(\begin{aligned}1\space {1}\\ 1\space{0}\end{aligned}\right) $,有$A^n\left(\begin{aligned} f_2 \\ f_1\end{aligned}\right)=\left(\begin{aligned} f_{n+2} \\ f_{n+1}\end{aligned}\right)$

设循环节为$n$,即求$A^n=E$的最小$n$。

将$A$相似对角化:$A=T^{-1}BT,B=\left(\begin{aligned}\lambda_1 \space {0}\\ 0\space{\lambda_2}\end{aligned}\right)$,其中特征值$\lambda_1=\frac{1+\sqrt 5}2$,$\lambda_2=\frac{1-\sqrt 5}2$。

于是显然有$B^n=E\Leftrightarrow A^n=E\Leftrightarrow (\lambda_1^n\equiv 1\space mod\space p \space and\space\lambda_2^n\equiv 1\space mod\space p)$。

分两种情况讨论:

  1. $5$是$p$的二次剩余。此时有$\lambda_1\equiv const_1,\lambda_2\equiv const_2$,$const_1,const_2\in integer$。故$\lambda_1^{p-1}\equiv\lambda_2^{p-1}\equiv 1\space mod\space p$。从小到大枚举$p-1$的因数求出最短循环节即可。

  2. $5$不是$p$的二次剩余。这时候有$5^{\frac{p-1}2}\equiv -1\space mod\space p$即$(\sqrt5)^{p-1}\equiv -1\space mod\space p$,这种情况比较麻烦,我们将$\lambda^n$用二项式定理展开,以$\lambda_1^n$为例:
    $\lambda_1^n$

    $=\frac1{2^n}(1+\sqrt5)^{n}$

    $=\frac1{2^n}(1+n\sqrt5+\frac{n(n-1)}2\sqrt5^2+…+\frac{n(n-1)}2\sqrt5^{n-2}+n\sqrt5^{n-1}+\sqrt5^{n})$

    我们不妨取$n=p+1$,这时有

    $\lambda_1^{p+1}$

    $=\frac1{4\times 2^{p-1}}(1+(p+1)\sqrt5+\frac{p(p+1)}2\sqrt5^2+…+\frac{p(p+1)}2\sqrt5^{p-1}+(p+1)\sqrt5^{p}+\sqrt5^{p+1})$

    $\equiv \frac14 (1+(p+1)\sqrt5 +(p+1)\sqrt5^p+\sqrt5^{p+1})\space mod\space p$

    $\equiv \frac14 (1+(p+1)\sqrt5+(p+1)\sqrt5(-1)+5\times (-1))\space mod\space p$

    $\equiv -1\space mod\space p$

    于是$\lambda_1^{2(p+1)}\equiv 1 \space mod\space p$

    枚举$2(p+1)$的因数即可。

当时直接贴上循环节和暴力程序比了一下发现只有$2$的情况需要保留循环节,其余情况都需要输出循环节的$\frac12$倍。这里的原理大概是,矩阵$A$的行列式为$-1$,只有模$2$意义下$-1\equiv1$,所以其余情况要想让$A^n=E$,$n$必然为偶数。

AC代码

点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define M 2
struct mt{ll m[M][M];};
mt E={{{1,0},{0,1}}},A={{{1,1},{1,0}}};
ll qmul(ll a,ll b,ll mod){
ll res=0;
while(b){
if(b&1)res=(res+a)%mod;
a=a*2%mod;b>>=1;
}
return res;
}
mt mul(mt a,mt b,ll mod){
mt c;
int i,j,k;
for(i=0;i<M;i++){
for(j=0;j<M;j++){
c.m[i][j]=0;
for(k=0;k<M;k++)c.m[i][j]=(c.m[i][j]+(__int128)a.m[i][k]*b.m[k][j]%mod)%mod;
}
}
return c;
}
mt qpmt(mt a,ll k,ll mod){
mt ans=E;
for(;k;k>>=1,a=mul(a,a,mod))if(k&1)ans=mul(ans,a,mod);
return ans;
}
#define N 70005
int p[N],isnp[N],tot;//大小
void sieve(){
int i,j;isnp[0]=isnp[1]=1;
for(i=2;i<N;i++){
if(!isnp[i])p[tot++]=i;
for(j=0;1LL*p[j]*i<N&&j<tot;j++){
isnp[i*p[j]]=1;
if(i%p[j]==0)break;
}
}
}
ll qp(ll x,ll p,ll mod){
ll ans=1;x%=mod;
for(;p;p>>=1,x=(__int128)x*x%mod)if(p&1)ans=(__int128)ans*x%mod;
return ans;
}
int isQuadratic(ll a,ll mod){//a是mod的二次剩余(a^{(mod-1)/2}=1)
if(qp(a,(mod-1)/2,mod)==1)return 1;
else return 0;
}
ll num[N],pri[N];
int splitPrime(ll n,ll pri[],ll num[]){//分解质因数
int i,now=0;
for(i=0;1LL*p[i]*p[i]<=n;i++){
if(n%p[i]==0){
int cnt=0;
while(n%p[i]==0)cnt++,n/=p[i];
num[now]=cnt;
pri[now]=p[i];
now++;
}
}
if(n>1){
pri[now]=n;
num[now]=1;
now++;
}
return now;
}
ll fac[N];
int findFactor(ll n){
int i,now=0;
for(i=1;1LL*i*i<=n;i++){
if(n%i==0){
fac[now++]=i;
if(1LL*i*i!=n)fac[now++]=n/i;
}
}
return now;
}
ll findloop(ll n){
int i,j,cnt=splitPrime(n,pri,num);
ll ans=1;//lcm(len_i)
for(i=0;i<cnt;i++){
ll now=1;//len_i
if(pri[i]==2)now=3;
else if(pri[i]==5)now=20;
else{
int cntFac=0;
if(isQuadratic(5,pri[i]))cntFac=findFactor(pri[i]-1);
else cntFac=findFactor((pri[i]+1)*2);
sort(fac,fac+cntFac);
for(j=0;j<cntFac;j++){
mt a=qpmt(A,fac[j],pri[i]);
if(a.m[0][0]==1&&a.m[1][1]==1&&!a.m[0][1]&&!a.m[1][0]){
now=fac[j];
break;
}
}
}
//now:c_i
for(j=1;j<num[i];j++)now*=pri[i];
ans=ans/__gcd(ans,now)*now;
}
return ans;
}
int main(){
ll n;
sieve();
while(~scanf("%lld",&n)){
if(n==2)printf("3\n");
else printf("%lld\n",findloop(n)/2);
}
return 0;
}

E Easy Problem Once More

题目描述

解题思路

AC代码

点击
1
2


F Winter’s Coming

题目描述

解题思路

AC代码

点击
1
2


G Graph Reconstruction

题目描述

给定度序列,还原简单图。如果有多解,输出两组解。

解题思路

根据度序列排序,从大到小枚举度序列中的点,向后连边,即可求出一组解。过程中任意找一个最后两个度相等的节点,交换一下连边即可求出第二组解。

$SBspj$,再见

AC代码

点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
struct P{
int deg,i;
bool operator<(const P&a)const{return deg>a.deg||(deg==a.deg&&i>a.i);}
}a[110],b[110];
pair<int,int>E[10010],E2[10010];
int tot,tot2;
int n,sumdeg;
int dfs(int now,int sumd){
int i;
if(now==n){
for(i=0;i<n;i++)if(a[i].deg)return 0;
return 1;
}
sumd-=a[now].deg*2;
if(sumd<0)return 0;
for(i=now+1;i<=now+a[now].deg;i++){
E[tot++]=make_pair(a[now].i,a[i].i);
a[i].deg--;
if(a[i].deg<0)return 0;
}
a[now].deg=0;
sort(a+now+1,a+n);
return dfs(now+1,sumd);
}
int dfs2(int now,int sumd,int flag){//flag:有没有改
int i;
if(now==n)return flag;//一定有解
sumd-=a[now].deg*2;
if(sumd<0)return 0;
for(i=now+1;i<now+a[now].deg;i++){
E2[tot2++]=make_pair(a[now].i,a[i].i);
a[i].deg--;
}
if(a[now].deg>0){
a[now].deg=0;
if(!flag&&a[i].deg&&a[i].deg==a[i+1].deg){
a[i+1].deg--;
E2[tot2++]=make_pair(a[now].i,a[i+1].i);
sort(a+now+1,a+n);
return dfs2(now+1,sumd,1);
}
E2[tot2++]=make_pair(a[now].i,a[i].i);
a[i].deg--;
sort(a+now+1,a+n);
}
return dfs2(now+1,sumd,flag);
}
int main(){
int i;
//freopen("in.txt","r",stdin);
while(~scanf("%d",&n)){
tot=tot2=0;
sumdeg=0;
for(i=0;i<n;i++)scanf("%d",&a[i].deg),a[i].i=i+1,b[i]=a[i],sumdeg+=a[i].deg;
sort(a,a+n);
if(!dfs(0,sumdeg))printf("IMPOSSIBLE\n");
else{
for(i=0;i<n;i++)a[i]=b[i];
sort(a,a+n);
if(!dfs2(0,sumdeg,0)){
printf("UNIQUE\n");
printf("%d %d\n",n,tot);
if(tot){
printf("%d",E[0].first);
for(i=1;i<tot;i++)printf(" %d",E[i].first);
}
printf("\n");
if(tot){
printf("%d",E[0].second);
for(i=1;i<tot;i++)printf(" %d",E[i].second);
}
printf("\n");
//debug(0);
}else{
printf("MULTIPLE\n");
printf("%d %d\n",n,tot);
if(tot){
printf("%d",E[0].first);
for(i=1;i<tot;i++)printf(" %d",E[i].first);
}
printf("\n");
if(tot){
printf("%d",E[0].second);
for(i=1;i<tot;i++)printf(" %d",E[i].second);
}
printf("\n");
printf("%d %d\n",n,tot2);
if(tot2){
printf("%d",E2[0].first);
for(i=1;i<tot2;i++)printf(" %d",E2[i].first);
}
printf("\n");
if(tot2){
printf("%d",E2[0].second);
for(i=1;i<tot2;i++)printf(" %d",E2[i].second);
}
printf("\n");
//debug(1);
}
}
}
return 0;
}

H Skycity

题目描述

用木板围住圆,要求木板长度均大于某个值,求最小消耗。

解题思路

转化成正多边形计算即可。

AC代码

点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <algorithm>
#include<iostream>
#include <cmath>
using namespace std;
const int ms = 50000 + 10;
typedef long long ll;

int r, R, H, F, S;
double h, s;
const double pi = acos(-1.0);

double cal(int f)
{
double rr = 1.0 * (R - r) / F * f + r;
double top = floor(pi / atan2(s, (2 * rr)));
return 2 * rr * tan(pi / top) *top;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
while (cin >> R >> r >> H >> F >> S)
{
h = 1.0 * H / F;
s = S / h;
double res = 0;
for (int i = 0; i < F; ++i)
{
res += cal(i)*h;
}
printf("%.3lf\n", res);
}
}

I LIKE vs CANDLE

题目描述

给一棵树,每个点有可正可负的权值,每次可以花费$x$翻转一个未被翻转过的节点的子树,或者花费$y$反转一个已被翻转过的节点的子树。翻转某棵子树的意思就是,把这个子树所有节点的权值乘$-1$。求最终所有权值和减去总花费的最大值。

解题思路

树形$dp$记录下每个节点分别修改、不修改造成的影响即可。

AC代码 - by Mogg

点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <algorithm>
#include<iostream>
#include <vector>
using namespace std;
const int ms = 50000 + 10;
typedef long long ll;
int n, X, Y;
vector<int> g[ms];
int flag[ms], dp[ms][2], power[ms];
void dfs(int x, int s)
{
if (flag[x]) s ^= 1;
if (s)
power[x] = -power[x];
dp[x][0] = power[x], dp[x][1] = -power[x];
for (int i : g[x])
{
dfs(i, s);
dp[x][0] += max(dp[i][0], dp[i][1] - (flag[i] ? Y : X));
dp[x][1] += max(dp[i][1], dp[i][0] - (flag[i] ? Y : X));
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
while (cin >> n >> X >> Y)
{
for (int i = 1; i <= n; ++i)
{
int par, l;
cin >> power[i] >> par >> flag[i] >> l;
if (l) power[i] = -power[i];
g[par].push_back(i);
}
dfs(0, 0);
if (dp[0][0] < 0)
cout << "HAHAHAOMG\n";
else
cout << dp[0][0] << "\n";
for (int i = 0; i <= n; ++i)
g[i].clear();
}
}

J Josephina and RPG

题目描述

有$n$个人,$p_{ij}$表示$i$打败$j$的概率。初始时选择其中一个人$x$。有$m$个对手$a_1…a_m$依次出现,每次打赢$a_i$后可以选择把当前选手换成$a_i$或者不换。求打败所有对手的概率。

解题思路

$dp[i][j]$表示打到第$i$场,当前出战的选手是$j$的获胜概率。转移显然。

AC代码 - by qxforever

点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
const int maxn = 133;
double p[maxn][maxn];
double dp[10002][maxn];
int a[10002];
int m,n;
int main()
{
while(~scanf("%d",&m)){
n=m*(m-1)*(m-2)/6;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%lf",&p[i][j]);
int N;cin >> N ;
memset(dp,0,sizeof(dp));
for(int i=1;i<=N;i++) scanf("%d",a+i);
for(int i=0;i<maxn;i++) dp[0][i]=1;
for(int i=1;i<=N;i++){
int t=a[i];
dp[i][t]=dp[i-1][t]*0.5;
for(int j=0;j<n;j++){
dp[i][j]=max(dp[i][j],dp[i-1][j]*p[j][t]);
dp[i][t]=max(dp[i][t],dp[i][j]);
}
}
double ans=0;
for(int i=0;i<n;i++) ans=max(ans,dp[N][i]);
printf("%.7f\n",ans);
}
}

K Pocket Cube

题目描述

转$2\times 2$的魔方,问$n$次以内最多能拼好几个面。

解题思路

巨麻烦的爆搜。

AC代码 - by Mogg

点击
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include<algorithm>
#include<iostream>
using namespace std;

typedef long long ll;
int color[24], n, ans;
int check()
{
int res = 0;
res += (color[0] == color[1]) && (color[1] == color[2]) && (color[2] == color[3]);
res += (color[4] == color[5]) && (color[5] == color[10]) && (color[10] == color[11]);
res += (color[6] == color[7]) && (color[7] == color[12]) && (color[12] == color[13]);
res += (color[8] == color[9]) && (color[9] == color[14]) && (color[14] == color[15]);
res += (color[16] == color[17]) && (color[17] == color[18]) && (color[18] == color[19]);
res += (color[20] == color[21]) && (color[21] == color[22]) && (color[22] == color[23]);
return res;
}
void rt1()
{
int t1 = color[0], t2 = color[2];
color[0] = color[20], color[2] = color[22];
color[20] = color[16], color[22] = color[18];
color[16] = color[6], color[18] = color[12];
color[6] = t1, color[12] = t2;
t1 = color[4];
color[4] = color[10], color[10] = color[11];
color[11] = color[5], color[5] = t1;
}
void rt2()
{
int t1 = color[0], t2 = color[2];
color[0] = color[6], color[2] = color[12];
color[6] = color[16], color[12] = color[18];
color[16] = color[20], color[18] = color[22];
color[20] = t1, color[22] = t2;
t1 = color[4];
color[4] = color[5], color[5] = color[11];
color[11] = color[10], color[10] = t1;
}
void rt3()
{
int t1 = color[2], t2 = color[3];
color[2] = color[11], color[3] = color[5];
color[11] = color[17], color[5] = color[16];
color[17] = color[8], color[16] = color[14];
color[8] = t1, color[14] = t2;
t1 = color[6];
color[6] = color[12], color[12] = color[13];
color[13] = color[7], color[7] = t1;
}
void rt4()
{
int t1 = color[2], t2 = color[3];
color[2] = color[8], color[3] = color[14];
color[8] = color[17], color[14] = color[16];
color[17] = color[11], color[16] = color[5];
color[11] = t1, color[5] = t2;
t1 = color[6];
color[6] = color[7], color[7] = color[13];
color[13] = color[12], color[12] = t1;
}
void rt5()
{
int t1 = color[22], t2 = color[23];
color[22] = color[5], color[23] = color[4];
color[5] = color[7], color[4] = color[6];
color[7] = color[9], color[6] = color[8];
color[9] = t1, color[8] = t2;
t1 = color[0];
color[0] = color[2], color[2] = color[3];
color[3] = color[1], color[1] = t1;
}
void rt6()
{
int t1 = color[22], t2 = color[23];
color[22] = color[9], color[23] = color[8];
color[9] = color[7], color[8] = color[6];
color[7] = color[5], color[6] = color[4];
color[5] = t1, color[4] = t2;
t1 = color[0];
color[0] = color[1], color[1] = color[3];
color[3] = color[2], color[2] = t1;
}
void dfs(int x, int o)
{
ans = max(ans, check());
if (ans == 6 || x > n) return;
if (o != 2)
{
rt1();
dfs(x + 1, 1);
rt2();
}
if (o != 1)
{
rt2();
dfs(x + 1, 2);
rt1();
}
if (o != 4)
{
rt3();
dfs(x + 1, 3);
rt4();
}
if (o != 3)
{
rt4();
dfs(x + 1, 4);
rt3();
}
if (o != 6)
{
rt5();
dfs(x + 1, 5);
rt6();
}
if (o != 5)
{
rt6();
dfs(x + 1, 6);
rt5();
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
while (cin >> n)
{
ans = 0;
for (int i = 0; i < 24; ++i)
{
cin >> color[i];
}
dfs(1, 0);
cout << ans << "\n";
}
}