「AOJ Problem Set from ALDS1問　0～19」の編集履歴（バックアップ）一覧はこちら

「AOJ Problem Set from ALDS1問　0～19」(2014/01/17 (金) 03:27:31) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

会津大学オンラインジャッジALDS　問0～20まで

*Getting Started - Insertion Sort
挿入ソートのステップを表示していく問題。
解法
挿入ソートが何をしているかイメージできたら何の問題もない問題です。
要は数字列を左から整列していき、右へ進むだけです。
右で新しい数字が来たら左にさかのぼって入れる位置を決め、そこまでにいる数を全て右へ一つずつずらします。


 #include<stdio.h>
 
 static const int N = 1000;
 
 void trace(int A[], int n){
   int i;
   for ( i = 1; i <= n; i++ ){
     if ( i > 1 ) printf(" ");
     printf("%d", A[i]);
   }
   printf("\n");
 }
 
 int main(){
   int n, i, j;
   int A[N+1];
   scanf("%d", &n);
 
   for ( i = 1; i <= n; i++ ) scanf("%d", &A[i]);
   
   trace(A, n);
   for(int j=2;j<=n;j++){
 		int key=A[j];
  		i=j-1;
 		while(i > 0 && A[i]>key){
  			A[i+1]=A[i];
 			i--;
 		} 
 		A[i+1]=key;
 		trace(A,n);
  	}
   return 0;
 }




*Getting Started - Greatest Common Divisor
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_B
ｇｃｄを実装する問題。
指定通り実装するだけです。


 #include<stdio.h>
 int gcd(int a,int b){
 	int c;
 	while(a!=0){
 		c=a;
 		a=b%a;
 		b=c;
  	}
 	return b;
 }
 
 int main(){
  	int a,b;
 	scanf("%d %d",&a,&b);
 	printf("%d\n",gcd(a,b));
 }


*Getting Started - Prime Numbers
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_C
与えられた数列の中に素数が何個あるか答える問題。
解法
1億までの数しか数列に現れないので、10000までの素数で試し割すれば素数かどうか判別できます。
10000までの素数の列は篩で求めます。


 #include<stdio.h>
 #include<vector>
 
 std::vector<int> prime_list;
 void calc_prime_list(){
 	int is_prime[10001]={0};
 	for(int i=2;i<400;i++){
 		if(is_prime[i]==1)continue;
 		for(int j=i*2;j<10001;j+=i){
 			is_prime[j]=1;
 		}
 	}
 	for(int i=2;i<10001;i++){
 		if(is_prime[i]==0)prime_list.push_back(i);
 	}
 }
 
 bool prime_check(int n){
  	for(int i=0;i<prime_list.size();i++){
 		int p=prime_list[i];
 		if(p*p>n)break;
 		if(n%p==0)return false;
  	}
 	return true;
 }
 
 int main(){
 	calc_prime_list();
 	int n,ans=0,num;
 	scanf("%d",&n);
  	while(n--){
 		scanf("%d",&num);
  		ans+=prime_check(num);
 	}
 	printf("%d\n",ans);
 }




*Sort I - Bubble Sort
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_A
指定通りソートを記述するだけ。
数列の右端から初めて左端へ進みながら小さい数を選んで左右を入れ替えていく。
すると最初の右から左への一巡で、一番小さい数が左端にくる。
あとはそれから左端一個除いた部分で同じ処理を繰り返しこれを繰り返すと最後は全部ソートされる。


 #include<stdio.h>
 
 void print(int A[],int n){
 	for(int i=1;i<n;i++)printf("%d ",A[i]);
 	printf("%d\n",A[n]);
 }
 
 int main(){
 	int A[102],n,ans=0;
  	scanf("%d",&n);
 	for(int i=1;i<=n;i++)scanf("%d",&A[i]);
 	for(int i=1;i<=n;i++){
  		for(int j=n;j>i;j--){
 			if(A[j]<A[j-1]){
 				int t=A[j-1];
 				A[j-1]=A[j];
 				A[j]=t;
 				ans++;
  			}
 		}
 		
  	}
 	print(A,n);
 	printf("%d\n",ans);
 }


*Sort I - Selection Sort
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_B
選択ソートを実装しソートの交換回数をこたえる問題。
選択ソートはまず配列を全部見て、一番小さいものを左端に持ってくる。
すると左端は一個でソートされ一番小さいものが左端に来て、残りは未ソートです。
2個めから全部精査しその中で一番小さいものを左から2番目に持ってくれば。
左は一番小さいものが左端に、その次に小さいのが左から2番目とこれを繰り返せばすべてソートされます。

 #include<stdio.h>
 
 void print(int A[],int n){
 	for(int i=1;i<n;i++)printf("%d ",A[i]);
 	printf("%d\n",A[n]);
 }
  
 int main(){
 	int A[102],n,ans=0;
 	scanf("%d",&n);
 	for(int i=1;i<=n;i++)scanf("%d",&A[i]);
 	for(int i=1;i<=n;i++){
 		int mini=i;
  		for(int j=i;j<=n;j++){
 			if(A[j]<A[mini]){
 				mini=j;
 			}
 		}
 		if(i!=mini){
 			int t=A[i];
  			A[i]=A[mini];
 			A[mini]=t;
 			ans++;
 		}
  	}
 	print(A,n);
 	printf("%d\n",ans);
 }





*Sort I - Stability
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_C
バブルソートと選択ソートを行いそれがソート結果が安定であったかどうか判定する問題。

解法
バブルソートは無条件で安定なので常にStableです。
選択ソートは左側を決めてそれと入れ替える数を右側で探す際。
最初に入れ替える数と同じ数が出会った場所をPとし。
そのPより右側で最も小さい数が見つかった場合安定でなくなります。


 #include<stdio.h>
 #include<algorithm>
 #include<string.h>
 
 void print(char A[37][3],int n){
 	for(int i=1;i<n;i++)printf("%s ",A[i]);
 	printf("%s\n",A[n]);
 }
  
 void BubbleSort(char A[37][3],int n){
 	for(int i=1;i<=n;i++){
  		for(int j=n;j>i;j--){
 			if(A[j][1]<A[j-1][1]){
 				std::swap(A[j-1][0],A[j][0]);
 				std::swap(A[j-1][1],A[j][1]);
  			}
 		}
 		
  	}
 	print(A,n);
 	printf("Stable\n");//バブルソートは常に安定
 }
 
 void SelectionSort(char A[37][3],int n){
 	bool isStable=true;
 	for(int i=1;i<=n;i++){
 		int mini=i,p;
  		p=mini;
  		for(int j=i;j<=n;j++){
 			if(A[j][1]<A[mini][1]){
 				mini=j;
 			}else if(A[j][1]==A[i][1]&&i==p){
 				p=j;
 			}
  		}
 		if(i!=mini){
 			std::swap(A[i][0],A[mini][0]);
 			std::swap(A[i][1],A[mini][1]);
 			if(i<p&&p<mini)isStable=false;
  		}
 	}
  	print(A,n);
 	printf("%s\n",isStable?"Stable":"Not stable");
 }
 
 int main(){
 	int n;
 	char A[37][3],B[37][3];
 	scanf("%d",&n);
 	for(int i=1;i<=n;i++){
 		scanf("%s",A[i]);
 	}
  	memcpy(B,A,sizeof(A));
 	BubbleSort(A,n);
 	SelectionSort(B,n);
 }


