鋪地毯
題目描述
為了準(zhǔn)備一個(gè)獨(dú)特的頒獎(jiǎng)典禮瑟枫，組織者在會(huì)場(chǎng)的一片矩形區(qū)域（可看做是平面直角坐標(biāo)系的第一象限）鋪上一些矩形地毯羽杰。一共有 n 張地毯语泽，編號(hào)從 1 到n 《骷保現(xiàn)在將這些地毯按照編號(hào)從小到大的順序平行于坐標(biāo)軸先后鋪設(shè)，后鋪的地毯覆蓋在前面已經(jīng)鋪好的地毯之上氯庆。
地毯鋪設(shè)完成后弟孟，組織者想知道覆蓋地面某個(gè)點(diǎn)的最上面的那張地毯的編號(hào)。注意：在矩形地毯邊界和四個(gè)頂點(diǎn)上的點(diǎn)也算被地毯覆蓋颊埃。
輸入輸出格式
輸入格式：
輸入文件名為carpet.in 随珠。
輸入共n+2 行。
第一行实昨，一個(gè)整數(shù)n 洞豁，表示總共有 n 張地毯。
接下來的n 行中，第 i+1 行表示編號(hào)i 的地毯的信息丈挟，包含四個(gè)正整數(shù) a 刁卜，b ，g 曙咽，k 蛔趴，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開，分別表示鋪設(shè)地毯的左下角的坐標(biāo)（a 例朱，b ）以及地毯在x軸和y 軸方向的長(zhǎng)度孝情。
第n+2 行包含兩個(gè)正整數(shù) x 和y，表示所求的地面的點(diǎn)的坐標(biāo)（x 洒嗤，y）箫荡。
輸出格式：
輸出文件名為carpet.out 。
輸出共1 行渔隶，一個(gè)整數(shù)羔挡，表示所求的地毯的編號(hào)；若此處沒有被地毯覆蓋則輸出-1 间唉。
輸入輸出樣例
輸入樣例#1：
3
1 0 2 3
0 2 3 3
2 1 3 3
2 2
輸出樣例#1：
3
輸入樣例#2：
3
1 0 2 3
0 2 3 3
2 1 3 3
4 5
輸出樣例#2：
-1
說明
【樣例解釋1】
如下圖绞灼，1 號(hào)地毯用實(shí)線表示，2 號(hào)地毯用虛線表示终吼，3 號(hào)用雙實(shí)線表示镀赌，覆蓋點(diǎn)（2,2）的最上面一張地毯是 3 號(hào)地毯。
【數(shù)據(jù)范圍】
對(duì)于30% 的數(shù)據(jù)际跪，有 n ≤2 商佛；
對(duì)于50% 的數(shù)據(jù)，0 ≤a, b, g, k≤100姆打；
對(duì)于100%的數(shù)據(jù)良姆，有 0 ≤n ≤10,000 ，0≤a, b, g, k ≤100,000幔戏。
思路
先把所有的地毯離線玛追，然后讀入所求位置之后將地毯倒著來，當(dāng)前地毯覆蓋目標(biāo)點(diǎn)闲延，輸出即可
代碼
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int n,a[11000],b[11000],g[11000],k[11000],x,y;
int main(){
scanf("%d",&n);
for (int i = 1;i <= n;i++){
scanf("%d%d%d%d",&a[i],&b[i],&g[i],&k[i]);
}
scanf("%d%d",&x,&y);
for (int i = n;i >= 1;i--){
int you = a[i] + g[i];
int shang = b[i] + k[i];
if (x >= a[i] && y >= b[i] && x <= you && y <= shang)
{
printf("%d\n",i);
return 0;
}
}
printf("-1\n");
return 0;
}
思路
首先弄懂樣例痊剖，然后從簡(jiǎn)單數(shù)據(jù)入手找規(guī)律。
（ax+by）2=(a*x)2+2abxy+(b*y)^2
（ax+by）3=(a*x)3+3(a^2)b(x^2)y+3a(b2)*x*(y2)+(b*y)^3
（ax+by）4=(a*x)4+4(a^3)b(x^3)y+6(a^2)(b2)*(x2)(y^2)+4a(b^3)x(y^3)+(by)^3
（ax+by）^5=......
通過這幾個(gè)簡(jiǎn)單的公式可以得出(xn)*(ym)的系數(shù)為t(a^n)(b^m),t值如下所示：
1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
.........
其實(shí)就是楊輝三角（當(dāng)然也是所有的組合情況C(k,n)）
若f[i,j]表示(a*x+b*y)^i展開后的系數(shù)
(a^n)*(b^m)的系數(shù)為f[i,i-n+1]
又
f[i,j]:=f[i-1,j-1]+f[i-1,j];
結(jié)果： ans=f[k,k-n+1](a^n)(b^m)
由于題目要求輸出對(duì)10007 取模后的結(jié)果垒玲，則有：
f[i,j]:=（(f[i-1,j-1] mod 10007)+(f[i-1,j]mod 10007))mod 10007;
a^n = ((a^(N-1))mod 10007a)mod 10007
b^m = ((b^(m-1))mod 10007b)mod 10007
(a^n可以邊乘邊取余數(shù)的方法做陆馁，也可用快速冪）。
注意：邊界條件k=0合愈，k=n等叮贩。
代碼
#include<iostream>
#include<cstdio>
#define MAXN 1000+10
#define LL long long
using namespace std;
LL aa[MAXN][MAXN];
LL a,b,k,n,m;
LL ans;
void ready()
{
for(int i=1;i<=k+1;i++)
{
for(int j=1;j<=i;j++)
{
if(j==1||i==j)
{
aa[i][j]=1;
continue;
}
aa[i][j]=(aa[i-1][j]+aa[i-1][j-1])%10007;
}
}
}
void readdata()
{
scanf("%lld%lld%lld%lld%lld\n",&a,&b,&k,&n,&m);
}
int main()
{
readdata();
ready();
int cja=1;
for(int i=1;i<=n;i++)
cja=(cja%10007)*(a%10007)%10007;
int cjb=1;
for(int i=1;i<=m;i++)
cjb=(cjb%10007)*(b%10007)%10007;
ans=(cjb*cja)%10007;
ans=(ans*aa[k+1][n+1])%10007;
printf("%d\n",ans);
}
選擇客棧
題目描述
麗江河邊有n 家很有特色的客棧击狮，客棧按照其位置順序從 1 到n 編號(hào)。每家客棧都按照某一種色調(diào)進(jìn)行裝飾（總共 k 種益老，用整數(shù) 0 ~ k-1 表示）彪蓬，且每家客棧都設(shè)有一家咖啡店，每家咖啡店均有各自的最低消費(fèi)捺萌。
兩位游客一起去麗江旅游档冬，他們喜歡相同的色調(diào)，又想嘗試兩個(gè)不同的客棧互婿，因此決定分別住在色調(diào)相同的兩家客棧中捣郊。晚上辽狈，他們打算選擇一家咖啡店喝咖啡慈参，要求咖啡店位于兩人住的兩家客棧之間（包括他們住的客棧），且咖啡店的最低消費(fèi)不超過 p 刮萌。
他們想知道總共有多少種選擇住宿的方案驮配，保證晚上可以找到一家最低消費(fèi)不超過 p元的咖啡店小聚。
輸入輸出格式
輸入格式：
輸入文件hotel.in着茸，共n+1 行壮锻。
第一行三個(gè)整數(shù)n ，k 涮阔，p猜绣，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開，分別表示客棧的個(gè)數(shù)敬特，色調(diào)的數(shù)目和能接受的最低消費(fèi)的最高值掰邢；
接下來的n 行，第 i+1 行兩個(gè)整數(shù)伟阔，之間用一個(gè)空格隔開辣之，分別表示 i 號(hào)客棧的裝飾色調(diào)和i 號(hào)客棧的咖啡店的最低消費(fèi)。
輸出格式：
輸出文件名為hotel.out皱炉。
輸出只有一行怀估，一個(gè)整數(shù)，表示可選的住宿方案的總數(shù)合搅。
輸入輸出樣例
輸入樣例#1：
5 2 3
0 5
1 3
0 2
1 4
1 5
輸出樣例#1：
3
說明
【輸入輸出樣例說明】
- 2 人要住同樣色調(diào)的客棧多搀，所有可選的住宿方案包括：住客棧①③，②④灾部，②⑤康铭，④⑤
- 但是若選擇住4 、5 號(hào)客棧的話梳猪，4 麻削、5 號(hào)客棧之間的咖啡店的最低消費(fèi)是4 蒸痹，而兩人能承受的最低消費(fèi)是3 元，所以不滿足要求呛哟。因此只有前 3 種方案可選叠荠。
【數(shù)據(jù)范圍】
對(duì)于30% 的數(shù)據(jù)，有 n ≤100扫责；
對(duì)于50% 的數(shù)據(jù)榛鼎，有 n ≤1,000；
對(duì)于100%的數(shù)據(jù)鳖孤，有 2 ≤n ≤200,000者娱，0<k ≤50，0≤p ≤100 苏揣， 0 ≤最低消費(fèi)≤100黄鳍。
思路
首先我們看，
- 當(dāng)找到一個(gè)旅店在右邊平匈，若是其左邊有一個(gè)符合要求的咖啡店框沟，那么再往左邊看，
- 如果有一個(gè)顏色相同的旅店增炭，那么就算是一種住宿方法了忍燥，那么如果以這個(gè)右邊的旅店作為對(duì)應(yīng)點(diǎn)，將所有在左邊而且顏色與之相同的旅店數(shù)相加隙姿，就能得出很多種住宿方法了梅垄。
- 那么用這個(gè)辦法，用所有的對(duì)應(yīng)點(diǎn)對(duì)應(yīng)過去输玷，就能最快的時(shí)間內(nèi)找出所用的酒店了队丝。a數(shù)組是記錄同一種顏色中的酒店所出現(xiàn)的最后一次的位置；b數(shù)組記錄同一種顏色的酒店的出現(xiàn)次數(shù)饲嗽，而c數(shù)組則是臨時(shí)記錄當(dāng)前同樣顏色的酒店出現(xiàn)的次數(shù)炭玫，也就是為找對(duì)應(yīng)點(diǎn)而進(jìn)行的臨時(shí)記錄
代碼
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,k,p,m,ans;
int a[200010],b[200010],c[200010];
int main()
{
scanf("%d%d%d",&n,&k,&p);
for (int i = 1; i <= n; i++)
{
int k, q;
scanf("%d%d",&k,&q);
if (q <= p) m = i; //如果咖啡店的最低消費(fèi)地于標(biāo)準(zhǔn)，那么記錄其位置
if (m >= a[k]) c[k] = b[k]; //如果在當(dāng)前顏色的酒店之前有出現(xiàn)過同樣顏色的酒店那么記錄當(dāng)前同種顏色的酒店的出現(xiàn)次數(shù)
a[k] = i; //記錄同樣顏色的酒店最后一次的出現(xiàn)位置
ans+=c[k]; //每一個(gè)酒店都可以作為對(duì)應(yīng)點(diǎn)貌虾，所以不需要再去加上任何的判斷吞加，記錄住宿的方法
b[k]++; //記錄出現(xiàn)次數(shù)的總數(shù)
}
printf("%d",ans);
return 0;
}
聰明的質(zhì)檢員
題目描述 Description
小 T 是一名質(zhì)量監(jiān)督員，最近負(fù)責(zé)檢驗(yàn)一批礦產(chǎn)的質(zhì)量尽狠。這批礦產(chǎn)共有n 個(gè)礦石衔憨，從1到n 逐一編號(hào)，每個(gè)礦石都有自己的重量wi 以及價(jià)值vi袄膏。檢驗(yàn)礦產(chǎn)的流程是：見圖
若這批礦產(chǎn)的檢驗(yàn)結(jié)果與所給標(biāo)準(zhǔn)值S 相差太多践图，就需要再去檢驗(yàn)另一批礦產(chǎn)。小T不想費(fèi)時(shí)間去檢驗(yàn)另一批礦產(chǎn)沉馆，所以他想通過調(diào)整參數(shù)W 的值码党，讓檢驗(yàn)結(jié)果盡可能的靠近標(biāo)準(zhǔn)值S德崭，即使得S-Y 的絕對(duì)值最小。請(qǐng)你幫忙求出這個(gè)最小值揖盘。
輸入輸出
輸入描述 Input Description
第一行包含3個(gè)整數(shù) n眉厨，m，S兽狭，分別表示礦石的個(gè)數(shù)憾股、區(qū)間的個(gè)數(shù)和標(biāo)準(zhǔn)值。接下來的 n 行箕慧，每行2 個(gè)整數(shù)服球，中間用空格隔開，第i+1 行表示i 號(hào)礦石的重量wi 和價(jià)值vi 颠焦。接下來的 m 行斩熊，表示區(qū)間，每行2 個(gè)整數(shù)蒸健，中間用空格隔開座享，第i+n+1 行表示區(qū)間[Li,Ri]的兩個(gè)端點(diǎn)Li 和Ri婉商。注意：不同區(qū)間可能重合或相互重疊似忧。
輸出描述 Output Description
輸出只有一行，包含一個(gè)整數(shù)丈秩，表示所求的最小值盯捌。
樣例輸入 Sample Input
5 3 15
1 5
2 5
3 5
4 5
5 5
1 5
2 4
3 3
## 樣例
樣例輸出 Sample Output
10
數(shù)據(jù)范圍及提示 Data Size & Hint
解釋
當(dāng) W 選4 的時(shí)候，三個(gè)區(qū)間上檢驗(yàn)值分別為20蘑秽、5饺著、0，這批礦產(chǎn)的檢驗(yàn)結(jié)果為25肠牲，此時(shí)與標(biāo)準(zhǔn)值S 相差最小為10幼衰。
數(shù)據(jù)范圍
對(duì)于 10%的數(shù)據(jù)，有1≤n缀雳，m≤10渡嚣；
對(duì)于 30%的數(shù)據(jù)，有1≤n肥印，m≤500识椰；
對(duì)于 50%的數(shù)據(jù)，有1≤n深碱，m≤5,000腹鹉；
對(duì)于 70%的數(shù)據(jù)，有1≤n敷硅，m≤10,000功咒；
對(duì)于 100%的數(shù)據(jù)愉阎，有1≤n，m≤200,000力奋，0 < wi, vi≤10^6诫硕，0 < S≤10^12，1≤Li≤Ri≤n刊侯。
思路
首先章办，我們可以知道每一個(gè)區(qū)間的價(jià)值都是遞減的：隨著W的增加，滿足條件的礦石數(shù)量減少滨彻，價(jià)值和減少藕届，所以總的價(jià)值和也減少。
那么我們可以二分W(礦石最低重量)亭饵，然后統(tǒng)計(jì)滿足條件的礦石的數(shù)量休偶、價(jià)值的前綴和。
總時(shí)間復(fù)雜度O(mlogn)
代碼
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define mod 1000000007
#define ll long long
#define inf (1LL<<60)
using namespace std;
ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,m,mx;
ll S,ans=inf;
int l[200005],r[200005];
int w[200005],v[200005];
ll sum[200005],cnt[200005];
ll cal(int W)
{
ll tmp=0;
for(int i=1;i<=n;i++)
{
sum[i]=sum[i-1];
cnt[i]=cnt[i-1];
if(w[i]>=W)
{
sum[i]+=v[i];
cnt[i]++;
}
}
for(int i=1;i<=m;i++)
{
tmp+=(cnt[r[i]]-cnt[l[i]-1])*(sum[r[i]]-sum[l[i]-1]);
}
return tmp;
}
int main()
{
n=read();m=read();S=read();
for(int i=1;i<=n;i++)
w[i]=read(),v[i]=read();
for(int i=1;i<=n;i++)
mx=max(mx,w[i]);
for(int i=1;i<=m;i++)
l[i]=read(),r[i]=read();
int l=0,r=mx+1;
while(l<=r)
{
int mid=(l+r)>>1;
ll t=cal(mid);
ans=min(ans,abs(t-S));
if(t<S)r=mid-1;
else l=mid+1;
}
printf("%lld\n",ans);
return 0;
}
Mayan游戲
題目描述
Mayan puzzle是最近流行起來的一個(gè)游戲辜羊。游戲界面是一個(gè) 7 行5 列的棋盤踏兜，上面堆放著一些方塊，方塊不能懸空堆放八秃，即方塊必須放在最下面一行碱妆，或者放在其他方塊之上。游戲通關(guān)是指在規(guī)定的步數(shù)內(nèi)消除所有的方塊昔驱，消除方塊的規(guī)則如下：
1 . 每步移動(dòng)可以且僅可以沿橫向（即向左或向右）拖動(dòng)某一方塊一格：當(dāng)拖動(dòng)這一方塊時(shí)疹尾，如果拖動(dòng)后到達(dá)的位置（以下稱目標(biāo)位置）也有方塊，那么這兩個(gè)方塊將交換位置（參見輸入輸出樣例說明中的圖6 到圖7 ）骤肛；如果目標(biāo)位置上沒有方塊纳本，那么被拖動(dòng)的方塊將從原來的豎列中抽出，并從目標(biāo)位置上掉落（直到不懸空腋颠，參見下面圖1 和圖2）繁成；
2 . 任一時(shí)刻，如果在一橫行或者豎列上有連續(xù)三個(gè)或者三個(gè)以上相同顏色的方塊淑玫，則它們將立即被消除（參見圖1 到圖3）巾腕。
注意：
a) 如果同時(shí)有多組方塊滿足消除條件，幾組方塊會(huì)同時(shí)被消除（例如下面圖4 混移，三個(gè)顏色為1 的方塊和三個(gè)顏色為 2 的方塊會(huì)同時(shí)被消除祠墅，最后剩下一個(gè)顏色為 2 的方塊）。
b) 當(dāng)出現(xiàn)行和列都滿足消除條件且行列共享某個(gè)方塊時(shí)歌径，行和列上滿足消除條件的所有方塊會(huì)被同時(shí)消除（例如下面圖5 所示的情形毁嗦，5 個(gè)方塊會(huì)同時(shí)被消除）。
3 . 方塊消除之后回铛，消除位置之上的方塊將掉落狗准，掉落后可能會(huì)引起新的方塊消除克锣。注意：掉落的過程中將不會(huì)有方塊的消除。
上面圖1 到圖 3 給出了在棋盤上移動(dòng)一塊方塊之后棋盤的變化腔长。棋盤的左下角方塊的坐標(biāo)為（0, 0 ）袭祟，將位于（3, 3 ）的方塊向左移動(dòng)之后，游戲界面從圖 1 變成圖 2 所示的狀態(tài)捞附，此時(shí)在一豎列上有連續(xù)三塊顏色為4 的方塊巾乳，滿足消除條件，消除連續(xù)3 塊顏色為4 的方塊后鸟召，上方的顏色為3 的方塊掉落胆绊，形成圖 3 所示的局面。
輸入輸出格式
輸入格式：
輸入文件mayan.in欧募，共 6 行压状。
第一行為一個(gè)正整數(shù)n ，表示要求游戲通關(guān)的步數(shù)跟继。
接下來的5 行种冬，描述 7*5 的游戲界面。每行若干個(gè)整數(shù)舔糖，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開娱两，每行以一個(gè)0 結(jié)束，自下向上表示每豎列方塊的顏色編號(hào)（顏色不多于10種剩盒，從1 開始順序編號(hào)谷婆，相同數(shù)字表示相同顏色）。
輸入數(shù)據(jù)保證初始棋盤中沒有可以消除的方塊辽聊。
輸出格式：
輸出文件名為mayan.out。
如果有解決方案期贫，輸出 n 行跟匆，每行包含 3 個(gè)整數(shù)x，y通砍，g 玛臂，表示一次移動(dòng)，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開封孙，其中（x 迹冤，y）表示要移動(dòng)的方塊的坐標(biāo)，g 表示移動(dòng)的方向虎忌，1 表示向右移動(dòng)泡徙，-1表示向左移動(dòng)。注意：多組解時(shí)膜蠢，按照 x 為第一關(guān)健字堪藐，y 為第二關(guān)健字莉兰，1優(yōu)先于-1 ，給出一組字典序最小的解礁竞。游戲界面左下角的坐標(biāo)為（0 糖荒，0 ）。
如果沒有解決方案模捂，輸出一行捶朵，包含一個(gè)整數(shù)-1。
輸入輸出樣例
輸入樣例#1：
3
1 0
2 1 0
2 3 4 0
3 1 0
2 4 3 4 0
輸出樣例#1：
2 1 1
3 1 1
3 0 1
說明
【輸入輸出樣例說明】
按箭頭方向的順序分別為圖6 到圖11
樣例輸入的游戲局面如上面第一個(gè)圖片所示狂男，依次移動(dòng)的三步是：（2 泉孩，1 ）處的方格向右移動(dòng)，（3并淋，1 ）處的方格向右移動(dòng)寓搬，（3 ，0）處的方格向右移動(dòng)县耽，最后可以將棋盤上所有方塊消除句喷。
【數(shù)據(jù)范圍】
對(duì)于30% 的數(shù)據(jù)，初始棋盤上的方塊都在棋盤的最下面一行兔毙；
對(duì)于100%的數(shù)據(jù)唾琼，0 < n≤5 。
思路
如果某種顏色的方塊只剩下1個(gè)或兩個(gè)澎剥，則無解锡溯。
如果某個(gè)方塊的左邊是有方塊的，則放棄搜索該方塊向左移動(dòng)的方案（此方案會(huì)在左邊方塊右移時(shí)被解決）
對(duì)于每個(gè)方塊:
- 若左右不相等哑姚，且可以右移祭饭，那么右移，并判斷合法性叙量；
- 若左邊為空倡蝙，且可以左移，那么左移绞佩，并判斷合法性寺鸥。
代碼
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100
using namespace std;
int n;
struct tnode{int a[5][7];
int ss[11];
}q[maxn+10];
struct node{int x,y,g;}ans[6];
int sum=0;
bool f[5][7];
bool ok(int p)
{
int i,j,k;
for(i=0;i<=4;i++)if(q[p].a[i][0]!=0)return 0;
return 1;
}
bool xiao(int p)
{
int i,j,k;
for(i=1;i<=10;i++)
if(q[p].ss[i]==1 || q[p].ss[i]==2)return 0;
return 1;
}
void copy(int x,int y)
{
int i,j,k;
for(i=0;i<=4;i++)
for(j=0;j<=6;j++)
q[x].a[i][j]=q[y].a[i][j];
for(k=1;k<=10;k++)q[x].ss[k]=q[y].ss[k];
}
bool drop(int p)
{
int i,j,k;
bool flag=0;
for(i=0;i<=4;i++)
for(j=1;j<=6;j++)
if(q[p].a[i][j]!=0)
{
k=j;
while(k>0 && q[p].a[i][k-1]==0)
{
swap(q[p].a[i][k],q[p].a[i][k-1]);
flag=1,k--;
}
}
return flag;
}
bool xiaoqu(int p)
{
memset(f,0,sizeof(f));
int i,j,k;
bool flag=0;
for(i=0;i<=6;i++)
for(j=0;j<=2;j++)
if(q[p].a[j][i]!=0 &&
q[p].a[j+1][i]==q[p].a[j][i] &&
q[p].a[j+2][i]==q[p].a[j][i]
)
f[j][i]=f[j+1][i]=f[j+2][i]=1;
for(i=0;i<=4;i++)
for(j=0;j<=4;j++)
if(q[p].a[i][j]!=0 &&
q[p].a[i][j+1]==q[p].a[i][j] &&
q[p].a[i][j+2]==q[p].a[i][j]
)
f[i][j]=f[i][j+1]=f[i][j+2]=1;
for(i=0;i<=4;i++)
for(j=0;j<=6;j++)if(f[i][j])
{
k=q[p].a[i][j];
q[p].ss[k]--;
q[p].a[i][j]=0;
flag=1;
}
return flag;
}
bool dfs(int step,int p)
{
if(step>n)return ok(p);
if(!xiao(p))return 0;
int i,j,k,x,y;
for(i=0;i<=4;i++)
for(j=0;j<=6;j++)
{
if(q[p].a[i][j]==0)break;
ans[step].x=i,ans[step].y=j;
if(i<4 && q[p].a[i][j]!=q[p].a[i+1][j])
{
ans[step].g=1,sum++;
copy(sum,p);
swap(q[sum].a[i][j],q[sum].a[i+1][j]);
while(drop(sum) || xiaoqu(sum));
if(dfs(step+1,sum))return 1;
sum--;
}
if(i>0 && q[p].a[i-1][j]==0)
{
ans[step].g=-1,sum++;
copy(sum,p);
swap(q[sum].a[i][j],q[sum].a[i-1][j]);
while(drop(sum) || xiaoqu(sum));
if(dfs(step+1,sum))return 1;
sum--;
}
}
return 0;
}
int main()
{
int i,j,k;
scanf("%d",&n);
for(i=0;i<=4;i++)
for(j=0;j<=7;j++)
{
scanf("%d",&k);
if(k==0)break;
q[0].a[i][j]=k;
q[0].ss[k]++;
}
if(dfs(1,0))
for(i=1;i<=n;i++)
printf("%d %d %d\n",ans[i].x,ans[i].y,ans[i].g);
else printf("-1\n");
return 0;
}
