【題目描述】

小 C 正在玩一個(gè)移球游戲，他面前有?n+1n+1?根柱子，柱子從?1～n+11～n+1?編號(hào)，其中11?號(hào)柱子、22?號(hào)柱子、· · ·、nn?號(hào)柱子上各有?mm?個(gè)球，它們自底向上放置在柱子上，n+1n+1號(hào)柱子上初始時(shí)沒有球。這?n×mn×m?個(gè)球共有?nn?種顏色，每種顏色的球各?mm?個(gè)。

常寧網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)建站！從網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、自適應(yīng)網(wǎng)站建設(shè)等網(wǎng)站項(xiàng)目制作，到程序開發(fā)，運(yùn)營(yíng)維護(hù)。創(chuàng)新互聯(lián)建站從2013年成立到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來保證我們的工作的順利進(jìn)行。專注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)建站。

初始時(shí)一根柱子上的球可能是五顏六色的，而小 C 的任務(wù)是將所有同種顏色的球移到同一根柱子上，這是唯一的目標(biāo)，而每種顏色的球最后放置在哪根柱子則沒有限制。

小 C 可以通過若干次操作完成這個(gè)目標(biāo)，一次操作能將一個(gè)球從一根柱子移到另一根柱子上。更具體地，將?xx?號(hào)柱子上的球移動(dòng)到?yy?號(hào)柱子上的要求為：

1.?xx?號(hào)柱子上至少有一個(gè)球；

2.?yy?號(hào)柱子上至多有?m?1m?1?個(gè)球；

3. 只能將?xx?號(hào)柱子最上方的球移到?yy?號(hào)柱子的最上方。

小 C 的目標(biāo)并不難完成，因此他決定給自己加加難度：在完成目標(biāo)的基礎(chǔ)上，使用的操作次數(shù)不能超過?820000820000。換句話說，小 C 需要使用至多 820000 次操作完成目標(biāo)。

小 C 被難住了，但他相信難不倒你，請(qǐng)你給出一個(gè)操作方案完成小 C 的目標(biāo)。合法的方案可能有多種，你只需要給出任意一種，題目保證一定存在一個(gè)合法方案。

【輸入】

第一行兩個(gè)用空格分隔的整數(shù)?nn，mm。分別表示球的顏色數(shù)、每種顏色球的個(gè)數(shù)。

接下來?nn?行每行?mm?個(gè)用單個(gè)空格分隔的整數(shù)，第?ii?行的整數(shù)按自底向上的順序依次給出了?ii?號(hào)柱子上的球的顏色。

【輸出】

本題采用自定義校驗(yàn)器（special judge）評(píng)測(cè)。

你的輸出的第一行應(yīng)該僅包含單個(gè)整數(shù)?kk，表示你的方案的操作次數(shù)。你應(yīng)保證0≤k≤8200000≤k≤820000。

接下來?kk?行每行你應(yīng)輸出兩個(gè)用單個(gè)空格分隔的正整數(shù)?xx,?yy，表示這次操作將?xx?號(hào)柱子最上方的球移動(dòng)到?yy?號(hào)柱子最上方。你應(yīng)保證?1≤x,y≤n+11≤x,y≤n+1?且?xx≠yy。

【輸入樣例】

2 3
1 1 2
2 1 2

【輸出樣例】

6
1 3
2 3
2 3
3 1
3 2
3 2

【提示】

【樣例解釋】

柱子中的內(nèi)容為：按自底向上的順序依次給出柱子上每個(gè)球的顏色。

操作	1號(hào)柱子	2號(hào)柱子	3號(hào)柱子
初始	1 1 2	2 1 2
1 3	1 1	2 1 2	2
2 3	1 1	2 1	2 2
2 3	1 1	2	2 2 1
3 1	1 1 1	2	2 2
3 2	1 1 1	2 2	2
3 2	1 1 1	2 2 2

【數(shù)據(jù)范圍】

對(duì)于所有測(cè)試點(diǎn)，保證?2≤n≤502≤n≤50，2≤m≤4002≤m≤400。

【校驗(yàn)器】

為了方便選手測(cè)試，我們下發(fā)了checker.cpp文件，選手可以編譯該程序，并使用它校驗(yàn)自己的輸出文件。但請(qǐng)注意它與最終評(píng)測(cè)時(shí)所使用的校驗(yàn)器并不完全一致。你也不需要關(guān)心其代碼的具體內(nèi)容。

編譯命令為：g++ checker.cpp ?o checker。

checker 的使用方式為：checker，參數(shù)依次表示輸入文件與你的輸出文件。

若你輸出的數(shù)字大小范圍不合法，則校驗(yàn)器會(huì)給出相應(yīng)提示。若你的輸出數(shù)字大小范圍正確，但方案錯(cuò)誤，則校驗(yàn)器會(huì)給出簡(jiǎn)要的錯(cuò)誤信息：