*Elementary data structures - Reverse Polish Notation
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_A
逆ポーランド記法の数式を処理する問題。
 
 #include<stdio.h>
 #include<stdlib.h>
 #include<string.h>
 #include<stack>
 
 int main(){
  int x,x1,x2;
  std::stack<int> Stack;
  char s[100];
  
  while( scanf("%s", s) != EOF ){
     if ( s[0] == '+' ){
 	x1=Stack.top();
 	Stack.pop();
 	x2=Stack.top();
 	Stack.pop();
 	Stack.push(x1+x2);
    } else if ( s[0] == '-' ){
 	x1=Stack.top();
 	Stack.pop();
 	x2=Stack.top();
 	Stack.pop();
 	Stack.push(x2-x1);
    } else if ( s[0] == '*' ){
  	x1=Stack.top();
 	Stack.pop();
 	x2=Stack.top();
 	Stack.pop();
 	Stack.push(x1*x2);
    } else {
       Stack.push(atoi(s));
    }
   }
   printf("%d\n",Stack.top());
   return 0;
 }




*Elementary data structures - Round-Robin Scheduling
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_B
コンピュータのタスク処理手順を題材にした問題。

解法
queueで回せば一発です。

 #include<iostream>
 #include<queue>
 #include<string>
 
 struct S{
  	std::string name;
 	int time;
 };
 
 int main(){
 	int n,q;
  	std::queue<S> qu;
 	std::cin>>n>>q;
 	S s;
 	for(int i=0;i<n;i++){
 		std::cin>>s.name>>s.time;
		qu.push(s);
 	}
 	int time=0;
 	while(qu.empty()==false){
 		s=qu.front();
  		qu.pop();
		if(s.time-q<=0){
 			time+=s.time;
 			std::cout<<s.name<<" "<<time<<"\n";
 		}else{
 			time+=q;
  			s.time-=q;
 			qu.push(s);
 		}
 	}
 }





*Elementary data structures - Doubly Linked List
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_C
双方向リンクリストをCで実装する問題。
ポインタ苦手。


 #include<stdio.h>
 #include<stdlib.h>
 #include<string.h>
 
 struct node{
   unsigned int key;
   struct node *next;
   struct node *prev;
 };
 
 typedef struct node * NodePointer;
 
 NodePointer nil;
 
 NodePointer listSearch(int key){
  /* your code */
   NodePointer cur=nil->next;
   while(1){
    	if(cur==nil)return cur;
 	if(cur->key==key)return cur;
 	cur=cur->next;
   }
 } 
 
 void init(){
   nil = malloc(sizeof(struct node));
   nil->next = nil;
   nil->prev = nil;
 } 
 
 void printList(){
   NodePointer cur = nil->next;
   int isf = 1;
   while(1){
     if ( cur == nil ) break;
     if ( isf == 0)  printf(" ");
     printf("%d", cur->key);
     cur = cur->next;
     isf = 0;
   }
   printf("\n");
 }
 
 void deleteNode(NodePointer t){
  /* your code */
   NodePointer cur ,prev;
   if(t!=nil){
         cur=t->next;
 	prev=t->prev;
 	prev->next=cur;
 	cur->prev=prev;
  	if(t->next==nil){
 		nil->prev=prev;
 		prev->next=nil;
 	}
 	free(t);
   }
 }
 
 void deleteFirst(){
  NodePointer t = nil->next;
  if ( t == nil ) return;
  deleteNode(t);
 }
 
 void deleteLast(){
  /* your code */
  NodePointer cur=nil->prev;
  if(cur==nil)return;
  deleteNode(cur);
 }
 
 void delete(int key){
  /* your code */
  NodePointer t; 
  t=listSearch(key);
  if(t==nil)return ;
  deleteNode(t);
 } 
 
 
 void insert(int key){
  NodePointer x;
  x = malloc(sizeof(struct node));
  x->key = key;
  /* 
   your code 
  */
  if(nil->next==nil){
  	nil->prev=x;
  }
  x->next=nil->next;
  x->prev=nil;
   nil->next->prev=x;
   nil->next=x;
 } 
 
 int main(){
   int key, n, i;
   int size = 0;
   char com[20];
   int np = 0, nd = 0;
   scanf("%d", &n);
   init();
   for ( i = 0; i < n; i++ ){
     scanf("%s", com);
     if ( com[0] == 'i' ) {
 		scanf("%d",&key);
 		insert(key); np++; size++;
 	}
     else if ( com[0] == 'd' ) {
       if (strlen(com) > 6){
 	if ( com[6] == 'F' ) deleteFirst();
 	else if ( com[6] == 'L' ) deleteLast();
      } else {
 	scanf("%d",&key);
 	delete(key); nd++; 
      }
      size--;
    }
  }
   printList();
   return 0;
 }





*Search - Search I
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_A
両方の集合に共通する数字の個数を数える問題。
ソートして尺取虫、std::setを使うのも手。

 #include<stdio.h>
 #include<algorithm>
  
 int main(){
 	int S[10001],T[501],n,q,ans=0,p1=0,p2=0;
 	scanf("%d",&n);
 	for(int i=0;i<n;i++)scanf("%d",&S[i]);
 	scanf("%d",&q);
 	for(int i=0;i<q;i++)scanf("%d",&T[i]);
	std::sort(S,S+n);
 	std::sort(T,T+q);
 	while(p1<n&&p2<q){
 		if(S[p1]==T[p2]){
 			ans++;
 			p1++;
  			p2++;
 		}else if(S[p1]<T[p2]){
 			p1++;
 		}else{
 			p2++;
 		}
  	}
 	printf("%d\n",ans);
 }





*Search - Search II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B
前の問題と同じでデータ量が多いだけ。

 #include<stdio.h>
 #include<algorithm>
 
 int main(){
  	int S[100001],T[50001],n,q,ans=0,p1=0,p2=0;
 	scanf("%d",&n);
 	for(int i=0;i<n;i++)scanf("%d",&S[i]);
 	scanf("%d",&q);
 	for(int i=0;i<q;i++)scanf("%d",&T[i]);
 	std::sort(T,T+q);
 	while(p1<n&&p2<q){
  		if(S[p1]==T[p2]){
 			ans++;
 			p1++;
 			p2++;
 		}else if(S[p1]<T[p2]){
 			p1++;
 		}else{
  			p2++;
 		}
 	}
 	printf("%d\n",ans);
 }





