「AOJ181～190」の編集履歴（バックアップ）一覧はこちら

AOJ181～190 - (2011/08/29 (月) 18:53:35) の１つ前との変更点

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

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

*0181 Persistence
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0181
ｎ巻そろった本を1巻から順にｍ段の本棚に右下から詰めて入れます。
格段の本の幅が小さくなるようないれ方をした時、格段の本の幅の最大の幅がどれくらいとなるか答えよ。
本を詰める順番は1巻から順にし順番を違えないとする。

解法
i段目までｍ冊目までの本を入れた時、どのような入れ方をしたにせよ、そこまでの本の幅が最小となる入れ方のみを残します。
この考え方で動的計画法で解きます。



 #include<stdio.h>
 #include<algorithm>
 void setData(int m,int n){
	int memo[21][102],w=0;
    for(int i=0;i<21;i++){
        for(int j=0;j<102;j++){
            memo[i][j]=2000000000;
        }
    }
	memo[0][0]=0;
	for(int i=0;i<n;i++){
		scanf("%d",&w);
		memo[0][i+1]=memo[0][i]+w;
	}
	int t1,t2;
	for(int i=1;i<m;i++){
		for(int j=0;j<n;j++){
			for(int k=j+1;k<=n;k++){
				t1=memo[i-1][j];
                t1=t1==2000000000?0:t1;
                t2=memo[0][k]-memo[0][j];
				t1=std::max(t1,t2);
				memo[i][k]=std::min(memo[i][k],t1);
			}
		}
	}
	printf("%d\n",memo[m-1][n]);
 }
 int main(){
	int m,n;
	while(1){
		scanf("%d %d",&m,&n);
		if(m==0 && n==0) break;
		setData(m,n);
	}
 }



----
*0182　Beaker
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0182
ビーカーからビーカーへ水を移して、全てのビーカーに一度ずつ水を入れれるかという問題。

解法
正答まであと少しのコードを書いています。
タイムリミッドを喰らうのでどう高速化しようか思案中です。


 #include<stdio.h>
 #include<map>
 #include<vector>
 int inBeakers[51];
 int okBeakers[51];
 int beakerSize[51];
 bool butBeakers[51];
 int n;
 bool allOK;
 int allCount;
 void saiki(int spentBeaker,int measure,int p){
	if(spentBeaker==allCount && measure==0){
		allOK=true;
		return;
	}else if(measure==0){
		std::vector<int> memo;
		for(int i=0;i<n;i++){
			if(inBeakers[i]>0 && butBeakers[i]==false){
				inBeakers[i]--;
				saiki(spentBeaker,beakerSize[i],n-1);
				if(allOK==true) return;
				butBeakers[i]=true;
				inBeakers[i]++;
				memo.push_back(i);
			}
		}
		for(int i=0;i<memo.size();i++){
			butBeakers[memo[i]]=false;
		}
	}else{
		for(int i=p;i>=0;i--){
			if(okBeakers[i]>0 && measure>=beakerSize[i]){
				okBeakers[i]--;
				inBeakers[i]++;
				saiki(spentBeaker+1,measure-beakerSize[i],i);
				if(allOK==true) return;
				inBeakers[i]--;
				okBeakers[i]++;
			}
		}
	}
 }
 void setData(){
	std::map<int,int> beakers;
	std::map<int,int>::iterator it;
	int t;
	allOK=false;
	for(int i=0;i<n;i++){
		scanf("%d",&t);
		if(beakers.find(t)==beakers.end()){
			beakers[t]=1;
		}else{
			beakers[t]++;
		}
	}
	it=beakers.begin();
	allCount=n=0;
	while(it!=beakers.end()){
		okBeakers [n]=(*it).second;
		inBeakers [n]=0;
		butBeakers[n]=false;
		beakerSize[n]=(*it).first;
		allCount+=okBeakers[n];
		it++;
		n++;
	}
	okBeakers[n-1]--;
	if(n>1){
		saiki(1,beakerSize[n-1],n-1);
	}else{
		allOK=true;
	}
	printf("%s\n",allOK==true?"YES":"NO");
 }
 int main(){
	while(1){
		scanf("%d",&n);
		if(n==0) break;
		setData();
	}
 }