1.?A x，表示進(jìn)行到第 x 個(gè)操作時(shí)不合法。

2.?B x，表示操作執(zhí)行完畢后第 x 個(gè)柱子上的球不合法。

若你的方案正確，校驗(yàn)器會(huì)給出OK。

作者超懶，直接上代碼！

#include#include#include#include#include 
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long int_;
inline int readint(){
	int a = 0; char c = getchar(), f = 1;
	for(; c<'0'||c>'9'; c=getchar())
		if(c == '-') f = -f;
	for(; '0'<=c&&c<='9'; c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}
inline void writeint(int x){
	if(x >9) writeint(x/10);
	putchar((x-x/10*10)^48);
}
inline int ABS(const int &x){
	return x< 0 ? -x : x;
}

const int MaxN = 55;
const int MaxM = 405;
int a[MaxN][MaxM], n, m;
int count(int x,int mid){
	int s = 0; rep(i,1,m) s += (a[x][i]<= mid); return s;
}
# define TOP(x) a[x][a[x][0]]

vector< pair>ans;
# define CMD(x,y) do{ ans.push_back(make_pair(x,y));\
a[y][++ a[y][0]] = a[x][a[x][0] --]; } while(false)
int pos[MaxN]; // pos[0] is empty
inline void create(int x,int s){
	rep(i,1,s) CMD(x,pos[0]);
}
inline void pourOut(int x,int y,int k){
	for(; k; --k) CMD(x,y);
}
inline void moveUp(int x,int want,int helper,bool sgn=1,bool f=1){
	int s = count(x,want), lost = 0;
	if(!sgn) s = m-s; // >want
	bool wxk = false; // if it's swapped
	if((m>>1)< s && f){
		wxk = 1; create(helper,m-s);
		swap(helper,pos[0]); // temporary
	} else create(helper,s);
	for(int work=s; work; )
		if((TOP(x)<= want) == sgn){
			CMD(x,helper); -- work;
		} else { CMD(x,pos[0]); ++ lost; }
	pourOut(pos[0],x,lost); // normal balls
	if(!f) return ; // keep %want% in register
	pourOut(helper,x,s); // put %want% on the top
	if(wxk){ // restore
		swap(helper,pos[0]);
		pourOut(pos[0],helper,m-s);
	} else pourOut(pos[0],helper,s);
}
void solve(int l,int r){
	if(l == r) return ; // already done
	if(l+1 == r){ // n = 2
		moveUp(pos[l],l,pos[r]);
		moveUp(pos[r],l,pos[l]);
		pourOut(pos[l],pos[0],count(pos[l],l));
		pourOut(pos[r],pos[0],count(pos[r],l));
		pourOut(pos[l],pos[r],a[pos[l]][0]);
		swap(pos[0],pos[l]); return ;
	}
	int mid = (l+r)>>1;
	for(int i=l+1; i<=r; ++i){
		int s1 = count(pos[i-1],mid);
		int s2 = count(pos[i],mid);
		bool sgn = (s1+s2 >= m); // want
		if((sgn && (m>>1)< m-s1)
		|| (!sgn && (m>>1)< s1)) // fill pos[i-1]
			swap(pos[i],pos[i-1]), s1 = s2;
		if(!s1 || s1 == m) continue; // well...
		int aid = (i == r) ? pos[l] : pos[i+1];
		moveUp(pos[i],mid,aid,sgn); // extract i
		moveUp(pos[i-1],mid,aid,sgn^1,false);
		pourOut(pos[i],pos[i-1],m-a[pos[i-1]][0]);
		pourOut(aid,pos[i],m-a[pos[i]][0]);
		pourOut(pos[0],aid,a[pos[0]][0]);
	}
	for(int i=l,j=r; imid; --j);
		swap(pos[i],pos[j]);
	}
	solve(l,mid), solve(mid+1,r);
}

int main(){
	n = readint(), m = readint();
	rep(i,1,n) rep(j,1,m)
		a[i][j] = readint();
	rep(i,1,n) // init
		pos[i] = i, a[i][0] = m;
	pos[0] = n+1; solve(1,n);
	writeint(ans.size());
	putchar('\n');
	for(auto it : ans){
		writeint(it.first);
		putchar(' ');
		writeint(it.second);	
		putchar('\n');
	}
	return 0;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

本文名稱：2014：【20NOIP提高組】移球游戲-創(chuàng)新互聯(lián)
文章轉(zhuǎn)載：http://chinadenli.net/article26/dechcg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站改版、網(wǎng)站制作、外貿(mào)網(wǎng)站建設(shè)、企業(yè)建站、品牌網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)