*Search - Search III
まあそのstd::setを使えば一発だったんだけど。
一応ハッシュテーブルの学習用問題だと考えて計算。
ハッシュ関数の作りが適当なのはここだけの秘密、ただしい３２ビットハッシュ関数の作り方ってどんなんだろう？
AOJやっててよかったことは今のところ何もないので、評価値が下がろうが気にしない。



 #include<stdio.h>
 #include<string.h>
 #include<list>
  
 const int LIMIT =((1<<16)+33);
 std::list<int> hashTable[LIMIT];
 int h1(char *str){
    int p,p1,num,result=0;
    char c;
     
    for(p=0;p<strlen(str);p++){
        c=str[p];
        num=0;
        if(c=='A')num=0;
        if(c=='C')num=1;
        if(c=='G')num=2;
        if(c=='T')num=3;
        p1=(p%8)*2;
        result=((num<<p1)^result);
    }
    return result%LIMIT;
 }
 int h2(char *str){
    int num,result=0,b=1;
    char c;
    for(int p=0;p<strlen(str);p++){
        c=str[p];
        num=1;
        if(c=='A')num=1;
        if(c=='C')num=2;
        if(c=='G')num=3;
        if(c=='T')num=4;
        result+=num*b;
        b*=5;
    }
    return result;
 }
  
 bool find(char *str){
    int H1=h1(str);
    int H2=h2(str);
    for(std::list<int>::iterator it=hashTable[H1].begin();it!=hashTable[H1].end();it++){
        if(H2==(*it))return true;
    }
     return false;
 }
  
 void insert(char *str){
     if(find(str)==false){
         hashTable[h1(str)].push_front(h2(str));
     }
 }
  
 int main(){
    int n;
    char str[14],com[10];
    scanf("%d",&n);
    while(n--){
         scanf("%s %s",com,str);
         if(com[0]=='i'){
             insert(str);
         }else{
             printf("%s\n",find(str)?"yes":"no");
         }
     }   
 }






*Recursion / Divide and Conquer - Brute Force
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A
全探索で実装しなさいという指定だったのだけど。
動的計画法のほうが明らかに楽だよねこれ。
というわけで動的計画法で解。

 #include<stdio.h>
 #include<string.h>
 
 int main(){
 	int n,q,a,sum=0,m;
 	bool memo[40001];
 	memset(memo,0,sizeof(memo));
  	memo[0]=true;
 	scanf("%d",&n);	
 	for(int i=0;i<n;i++){
 		scanf("%d",&a);
 		for(int j=sum;j>=0;j--){
 			memo[j+a]=memo[j+a]||memo[j];
 		}
  		sum+=a;
 	}
 	scanf("%d",&q);
 	for(int i=0;i<q;i++){
 		scanf("%d",&m);
 		printf("%s\n",memo[m]?"yes":"no");
 	}
 }




*Recursion / Divide and Conquer - Merge Sort
マージソートを実装する問題。
指定通り記述するだけです。
マージソートは一番小さい単位まで分解してその中身をソート済みにする。
戻ってきた時に、ソート済みの両側を小さいほうからマージしていく。
イメージができていれば簡単な問題。

 #include<stdio.h>
 #include<string.h>
 
 const int SENTINEL=2147483647 ;
 int count=0;
  
 void Merge(int* A,int left,int mid,int right){
 	int n1=mid-left;
 	int n2=right-mid;
 	int *L=new int[n1+1];
	int *R=new int[n2+1];
 	for(int i=0;i<=n1-1;i++)L[i]=A[left+i];
 	for(int i=0;i<=n2-1;i++)R[i]=A[mid+i];
  	int i=0,j=0;
 	L[n1]=R[n2]=SENTINEL;
 	
 	for(int k=left;k<=right-1;k++){
 		count++;
 		if(L[i]<=R[j]){
 			A[k]=L[i];
 			i++;
 		}else{
 			A[k]=R[j];
 			j++;
 		}
 	}
 	delete []L;
 	delete []R;
 } 
  void Merge_Sort(int *A,int left,int right){
 	if(left+1<right){
 		int mid=(left+right)/2;
 		Merge_Sort(A,left,mid);
 		Merge_Sort(A,mid,right);
 		Merge(A,left,mid,right);
 	}
 }
 
 int main(){
 	int n;	
 	int *A=new int[500001];
 	scanf("%d",&n);
 	for(int i=0;i<n;i++)scanf("%d",&A[i]);
 	Merge_Sort(A,0,n);
  	for(int i=0;i<n;i++){
 		if(i>0)printf(" ");
 		printf("%d",A[i]);
 	}
 	printf("\n%d\n",count);
 	delete []A;
 }



*Recursion / Divide and Conquer - Koch Curve
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_C
コッホ曲線の座標を表示する問題
再帰でまあなんとか、もうちょっと一般のフラクタル図形を計算できるようにしたほうがいいかも、、、


 #include<stdio.h>
 #include<math.h>
 
 int n;
 const double toR=M_PI/180.0;
 
 void saiki(double px,double py,double len,double r,int deep){
 	if(deep==n){
 		if(px<0)px=-px;
  		if(py<0)py=-py;
 		printf("%lf %lf\n",px,py);
 		return ;
 	}
 	double nx,ny,len1;
 	len1=len/3.0;
 	saiki(px,py,len1,r,deep+1);
 	nx=px+len1*cos(r*toR);
 	ny=py+len1*sin(r*toR);
 	saiki(nx,ny,len1,r+60,deep+1);
 	nx+=len1*cos((r+60)*toR);
  	ny+=len1*sin((r+60)*toR);
 	saiki(nx,ny,len1,r-60,deep+1);
 	nx+=len1*cos((r-60)*toR);
 	ny+=len1*sin((r-60)*toR);
 	saiki(nx,ny,len1,r,deep+1);
 }
 
 int main(){
 	scanf("%d",&n);
  	saiki(0,0,100,0,0);
 	double a=100,b=0;
 	printf("%lf %lf\n",a,b);	
 }


*Sort II - Counting Sort
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_A
カウンティングソートを実装する問題。