----
*0183
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0183
三目並べの勝敗を判定する問題です。

解法
縦横斜めを素朴にチェックするマトリックス*ｃを作るだけです。
ｂの2進数はｗのサブセットになっているのでビット演算を使って両者を判別することは困難です。
かわりにチェックする3マスの足し算を使うことにしました。
奇麗なコードを用意出来なかったのが少し残念です。



 #include<stdio.h>
 int main(){
 char i,d[2],s,m[10],*c="3331114201203602";
 int u;
 while(scanf("%s",&m[0])!=EOF){
	if(m[0]=='0')break;
	scanf("%s %s",&m[3],&m[6]);
	d[0]='d';
    d[1]='\0';
	for(i=0;i<8;i++){
		s=c[i+8]%8;
		u=(int)m[s]+(int)m[s+c[i]%8]+(int)m[s+2*(c[i]%8)];
		//ｂが３つかｗが３つか並んでたら
                if(u==3*98 || u==3*119){
			d[0]=u/3;
		}
	}
	printf("%s\n",d[0]=='d'?"NA":d);
 }




----
*0184 Tsuruga Castle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0184
解法
何も考えずに集計するだけです。
10の倍数であることを利用して割ることで少しだけコードが短くなります。

 #include<stdio.h>
 int main(){
	int n,y,sums[7],i;
	while(1){
		scanf("%d",&n);
		if(n==0) break;
		for(i=0;i<7;i++)sums[i]=0;
		for(i=0;i<n;i++){
			scanf("%d",&y);
			y=y>60?60:y;
			sums[y/10]++;
		}
		for(i=0;i<7;i++){
			printf("%d\n",sums[i]);
		}
	}
 }









----
*0185 Goldbach's Conjecture II
6以上の偶数を2つの素数の和で表した時何通りの表し方があるかを答える問題。

解法
エラトステネスの篩で素数のリストを生成します。
後は偶数の組み合わせはないので偶数を無視して集計するだけです。


 #include<stdio.h>
 #include<string.h>
 const int max=1000001;
 bool so[max];
 void setSo(){
	memset(so,true,max);
	for(int i=3;i<1001;i+=2){
		if(so[i]==false)continue;
		for(int j=i*3;j<max;j+=i*2){
			so[j]=false;
		}
	}
 }
 int main(){
	int n,sum;
	setSo();
	while(1){
		scanf("%d",&n);
		if(n==0) break;
		sum=0;
		for(int i=3;i<=n/2;i+=2){
			sum+=so[i]&&so[n-i]?1:0;
		}
		printf("%d\n",sum);
	}
 }






----
*0186
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0186
決められた予算と購入量の中、会津地鶏と普通の鶏を賢く購入する問題。

解法
この問題は一見線形計画法の問題に見えますが、変数が少ないためバイナリサーチで解けます。
会津地鶏を買う量を決めれば後は買うものが自動でもとまるという性質を利用して解きます。
もう少し問題が難しくなれば線形計画法を解くコードを書く必要があるでしょう。


 #include<stdio.h>
 void BinarySearch(int q1){
	int b,c1,c2,q2;
	int up=1000000,down=1,mid,ans=0,sum;
	scanf("%d %d %d %d",&b,&c1,&c2,&q2);
	
	do{
		mid=(down+up)/2;
		sum=mid+(b-mid*c1)/c2;
		if(mid>q2 || sum<q1 || b-mid*c1<0){
			up=mid-1;
		}else{
			ans=mid>ans?mid:ans;
			down=mid+1;
		}
	}while(down<=up);
	if(ans>0){
		printf("%d %d\n",ans,(b-ans*c1)/c2);
	}else{
		printf("NA\n");
	}
 }
 int main(){
	int q1;
	while(1){
		scanf("%d",&q1);
		if(q1==0)break;
		BinarySearch(q1);
	}
 }

*0181 Persistence
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0181
ｎ巻そろった本を1巻から順にｍ段の本棚に右下から詰めて入れます。
格段の本の幅が小さくなるようないれ方をした時、格段の本の幅の最大の幅がどれくらいとなるか答えよ。
本を詰める順番は1巻から順にし順番を違えないとする。

解法
i段目までｍ冊目までの本を入れた時、どのような入れ方をしたにせよ、そこまでの本の幅が最小となる入れ方のみを残します。
この考え方で動的計画法で解きます。



 #include<stdio.h>
 #include<algorithm>
 void setData(int m,int n){
	int memo[21][102],w=0;
    for(int i=0;i<21;i++){
        for(int j=0;j<102;j++){
            memo[i][j]=2000000000;
        }
    }
	memo[0][0]=0;
	for(int i=0;i<n;i++){
		scanf("%d",&w);
		memo[0][i+1]=memo[0][i]+w;
	}
	int t1,t2;
	for(int i=1;i<m;i++){
		for(int j=0;j<n;j++){
			for(int k=j+1;k<=n;k++){
				t1=memo[i-1][j];
                t1=t1==2000000000?0:t1;
                t2=memo[0][k]-memo[0][j];
				t1=std::max(t1,t2);
				memo[i][k]=std::min(memo[i][k],t1);
			}
		}
	}
	printf("%d\n",memo[m-1][n]);
 }
 int main(){
	int m,n;
	while(1){
		scanf("%d %d",&m,&n);
		if(m==0 && n==0) break;
		setData(m,n);
	}
 }



----
*0182　Beaker
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0182
ビーカーからビーカーへ水を移して、全てのビーカーに一度ずつ水を入れれるかという問題。

解法
正答まであと少しのコードを書いています。
タイムリミッドを喰らうのでどう高速化しようか思案中です。


 #include<stdio.h>
 #include<map>
 #include<vector>
 int inBeakers[51];
 int okBeakers[51];
 int beakerSize[51];
 bool butBeakers[51];
 int n;
 bool allOK;
 int allCount;
 void saiki(int spentBeaker,int measure,int p){
	if(spentBeaker==allCount && measure==0){
		allOK=true;
		return;
	}else if(measure==0){
		std::vector<int> memo;
		for(int i=0;i<n;i++){
			if(inBeakers[i]>0 && butBeakers[i]==false){
				inBeakers[i]--;
				saiki(spentBeaker,beakerSize[i],n-1);
				if(allOK==true) return;
				butBeakers[i]=true;
				inBeakers[i]++;
				memo.push_back(i);
			}
		}
		for(int i=0;i<memo.size();i++){
			butBeakers[memo[i]]=false;
		}
	}else{
		for(int i=p;i>=0;i--){
			if(okBeakers[i]>0 && measure>=beakerSize[i]){
				okBeakers[i]--;
				inBeakers[i]++;
				saiki(spentBeaker+1,measure-beakerSize[i],i);
				if(allOK==true) return;
				inBeakers[i]--;
				okBeakers[i]++;
			}
		}
	}
 }
 void setData(){
	std::map<int,int> beakers;
	std::map<int,int>::iterator it;
	int t;
	allOK=false;
	for(int i=0;i<n;i++){
		scanf("%d",&t);
		if(beakers.find(t)==beakers.end()){
			beakers[t]=1;
		}else{
			beakers[t]++;
		}
	}
	it=beakers.begin();
	allCount=n=0;
	while(it!=beakers.end()){
		okBeakers [n]=(*it).second;
		inBeakers [n]=0;
		butBeakers[n]=false;
		beakerSize[n]=(*it).first;
		allCount+=okBeakers[n];
		it++;
		n++;
	}
	okBeakers[n-1]--;
	if(n>1){
		saiki(1,beakerSize[n-1],n-1);
	}else{
		allOK=true;
	}
	printf("%s\n",allOK==true?"YES":"NO");
 }
 int main(){
	while(1){
		scanf("%d",&n);
		if(n==0) break;
		setData();
	}
 }





----
*0183 Black-and-White
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0183
三目並べの勝敗を判定する問題です。

解法
縦横斜めを素朴にチェックするマトリックス*ｃを作るだけです。
ｂの2進数はｗのサブセットになっているのでビット演算を使って両者を判別することは困難です。
かわりにチェックする3マスの足し算を使うことにしました。
奇麗なコードを用意出来なかったのが少し残念です。



 #include<stdio.h>
 int main(){
 char i,d[2],s,m[10],*c="3331114201203602";
 int u;
 while(scanf("%s",&m[0])!=EOF){
	if(m[0]=='0')break;
	scanf("%s %s",&m[3],&m[6]);
	d[0]='d';
    d[1]='\0';
	for(i=0;i<8;i++){
		s=c[i+8]%8;
		u=(int)m[s]+(int)m[s+c[i]%8]+(int)m[s+2*(c[i]%8)];
		//ｂが３つかｗが３つか並んでたら
                if(u==3*98 || u==3*119){
			d[0]=u/3;
		}
	}
	printf("%s\n",d[0]=='d'?"NA":d);
 }




----
*0184 Tsuruga Castle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0184
解法
何も考えずに集計するだけです。
10の倍数であることを利用して割ることで少しだけコードが短くなります。

 #include<stdio.h>
 int main(){
	int n,y,sums[7],i;
	while(1){
		scanf("%d",&n);
		if(n==0) break;
		for(i=0;i<7;i++)sums[i]=0;
		for(i=0;i<n;i++){
			scanf("%d",&y);
			y=y>60?60:y;
			sums[y/10]++;
		}
		for(i=0;i<7;i++){
			printf("%d\n",sums[i]);
		}
	}
 }









----
*0185 Goldbach's Conjecture II
6以上の偶数を2つの素数の和で表した時何通りの表し方があるかを答える問題。

解法
エラトステネスの篩で素数のリストを生成します。
後は偶数の組み合わせはないので偶数を無視して集計するだけです。


 #include<stdio.h>
 #include<string.h>
 const int max=1000001;
 bool so[max];
 void setSo(){
	memset(so,true,max);
	for(int i=3;i<1001;i+=2){
		if(so[i]==false)continue;
		for(int j=i*3;j<max;j+=i*2){
			so[j]=false;
		}
	}
 }
 int main(){
	int n,sum;
	setSo();
	while(1){
		scanf("%d",&n);
		if(n==0) break;
		sum=0;
		for(int i=3;i<=n/2;i+=2){
			sum+=so[i]&&so[n-i]?1:0;
		}
		printf("%d\n",sum);
	}
 }






----
*0186 Aizu Chicken
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0186
決められた予算と購入量の中、会津地鶏と普通の鶏を賢く購入する問題。

解法
この問題は一見線形計画法の問題に見えますが、変数が少ないためバイナリサーチで解けます。
会津地鶏を買う量を決めれば後は買うものが自動でもとまるという性質を利用して解きます。
もう少し問題が難しくなれば線形計画法を解くコードを書く必要があるでしょう。


 #include<stdio.h>
 void BinarySearch(int q1){
	int b,c1,c2,q2;
	int up=1000000,down=1,mid,ans=0,sum;
	scanf("%d %d %d %d",&b,&c1,&c2,&q2);
	
	do{
		mid=(down+up)/2;
		sum=mid+(b-mid*c1)/c2;
		if(mid>q2 || sum<q1 || b-mid*c1<0){
			up=mid-1;
		}else{
			ans=mid>ans?mid:ans;
			down=mid+1;
		}
	}while(down<=up);
	if(ans>0){
		printf("%d %d\n",ans,(b-ans*c1)/c2);
	}else{
		printf("NA\n");
	}
 }
 int main(){
	int q1;
	while(1){
		scanf("%d",&q1);
		if(q1==0)break;
		BinarySearch(q1);
	}
 }