2002db1.c

// 2002d-b
// 少し違ってるみたい

#include <stdio.h>

#define XX 101
#define YY 101

unsigned short pile[XX][YY];
int N;

void clear(void);
void print(void);
void search(int a, int *ax, int *ay);
void selection_sort(int a[], int n);

int main(void)
{
	int a,b,i,j,x,y;
	int ax,ay,bx,by;
	int tmp;
	int sum[XX];
	
	while(1){
		scanf("%d", &N);
		if(N==0) break;
///		printf("●●●●●%d\n", N);
		
		clear();
		
		for(i=1; i<=N; i++){
			pile[i][1]=i;
		}
//		print();
		
		while(1){
			scanf("%d %d", &a, &b);
			if(a==0 && b==0) break;
			
///			print();
///			printf("%d->%d\n", a, b);
			
			if(a==b) continue; // 同じのは意味が無い
			// どこにあるか見つける(床に置かない時)
			if(b!=0){
				search(a,&ax,&ay);
				search(b,&bx,&by);
//				printf("%d in (%d,%d), %d in (%d,%d)\n", a, ax, ay, b, bx, by);
				// 同じ列にある場合
				if(ax==bx){
//					puts("取るのも置くのも同じ列にある");
					if(ay>by){ // 取るのが上、置くのが下の場合、無視
//						puts("取るのが上、置くのが下の場合、無視");
					}else{ // 取るのが下、置くのが上の場合
						// 取るのの上をすべて床に置く
						i=ay+1;
						while(pile[ax][i]!=0){
							x=1;
							while(pile[x][1]!=0){
								x++;
							}
							
//							printf(" 列%dは空なので(%d,%d)->(%d,%d)\n", x, ax, i, x, 1);
							pile[x][1]=pile[ax][i];
							pile[ax][i]=0;
							i++;
							
//							print();
						}
						// 取るのを置くのの上に置く
						search(b, &bx, &by); // 再検索
//						printf(" (%d,%d)->(%d,%d)\n", ax, ay, bx, 2);
						pile[bx][2]=pile[ax][ay];
						pile[ax][ay]=0;
					}
				}else{ // 違う列にある場合
					i=ay+1;
					while(pile[ax][i]!=0){
						x=1;
						while(pile[x][1]!=0){ // 空っぽの列を見つける
							x++;
						}
						// 見つけた場所に置く
//						printf(" 列%dは空なので(%d,%d)->(%d,%d)\n", x, ax, i, x, 1);
						pile[x][1]=pile[ax][i];
						pile[ax][i]=0;
						i++;
						
//						print();
					} // 上を全部床に置いたので
					
					i=by;
					while(pile[bx][i]!=0){
						i++;
					}
//					printf(" (%d,%d)->(%d,%d)\n", ax, ay, bx, i);
					pile[bx][i]=pile[ax][ay];
					pile[ax][ay]=0;
					
//					print();
				}
			}else{ // 床に置く時
				search(a,&ax,&ay);
//				printf("%d in (%d,%d)\n", a, ax, ay);
				if(ay==1){ // すでに床にある
					
				}else{
///					puts("床におきたい");
					x=1;
					while(pile[x][1]!=0){
						x++;
					}
					pile[x][1]=pile[ax][ay];
					pile[ax][ay]=0;
				}
			}
		}
		
///		print();
		
		sum[0]=0;
		for(i=1; i<=N; i++){
			sum[i]=0;
			for(j=1; j<=N; j++){
				if(pile[i][j]==0){
					break;
				}else{
					sum[i]++;
				}
			}
		}
		
		selection_sort(sum, N+1);
//		puts("★★答★★");
		for(i=1; i<=N; i++){
			if(sum[i]){
				printf("%d\n", sum[i]);
			}
		}
		puts("end");
	}
	return 0;
}

void search(int a, int *ax, int *ay)
{
	int i,j;
	
	*ax=0;
	for(i=1; i<=N; i++){
		for(j=1; j<=N; j++){
			if(pile[i][j]==a){
				(*ax)=i;
				(*ay)=j;
				break;
			}
		}
		if(*ax) break;
	}
}

void selection_sort(int a[], int n)
{
    int i, j, t, lowest, lowkey;

    for (i = 0; i < n - 1; i++) {
		lowest = i;
		lowkey = a[i];
		for (j = i + 1; j < n; j++)
	    	if (a[j] < lowkey) {
				lowest = j; lowkey = a[j];
	    	}
		t = a[i]; a[i] = a[lowest]; a[lowest] = t;
    }
}

void clear(void)
{
	int i,j;
	
	for(i=0; i<XX; i++){
		for(j=0; j<YY; j++){
			pile[i][j]=0;
		}
	}
}

void print(void)
{
	int i,j;
	
	puts("\n■■■");
	for(i=1; i<=N; i++){
		if(pile[i][1]==0){
			// continue;
		}else{
			for(j=1; j<=N; j++){
				if(pile[i][j]==0){
					break;
				}else{
					printf("%d ", pile[i][j]);
				}
			}
		}
		printf("\n");
	}
	puts("■■■\n");
}