小さいほうから尺取虫法的に積み上げていって。
最後に引きながら位置を決定していく。
4 4 4 1 1 1 5 5
ソート後
1 1 1 4 4 4 5 5
なら
4を含む４までの数は6回数えられてるから6,5,4か所目に入るというのを最後の処理でやっている。
なるほどいろいろな手を考えるものだと感心。

 #include<stdio.h>
 #include<math.h>
 
 const int LIMIT=2000001;
 int C[10001];
 int n;
 int A[LIMIT],B[LIMIT];
  
 void Counting_Sort(int *A,int *B,int k){
  	for(int i=0;i<=k;i++)C[i]=0;
 	for(int j=1;j<=n;j++){
 		C[A[j]]++;
 	}
 	for(int i=1;i<=k;i++){
  		C[i]+=C[i-1];
 	}
 	for(int j=n;j>=1;j--){
 		B[C[A[j]]]=A[j];
 		C[A[j]]--;
 	}
 }
 
 int main(){
 	scanf("%d",&n);	
 	for(int i=1;i<=n;i++)scanf("%d",&A[i]);
 	Counting_Sort(A,B,10000);
 	for(int i=1;i<=n;i++){
  		if(i>1)printf(" ");
 		printf("%d",B[i]);
 	}
 	printf("\n");
 }




*Sort II - Partition
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_Bクイックソートのパーティション操作を実装する問題。
ある数より小さいものを右に、大きいものを左に。
右側でも左側でも上と同じことを繰りかえせばクイックソート。


 #include<stdio.h>
 #include<math.h>
 
 const int LIMIT=100001;
  
 int Partition(int *A,int p,int r){
 	int x=A[r];
 	int i=p-1;
 	for(int j=p;j<=r-1;j++){
 		if(A[j]<=x){
  			i++;
 			int t=A[i];
 			A[i]=A[j];
 			A[j]=t;
 		}
 	}
 	int t=A[i+1];
 	A[i+1]=A[r];
 	A[r]=t;
 	return i+1;
 }
 
 int main(){
 	int A[LIMIT],n;
 	scanf("%d",&n);	
 	for(int i=1;i<=n;i++)scanf("%d",&A[i]);
 	int result=Partition(A,1,n);
 	for(int i=1;i<result;i++){
 		if(i>1)printf(" ");
 		printf("%d",A[i]);
  	}
 	printf(" [%d]",A[result]);
 	for(int i=result+1;i<=n;i++){
 		printf(" %d",A[i]);
 	}
 	printf("\n");
 }



*Sort II - Quick Sort
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_C
クイックソートを実装しその結果が安定かどうか判定する問題。

クイックソートは定義通り、あと順番が違ってるかは番号割り振ってそれが入れ替わっていたらに変更。

 #include<stdio.h>
 #include<math.h>
 #include<set>
 
 struct S{
 	int n,no;
 	char c;
 	bool operator<=(const S &s)const{
 		return n<=s.n;
 	}
 };
 const int LIMIT=100001;
 S A[LIMIT];
 int Partition(S *A,int p,int r){
 	S x=A[r];
 	int i=p-1;
 	for(int j=p;j<=r-1;j++){
  		if(A[j]<=x){
 			i++;
 			S t=A[i];
 			A[i]=A[j];
 			A[j]=t;
 		}
 	}
 	S t=A[i+1];
 	A[i+1]=A[r];
 	A[r]=t;	
 	return i+1;
 } 
 void Quicksort(S *A,int p,int r){
 	if(p<r){
 		int q=Partition(A,p,r);
 		Quicksort(A,p,q-1);
 		Quicksort(A,q+1,r);
 	}
 }
 
 int main(){
 	S s;
 	int n;
 	char c;
 	scanf("%d",&n);
  	for(int i=1;i<=n;i++){
 		scanf("%c%c %d",&c,&A[i].c,&A[i].n);	
 		A[i].no=i;
 	}
 	Quicksort(A,1,n);
 	bool isStable=true;
  	for(int i=1;i<n;i++){
 		if(A[i].n==A[i+1].n&&A[i].no>A[i+1].no)isStable=false;
 	}
 	
 	printf("%s\n",isStable?"Stable":"Not stable");
  	for(int i=1;i<=n;i++){
 		printf("%c %d\n",A[i].c,A[i].n);
 	}
 }


*Tree - Rooted Trees
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_A
与えられたデータから木構造を組み立てて組みあがった結果を出力する問題。
木の左側とその兄弟という表現法があるなんて知らなかった。
サンプルソースの意図が読めずちょっと苦労した。

 #include<stdio.h>
 #define MAX 100005
 #define NIL -1
 
 /*
 p: parent
 l: left-child
 r: right sibling
 */
 struct Node{ int p, l, r,d;};
 struct Node T[MAX]; // Tree
 int depth[MAX];
 
 /*
 */
 
 
 void print(int u){
  /*
   */
  printf("node %d: parent = %d, depth = %d, ",u,T[u].p,T[u].d);
  if(T[u].p==-1){
  	printf("root, [");
  }else if(T[u].l==NIL){
  	printf("leaf, [");
  }else{
  	printf("internal node, [");
  }
  int p=T[u].l;
 
  while(p!=NIL){
       if(p==T[u].l)printf("%d",p);
       else printf(", %d",p);
      p=T[p].r;
  }
   printf("]\n");
 }
 
 void calc_depth(int deep,int p){
 	T[p].d=deep;
 	if(T[p].l==NIL)return;
 	for(p=T[p].l;p!=NIL;p=T[p].r){
 		calc_depth(deep+1,p);
 	}
 } 
 
 int main(){
  int i, j, d, v, c, l,n;
 
  scanf("%d", &n);
 
  for ( i = 0; i < n; i++ ) {
    T[i].p = T[i].l = T[i].r = NIL;
  }
 
   for ( i = 0; i < n; i++ ){
    scanf("%d %d", &v, &d);
     int old=0;
     for ( j = 0; j < d; j++ ){
       scanf("%d", &c);
 	T[c].p=v;
  	if(j==0){
 		T[v].l=c;
 	}else{
 		T[old].r=c;
 	}
 	old=c;
    }
  }
    int p;
   for(int i=0;i<n;i++)if(T[i].p==-1)p=i;
   calc_depth(0,p); 
   for ( i = 0; i < n; i++ ) print(i);
   return 0;
 }

会津大学オンラインジャッジALDS　問0～20まで

*Getting Started - Insertion Sort
挿入ソートのステップを表示していく問題。
解法
挿入ソートが何をしているかイメージできたら何の問題もない問題です。
要は数字列を左から整列していき、右へ進むだけです。
右で新しい数字が来たら左にさかのぼって入れる位置を決め、そこまでにいる数を全て右へ一つずつずらします。


 #include<stdio.h>
 
 static const int N = 1000;
 
 void trace(int A[], int n){
   int i;
   for ( i = 1; i <= n; i++ ){
     if ( i > 1 ) printf(" ");
     printf("%d", A[i]);
   }
   printf("\n");
 }
 
 int main(){
   int n, i, j;
   int A[N+1];
   scanf("%d", &n);
 
   for ( i = 1; i <= n; i++ ) scanf("%d", &A[i]);
   
   trace(A, n);
   for(int j=2;j<=n;j++){
 		int key=A[j];
  		i=j-1;
 		while(i > 0 && A[i]>key){
  			A[i+1]=A[i];
 			i--;
 		} 
 		A[i+1]=key;
 		trace(A,n);
  	}
   return 0;
 }




*Getting Started - Greatest Common Divisor
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_B
ｇｃｄを実装する問題。
指定通り実装するだけです。


 #include<stdio.h>
 int gcd(int a,int b){
 	int c;
 	while(a!=0){
 		c=a;
 		a=b%a;
 		b=c;
  	}
 	return b;
 }
 
 int main(){
  	int a,b;
 	scanf("%d %d",&a,&b);
 	printf("%d\n",gcd(a,b));
 }


*Getting Started - Prime Numbers
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_C
与えられた数列の中に素数が何個あるか答える問題。
解法
1億までの数しか数列に現れないので、10000までの素数で試し割すれば素数かどうか判別できます。
10000までの素数の列は篩で求めます。


 #include<stdio.h>
 #include<vector>
 
 std::vector<int> prime_list;
 void calc_prime_list(){
 	int is_prime[10001]={0};
 	for(int i=2;i<400;i++){
 		if(is_prime[i]==1)continue;
 		for(int j=i*2;j<10001;j+=i){
 			is_prime[j]=1;
 		}
 	}
 	for(int i=2;i<10001;i++){
 		if(is_prime[i]==0)prime_list.push_back(i);
 	}
 }
 
 bool prime_check(int n){
  	for(int i=0;i<prime_list.size();i++){
 		int p=prime_list[i];
 		if(p*p>n)break;
 		if(n%p==0)return false;
  	}
 	return true;
 }
 
 int main(){
 	calc_prime_list();
 	int n,ans=0,num;
 	scanf("%d",&n);
  	while(n--){
 		scanf("%d",&num);
  		ans+=prime_check(num);
 	}
 	printf("%d\n",ans);
 }




*Sort I - Bubble Sort
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_A
指定通りソートを記述するだけ。
数列の右端から初めて左端へ進みながら小さい数を選んで左右を入れ替えていく。
すると最初の右から左への一巡で、一番小さい数が左端にくる。
あとはそれから左端一個除いた部分で同じ処理を繰り返しこれを繰り返すと最後は全部ソートされる。


 #include<stdio.h>
 
 void print(int A[],int n){
 	for(int i=1;i<n;i++)printf("%d ",A[i]);
 	printf("%d\n",A[n]);
 }
 
 int main(){
 	int A[102],n,ans=0;
  	scanf("%d",&n);
 	for(int i=1;i<=n;i++)scanf("%d",&A[i]);
 	for(int i=1;i<=n;i++){
  		for(int j=n;j>i;j--){
 			if(A[j]<A[j-1]){
 				int t=A[j-1];
 				A[j-1]=A[j];
 				A[j]=t;
 				ans++;
  			}
 		}
 		
  	}
 	print(A,n);
 	printf("%d\n",ans);
 }


*Sort I - Selection Sort
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_B
選択ソートを実装しソートの交換回数をこたえる問題。
選択ソートはまず配列を全部見て、一番小さいものを左端に持ってくる。
すると左端は一個でソートされ一番小さいものが左端に来て、残りは未ソートです。
2個めから全部精査しその中で一番小さいものを左から2番目に持ってくれば。
左は一番小さいものが左端に、その次に小さいのが左から2番目とこれを繰り返せばすべてソートされます。

 #include<stdio.h>
 
 void print(int A[],int n){
 	for(int i=1;i<n;i++)printf("%d ",A[i]);
 	printf("%d\n",A[n]);
 }
  
 int main(){
 	int A[102],n,ans=0;
 	scanf("%d",&n);
 	for(int i=1;i<=n;i++)scanf("%d",&A[i]);
 	for(int i=1;i<=n;i++){
 		int mini=i;
  		for(int j=i;j<=n;j++){
 			if(A[j]<A[mini]){
 				mini=j;
 			}
 		}
 		if(i!=mini){
 			int t=A[i];
  			A[i]=A[mini];
 			A[mini]=t;
 			ans++;
 		}
  	}
 	print(A,n);
 	printf("%d\n",ans);
 }





*Sort I - Stability
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_C
バブルソートと選択ソートを行いそれがソート結果が安定であったかどうか判定する問題。

解法
バブルソートは無条件で安定なので常にStableです。
選択ソートは左側を決めてそれと入れ替える数を右側で探す際。
最初に入れ替える数と同じ数が出会った場所をPとし。
そのPより右側で最も小さい数が見つかった場合安定でなくなります。


 #include<stdio.h>
 #include<algorithm>
 #include<string.h>
 
 void print(char A[37][3],int n){
 	for(int i=1;i<n;i++)printf("%s ",A[i]);
 	printf("%s\n",A[n]);
 }
  
 void BubbleSort(char A[37][3],int n){
 	for(int i=1;i<=n;i++){
  		for(int j=n;j>i;j--){
 			if(A[j][1]<A[j-1][1]){
 				std::swap(A[j-1][0],A[j][0]);
 				std::swap(A[j-1][1],A[j][1]);
  			}
 		}
 		
  	}
 	print(A,n);
 	printf("Stable\n");//バブルソートは常に安定
 }
 
 void SelectionSort(char A[37][3],int n){
 	bool isStable=true;
 	for(int i=1;i<=n;i++){
 		int mini=i,p;
  		p=mini;
  		for(int j=i;j<=n;j++){
 			if(A[j][1]<A[mini][1]){
 				mini=j;
 			}else if(A[j][1]==A[i][1]&&i==p){
 				p=j;
 			}
  		}
 		if(i!=mini){
 			std::swap(A[i][0],A[mini][0]);
 			std::swap(A[i][1],A[mini][1]);
 			if(i<p&&p<mini)isStable=false;
  		}
 	}
  	print(A,n);
 	printf("%s\n",isStable?"Stable":"Not stable");
 }
 
 int main(){
 	int n;
 	char A[37][3],B[37][3];
 	scanf("%d",&n);
 	for(int i=1;i<=n;i++){
 		scanf("%s",A[i]);
 	}
  	memcpy(B,A,sizeof(A));
 	BubbleSort(A,n);
 	SelectionSort(B,n);
 }


*Elementary data structures - Reverse Polish Notation
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_A
逆ポーランド記法の数式を処理する問題。
 
 #include<stdio.h>
 #include<stdlib.h>
 #include<string.h>
 #include<stack>
 
 int main(){
  int x,x1,x2;
  std::stack<int> Stack;
  char s[100];
  
  while( scanf("%s", s) != EOF ){
     if ( s[0] == '+' ){
 	x1=Stack.top();
 	Stack.pop();
 	x2=Stack.top();
 	Stack.pop();
 	Stack.push(x1+x2);
    } else if ( s[0] == '-' ){
 	x1=Stack.top();
 	Stack.pop();
 	x2=Stack.top();
 	Stack.pop();
 	Stack.push(x2-x1);
    } else if ( s[0] == '*' ){
  	x1=Stack.top();
 	Stack.pop();
 	x2=Stack.top();
 	Stack.pop();
 	Stack.push(x1*x2);
    } else {
       Stack.push(atoi(s));
    }
   }
   printf("%d\n",Stack.top());
   return 0;
 }




*Elementary data structures - Round-Robin Scheduling
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_B
コンピュータのタスク処理手順を題材にした問題。

解法
queueで回せば一発です。

 #include<iostream>
 #include<queue>
 #include<string>
 
 struct S{
  	std::string name;
 	int time;
 };
 
 int main(){
 	int n,q;
  	std::queue<S> qu;
 	std::cin>>n>>q;
 	S s;
 	for(int i=0;i<n;i++){
 		std::cin>>s.name>>s.time;
		qu.push(s);
 	}
 	int time=0;
 	while(qu.empty()==false){
 		s=qu.front();
  		qu.pop();
		if(s.time-q<=0){
 			time+=s.time;
 			std::cout<<s.name<<" "<<time<<"\n";
 		}else{
 			time+=q;
  			s.time-=q;
 			qu.push(s);
 		}
 	}
 }





*Elementary data structures - Doubly Linked List
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_C
双方向リンクリストをCで実装する問題。
ポインタ苦手。


 #include<stdio.h>
 #include<stdlib.h>
 #include<string.h>
 
 struct node{
   unsigned int key;
   struct node *next;
   struct node *prev;
 };
 
 typedef struct node * NodePointer;
 
 NodePointer nil;
 
 NodePointer listSearch(int key){
  /* your code */
   NodePointer cur=nil->next;
   while(1){
    	if(cur==nil)return cur;
 	if(cur->key==key)return cur;
 	cur=cur->next;
   }
 } 
 
 void init(){
   nil = malloc(sizeof(struct node));
   nil->next = nil;
   nil->prev = nil;
 } 
 
 void printList(){
   NodePointer cur = nil->next;
   int isf = 1;
   while(1){
     if ( cur == nil ) break;
     if ( isf == 0)  printf(" ");
     printf("%d", cur->key);
     cur = cur->next;
     isf = 0;
   }
   printf("\n");
 }
 
 void deleteNode(NodePointer t){
  /* your code */
   NodePointer cur ,prev;
   if(t!=nil){
         cur=t->next;
 	prev=t->prev;
 	prev->next=cur;
 	cur->prev=prev;
  	if(t->next==nil){
 		nil->prev=prev;
 		prev->next=nil;
 	}
 	free(t);
   }
 }
 
 void deleteFirst(){
  NodePointer t = nil->next;
  if ( t == nil ) return;
  deleteNode(t);
 }
 
 void deleteLast(){
  /* your code */
  NodePointer cur=nil->prev;
  if(cur==nil)return;
  deleteNode(cur);
 }
 
 void delete(int key){
  /* your code */
  NodePointer t; 
  t=listSearch(key);
  if(t==nil)return ;
  deleteNode(t);
 } 
 
 
 void insert(int key){
  NodePointer x;
  x = malloc(sizeof(struct node));
  x->key = key;
  /* 
   your code 
  */
  if(nil->next==nil){
  	nil->prev=x;
  }
  x->next=nil->next;
  x->prev=nil;
   nil->next->prev=x;
   nil->next=x;
 } 
 
 int main(){
   int key, n, i;
   int size = 0;
   char com[20];
   int np = 0, nd = 0;
   scanf("%d", &n);
   init();
   for ( i = 0; i < n; i++ ){
     scanf("%s", com);
     if ( com[0] == 'i' ) {
 		scanf("%d",&key);
 		insert(key); np++; size++;
 	}
     else if ( com[0] == 'd' ) {
       if (strlen(com) > 6){
 	if ( com[6] == 'F' ) deleteFirst();
 	else if ( com[6] == 'L' ) deleteLast();
      } else {
 	scanf("%d",&key);
 	delete(key); nd++; 
      }
      size--;
    }
  }
   printList();
   return 0;
 }





*Search - Search I
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_A
両方の集合に共通する数字の個数を数える問題。
ソートして尺取虫、std::setを使うのも手。

 #include<stdio.h>
 #include<algorithm>
  
 int main(){
 	int S[10001],T[501],n,q,ans=0,p1=0,p2=0;
 	scanf("%d",&n);
 	for(int i=0;i<n;i++)scanf("%d",&S[i]);
 	scanf("%d",&q);
 	for(int i=0;i<q;i++)scanf("%d",&T[i]);
	std::sort(S,S+n);
 	std::sort(T,T+q);
 	while(p1<n&&p2<q){
 		if(S[p1]==T[p2]){
 			ans++;
 			p1++;
  			p2++;
 		}else if(S[p1]<T[p2]){
 			p1++;
 		}else{
 			p2++;
 		}
  	}
 	printf("%d\n",ans);
 }





*Search - Search II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B
前の問題と同じでデータ量が多いだけ。

 #include<stdio.h>
 #include<algorithm>
 
 int main(){
  	int S[100001],T[50001],n,q,ans=0,p1=0,p2=0;
 	scanf("%d",&n);
 	for(int i=0;i<n;i++)scanf("%d",&S[i]);
 	scanf("%d",&q);
 	for(int i=0;i<q;i++)scanf("%d",&T[i]);
 	std::sort(T,T+q);
 	while(p1<n&&p2<q){
  		if(S[p1]==T[p2]){
 			ans++;
 			p1++;
 			p2++;
 		}else if(S[p1]<T[p2]){
 			p1++;
 		}else{
  			p2++;
 		}
 	}
 	printf("%d\n",ans);
 }





*Search - Search III
まあそのstd::setを使えば一発だったんだけど。
一応ハッシュテーブルの学習用問題だと考えて計算。
ハッシュ関数の作りが適当なのはここだけの秘密、ただしい３２ビットハッシュ関数の作り方ってどんなんだろう？
AOJやっててよかったことは今のところ何もないので、評価値が下がろうが気にしない。



 #include<stdio.h>
 #include<string.h>
 #include<list>
  
 const int LIMIT =((1<<16)+33);
 std::list<int> hashTable[LIMIT];
 int h1(char *str){
    int p,p1,num,result=0;
    char c;
     
    for(p=0;p<strlen(str);p++){
        c=str[p];
        num=0;
        if(c=='A')num=0;
        if(c=='C')num=1;
        if(c=='G')num=2;
        if(c=='T')num=3;
        p1=(p%8)*2;
        result=((num<<p1)^result);
    }
    return result%LIMIT;
 }
 int h2(char *str){
    int num,result=0,b=1;
    char c;
    for(int p=0;p<strlen(str);p++){
        c=str[p];
        num=1;
        if(c=='A')num=1;
        if(c=='C')num=2;
        if(c=='G')num=3;
        if(c=='T')num=4;
        result+=num*b;
        b*=5;
    }
    return result;
 }
  
 bool find(char *str){
    int H1=h1(str);
    int H2=h2(str);
    for(std::list<int>::iterator it=hashTable[H1].begin();it!=hashTable[H1].end();it++){
        if(H2==(*it))return true;
    }
     return false;
 }
  
 void insert(char *str){
     if(find(str)==false){
         hashTable[h1(str)].push_front(h2(str));
     }
 }
  
 int main(){
    int n;
    char str[14],com[10];
    scanf("%d",&n);
    while(n--){
         scanf("%s %s",com,str);
         if(com[0]=='i'){
             insert(str);
         }else{
             printf("%s\n",find(str)?"yes":"no");
         }
     }   
 }






*Recursion / Divide and Conquer - Brute Force
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A
全探索で実装しなさいという指定だったのだけど。
動的計画法のほうが明らかに楽だよねこれ。
というわけで動的計画法で解。

 #include<stdio.h>
 #include<string.h>
 
 int main(){
 	int n,q,a,sum=0,m;
 	bool memo[40001];
 	memset(memo,0,sizeof(memo));
  	memo[0]=true;
 	scanf("%d",&n);	
 	for(int i=0;i<n;i++){
 		scanf("%d",&a);
 		for(int j=sum;j>=0;j--){
 			memo[j+a]=memo[j+a]||memo[j];
 		}
  		sum+=a;
 	}
 	scanf("%d",&q);
 	for(int i=0;i<q;i++){
 		scanf("%d",&m);
 		printf("%s\n",memo[m]?"yes":"no");
 	}
 }




*Recursion / Divide and Conquer - Merge Sort
マージソートを実装する問題。
指定通り記述するだけです。
マージソートは一番小さい単位まで分解してその中身をソート済みにする。
戻ってきた時に、ソート済みの両側を小さいほうからマージしていく。
イメージができていれば簡単な問題。

 #include<stdio.h>
 #include<string.h>
 
 const int SENTINEL=2147483647 ;
 int count=0;
  
 void Merge(int* A,int left,int mid,int right){
 	int n1=mid-left;
 	int n2=right-mid;
 	int *L=new int[n1+1];
	int *R=new int[n2+1];
 	for(int i=0;i<=n1-1;i++)L[i]=A[left+i];
 	for(int i=0;i<=n2-1;i++)R[i]=A[mid+i];
  	int i=0,j=0;
 	L[n1]=R[n2]=SENTINEL;
 	
 	for(int k=left;k<=right-1;k++){
 		count++;
 		if(L[i]<=R[j]){
 			A[k]=L[i];
 			i++;
 		}else{
 			A[k]=R[j];
 			j++;
 		}
 	}
 	delete []L;
 	delete []R;
 } 
  void Merge_Sort(int *A,int left,int right){
 	if(left+1<right){
 		int mid=(left+right)/2;
 		Merge_Sort(A,left,mid);
 		Merge_Sort(A,mid,right);
 		Merge(A,left,mid,right);
 	}
 }
 
 int main(){
 	int n;	
 	int *A=new int[500001];
 	scanf("%d",&n);
 	for(int i=0;i<n;i++)scanf("%d",&A[i]);
 	Merge_Sort(A,0,n);
  	for(int i=0;i<n;i++){
 		if(i>0)printf(" ");
 		printf("%d",A[i]);
 	}
 	printf("\n%d\n",count);
 	delete []A;
 }



*Recursion / Divide and Conquer - Koch Curve
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_C
コッホ曲線の座標を表示する問題
再帰でまあなんとか、もうちょっと一般のフラクタル図形を計算できるようにしたほうがいいかも、、、


 #include<stdio.h>
 #include<math.h>
 
 int n;
 const double toR=M_PI/180.0;
 
 void saiki(double px,double py,double len,double r,int deep){
 	if(deep==n){
 		if(px<0)px=-px;
  		if(py<0)py=-py;
 		printf("%lf %lf\n",px,py);
 		return ;
 	}
 	double nx,ny,len1;
 	len1=len/3.0;
 	saiki(px,py,len1,r,deep+1);
 	nx=px+len1*cos(r*toR);
 	ny=py+len1*sin(r*toR);
 	saiki(nx,ny,len1,r+60,deep+1);
 	nx+=len1*cos((r+60)*toR);
  	ny+=len1*sin((r+60)*toR);
 	saiki(nx,ny,len1,r-60,deep+1);
 	nx+=len1*cos((r-60)*toR);
 	ny+=len1*sin((r-60)*toR);
 	saiki(nx,ny,len1,r,deep+1);
 }
 
 int main(){
 	scanf("%d",&n);
  	saiki(0,0,100,0,0);
 	double a=100,b=0;
 	printf("%lf %lf\n",a,b);	
 }


*Sort II - Counting Sort
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_A
カウンティングソートを実装する問題。

小さいほうから尺取虫法的に積み上げていって。
最後に引きながら位置を決定していく。
4 4 4 1 1 1 5 5
ソート後
1 1 1 4 4 4 5 5
なら
4を含む４までの数は6回数えられてるから6,5,4か所目に入るというのを最後の処理でやっている。
なるほどいろいろな手を考えるものだと感心。

 #include<stdio.h>
 #include<math.h>
 
 const int LIMIT=2000001;
 int C[10001];
 int n;
 int A[LIMIT],B[LIMIT];
  
 void Counting_Sort(int *A,int *B,int k){
  	for(int i=0;i<=k;i++)C[i]=0;
 	for(int j=1;j<=n;j++){
 		C[A[j]]++;
 	}
 	for(int i=1;i<=k;i++){
  		C[i]+=C[i-1];
 	}
 	for(int j=n;j>=1;j--){
 		B[C[A[j]]]=A[j];
 		C[A[j]]--;
 	}
 }
 
 int main(){
 	scanf("%d",&n);	
 	for(int i=1;i<=n;i++)scanf("%d",&A[i]);
 	Counting_Sort(A,B,10000);
 	for(int i=1;i<=n;i++){
  		if(i>1)printf(" ");
 		printf("%d",B[i]);
 	}
 	printf("\n");
 }




*Sort II - Partition
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_Bクイックソートのパーティション操作を実装する問題。
ある数より小さいものを右に、大きいものを左に。
右側でも左側でも上と同じことを繰りかえせばクイックソート。


 #include<stdio.h>
 #include<math.h>
 
 const int LIMIT=100001;
  
 int Partition(int *A,int p,int r){
 	int x=A[r];
 	int i=p-1;
 	for(int j=p;j<=r-1;j++){
 		if(A[j]<=x){
  			i++;
 			int t=A[i];
 			A[i]=A[j];
 			A[j]=t;
 		}
 	}
 	int t=A[i+1];
 	A[i+1]=A[r];
 	A[r]=t;
 	return i+1;
 }
 
 int main(){
 	int A[LIMIT],n;
 	scanf("%d",&n);	
 	for(int i=1;i<=n;i++)scanf("%d",&A[i]);
 	int result=Partition(A,1,n);
 	for(int i=1;i<result;i++){
 		if(i>1)printf(" ");
 		printf("%d",A[i]);
  	}
 	printf(" [%d]",A[result]);
 	for(int i=result+1;i<=n;i++){
 		printf(" %d",A[i]);
 	}
 	printf("\n");
 }



*Sort II - Quick Sort
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_C
クイックソートを実装しその結果が安定かどうか判定する問題。

クイックソートは定義通り、あと順番が違ってるかは番号割り振ってそれが入れ替わっていたらに変更。

 #include<stdio.h>
 #include<math.h>
 #include<set>
 
 struct S{
 	int n,no;
 	char c;
 	bool operator<=(const S &s)const{
 		return n<=s.n;
 	}
 };
 const int LIMIT=100001;
 S A[LIMIT];
 int Partition(S *A,int p,int r){
 	S x=A[r];
 	int i=p-1;
 	for(int j=p;j<=r-1;j++){
  		if(A[j]<=x){
 			i++;
 			S t=A[i];
 			A[i]=A[j];
 			A[j]=t;
 		}
 	}
 	S t=A[i+1];
 	A[i+1]=A[r];
 	A[r]=t;	
 	return i+1;
 } 
 void Quicksort(S *A,int p,int r){
 	if(p<r){
 		int q=Partition(A,p,r);
 		Quicksort(A,p,q-1);
 		Quicksort(A,q+1,r);
 	}
 }
 
 int main(){
 	S s;
 	int n;
 	char c;
 	scanf("%d",&n);
  	for(int i=1;i<=n;i++){
 		scanf("%c%c %d",&c,&A[i].c,&A[i].n);	
 		A[i].no=i;
 	}
 	Quicksort(A,1,n);
 	bool isStable=true;
  	for(int i=1;i<n;i++){
 		if(A[i].n==A[i+1].n&&A[i].no>A[i+1].no)isStable=false;
 	}
 	
 	printf("%s\n",isStable?"Stable":"Not stable");
  	for(int i=1;i<=n;i++){
 		printf("%c %d\n",A[i].c,A[i].n);
 	}
 }


*Tree - Rooted Trees
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_A
与えられたデータから木構造を組み立てて組みあがった結果を出力する問題。
木の左側とその兄弟という表現法があるなんて知らなかった。
サンプルソースの意図が読めずちょっと苦労した。

 #include<stdio.h>
 #define MAX 100005
 #define NIL -1
 
 /*
 p: parent
 l: left-child
 r: right sibling
 */
 struct Node{ int p, l, r,d;};
 struct Node T[MAX]; // Tree
 int depth[MAX];
 
 /*
 */
 
 
 void print(int u){
  /*
   */
  printf("node %d: parent = %d, depth = %d, ",u,T[u].p,T[u].d);
  if(T[u].p==-1){
  	printf("root, [");
  }else if(T[u].l==NIL){
  	printf("leaf, [");
  }else{
  	printf("internal node, [");
  }
  int p=T[u].l;
 
  while(p!=NIL){
       if(p==T[u].l)printf("%d",p);
       else printf(", %d",p);
      p=T[p].r;
  }
   printf("]\n");
 }
 
 void calc_depth(int deep,int p){
 	T[p].d=deep;
 	if(T[p].l==NIL)return;
 	for(p=T[p].l;p!=NIL;p=T[p].r){
 		calc_depth(deep+1,p);
 	}
 } 
 
 int main(){
  int i, j, d, v, c, l,n;
 
  scanf("%d", &n);
 
  for ( i = 0; i < n; i++ ) {
    T[i].p = T[i].l = T[i].r = NIL;
  }
 
   for ( i = 0; i < n; i++ ){
    scanf("%d %d", &v, &d);
     int old=0;
     for ( j = 0; j < d; j++ ){
       scanf("%d", &c);
 	T[c].p=v;
  	if(j==0){
 		T[v].l=c;
 	}else{
 		T[old].r=c;
 	}
 	old=c;
    }
  }
    int p;
   for(int i=0;i<n;i++)if(T[i].p==-1)p=i;
   calc_depth(0,p); 
   for ( i = 0; i < n; i++ ) print(i);
   return 0;
 }




*Tree - Binary Trees
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_B
２分木を組み立てる問題。
まあいろいろ小手先の工夫で乗り切ります。
兄弟や階層や高さを求める処理を別枠にしておくことで処理がわかりやすくなりました。
特に書くことなし。

 #include<stdio.h>
 
 const int LIMIT=100001;
 const int NIL=-1;
 struct node{
 	int p,right,left,depth,height,sibling;
 };
 node Tree[LIMIT];
 
 int calc_depthAndHeight(int p,int deep){
  	if(Tree[p].left==NIL&&Tree[p].right==NIL){
 		Tree[p].depth=deep;
 		Tree[p].height=0;
 		return 1;
 	}else{
 		int h1=-1,h2=-1,h3;
 		if(Tree[p].left!=NIL)h1=calc_depthAndHeight(Tree[p].left,deep+1);
 		if(Tree[p].right!=NIL)h2=calc_depthAndHeight(Tree[p].right,deep+1);
 		h3=h1>h2?h1:h2;
 		Tree[p].height=h3;
 		Tree[p].depth=deep;
 		return h3+1;
 	}
 } 
  
 void print(int n){
 	for(int i=0;i<n;i++){
 		printf("node %d: parent = %d, sibling = %d, ",i,Tree[i].p,Tree[i].sibling);
 		int degree=(Tree[i].left!=-1)+(Tree[i].right!=-1);
 		printf("degree = %d, depth = %d, height = %d, ",degree,Tree[i].depth,Tree[i].height);
 		if(Tree[i].p==-1){
 			printf("root\n");
 		}else if(degree==0){
  			printf("leaf\n");
 		}else{
 			printf("internal node\n");
 		}
 	}
 }
 
 int main(){
 	int n,l,r,no;
 	scanf("%d",&n);
 	for(int i=0;i<n;i++)Tree[i].p=Tree[i].sibling=NIL;
 	for(int i=0;i<n;i++){
  		scanf("%d %d %d",&no,&l,&r);
 		Tree[no].left=l;
 		Tree[no].right=r;
 		Tree[l].p=Tree[r].p=no;
 		Tree[l].sibling=r;
 		Tree[r].sibling=l;
 	}
  	int p=0;
 	for(int i=0;i<n;i++)if(Tree[i].p==NIL)p=i;
 	int t=calc_depthAndHeight(p,0);
 	print(n);
 }