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

「AOJ1110～1120」(2013/01/17 (木) 19:06:42) の最新版変更点

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

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

*1111　Cyber Guardian
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1111
パケットフィルタリングの実装をこれ以上できないほど簡素にした問題。
ｎ個のパケットルールとｍ個の通信許可の質問が与えられる。
パケットルールはpermit(通信ＯＫ)なアドレスと通信拒否すべきアドレス(deny)でＦｒｏｍからＴｏへ送信される場合をＯＫか拒否をあらわす。
後から提示されたルールほど優先順位が高いとして検査し、パケットルールで通信Ｏｋなアドレスト判明したら通信可としてそれを表示。
通信不可能なアドレスであることが判明したらそれは表示しない。
どのルールにも引っかからないアドレスは通信拒否とせよ。
通信可の通信データの数を表示しそのあと通信内容を到着順に表示せよ。


解法
この問題英語の読解がどうしてもできず他人のコードを少しだけ読んでしまいました。
題意さえつかめれば後は簡単ですが自力で解けなかったのは少し悔しいところです。




 #include<stdio.h>
 #include<string>
 #include<vector>
 #include<iostream>
 
 bool isOk(std::string str1,std::string str2){
 	for(int i=0;i<str2.size();i++){
 		if(str2[i]!='?'&&str1[i]!=str2[i]){
 			return false;
 		}
 	}
 	return true;
 }
  
 void check(int n,int m){
 	std::string str1,str2,str3;
 	std::vector<std::string> To,From,Type,ansMes;
 	for(int i=0;i<n;i++){
 		std::cin>>str1>>str2>>str3;
 		Type.push_back(str1);
 		From.push_back(str2);
 		To.push_back(str3);
 	}
 	for(int i=0;i<m;i++){
 		std::cin>>str1>>str2>>str3;
 		for(int j=Type.size()-1;j>=0;j--){
 			if(isOk(str1,From[j])==true&&isOk(str2,To[j])==true){
 				if(Type[j]=="permit"){
 					ansMes.push_back(str1+" "+str2+" "+str3);
 				}
 				break;
 			}
 		}
 	}
 	std::cout<<ansMes.size()<<"\n";
 	for(int i=0;i<ansMes.size();i++){
 		std::cout<<ansMes[i]<<"\n";
 	}
 }
 
 int main(){
 	int n,m;
 	
 	while(1){
 		scanf("%d %d",&n,&m);
 		if(n==0&&m==0)break;
 		check(n,m);
 	}
 }




*Multi-column List
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1115
指定された行数、幅、列数、列の隙間に最低限入れる.の数の設定で与えられた文章をカラム割して表示する問題。


解法
一行ずつデータを読んで一ページ分テキストを読んだら出力して改ページする状態遷移マシーンにデータを食わせるだけです。
次の行に遷移するデータと改行だけのデータの読み込みに注意するくらいですね。


 #include<stdio.h>
 #include<string.h>
 
 void outPutAndClear(char plens[101][60],int plen,int wSize){
  	for(int i=0;i<plen;i++)printf("%s\n",plens[i]);
 	printf("#\n");
 	memset(plens,'.',101*60);
 	for(int i=0;i<plen;i++){
 		plens[i][wSize]='\0';
 	}
 }
 
 void calc(int plen){
 	int cnum,width,cspace;
 	scanf("%d %d %d",&cnum,&width,&cspace);
 	int wSize=cnum*width+cspace*(cnum-1);
 	char plens[101][60];
 	char text[1002],c,t;
 	int lineNo=0;
 	memset(plens,'.',sizeof(plens));
 	for(int i=0;i<plen;i++){
 		plens[i][wSize]='\0';
 	}
 	scanf("%c",&c);
 	while(1){
 		scanf("%c",&c);
 		if(c=='?'){
 			if(lineNo>0){
 				outPutAndClear(plens,plen,wSize);
 			}
 			printf("?\n");
 			break;
  		}
 		if(c=='\n'){
 			lineNo++;
 			if(lineNo>=plen*cnum){
 				outPutAndClear(plens,plen,wSize);
 				lineNo=0;
 			}
 			continue;
 		}
 		text[0]=c;
 		int p=1;
 		while(1){
 			scanf("%c",&c);
 			if(c=='\n')break;
 			text[p++]=c;
 		}
 		text[p]='\0';
 		for(int i=0;i*width<strlen(text);i++){
 			int colP=(lineNo/plen)*(width+cspace);
 			int copySize=width>strlen(text)-i*width?strlen(text)-i*width:width;
 			memcpy(&plens[lineNo%plen][colP],&text[i*width],copySize);
 			lineNo++;
 			if(lineNo>=plen*cnum){
 				outPutAndClear(plens,plen,wSize);
 				lineNo=0;
 			}
 		}
 	}
 	
 }
 
 int main(){
 	int plen;
 	while(1){
 		scanf("%d",&plen);
 		if(plen==0)break;
 		calc(plen);
 	}
 }






*1117　Missing Numbers
？マークで表示された集計表データが複数与えられる。
？の部分を確定できるなら表の左上から順番に？に入るデータを一行ずつ表示せよ。
できないならＮＯと表示せよ。
出力はアウトプットの間に改行を一つ出力すること。

解法
数値データの行内か列内で？が一つならその部分を確定できます。
集計列か集計行のデータ内で？が一つならその部分を確定できます。
集計列と集計行から見て全集計の部分がだけ？ならその部分を確定できます。
確定できる部分を全部確定していって、確定できなくなるまでこれを続けます。
最後に全部確定できたかチェックして左上から表示するだけです。
賢い方法を思いつかなかったので全部の場合を地道にチェックしています。


 #include<stdio.h>
 #include<stdlib.h>
 #include<string.h>
 
 void calc(int p,int s,int turn){
 	char first[102][102][10],text[102][102][10];
 	int mat[102][102];
 	for(int r=0;r<=p;r++){
 		for(int c=0;c<=s;c++){
 			scanf("%s",first[r][c]);
 			if(first[r][c][0]!='?')sscanf(first[r][c],"%d",&mat[r][c]);
 		}
 	}
 	memcpy(text,first,sizeof(first));
 	while(1){
 		bool isChange=false;
 		int sum,sum1;
 		bool commitOK;
 		for(int r=0;r<p;r++){
 			for(int c=0;c<s;c++){
 				commitOK=true;
 				sum1=0;
 				if(text[r][c][0]=='?'&&text[p][c][0]!='?'){
 					sum=mat[p][c];
 					for(int dr=0;dr<p;dr++){
 						if(dr==r)continue;
 						if(text[dr][c][0]=='?')commitOK=false;
 						else sum1+=mat[dr][c];
 					}
 					if(commitOK==true){
 						text[r][c][0]='0';
 						mat[r][c]=sum-sum1;
 						isChange=true;
 					}
 				}
 				commitOK=true;
 				sum1=0;
 				if(text[r][c][0]=='?'&&text[r][s][0]!='?'){
 					sum=mat[r][s];
 					for(int dc=0;dc<s;dc++){
 						if(dc==c)continue;
 						if(text[r][dc][0]=='?')commitOK=false;
 						else sum1+=mat[r][dc];
 					}
 					if(commitOK==true){
						text[r][c][0]='0';
 						mat[r][c]=sum-sum1;
 						isChange=true;
 					}
 				}
 			}
 		}
 		int count=0,no;
 		sum1=0;
 		//右端列の確認
 		for(int r=0;r<p;r++){
 			if(text[r][s][0]=='?'){
 				count++;
 				no=r;
 			}else{
 				sum1+=mat[r][s];
 			}
 		}
 		//右端列の確定
 		if(count==1&&text[p][s][0]!='?'){
 			isChange=true;
 			mat[no][s]=mat[p][s]-sum1;
 			text[no][s][0]='0';
 		}
 		//全部集計の確定
 		if(count==0&&text[p][s][0]=='?'){
 			isChange=true;
 			mat[p][s]=sum1;
 			text[p][s][0]='0';
 		}
 		
 		//下段の確認
 		count=0,sum1=0;
 		for(int c=0;c<s;c++){
 			if(text[p][c][0]=='?'){
 				count++;
 				no=c;
 			}else{
 				sum1+=mat[p][c];
 			}
 		}
 		//下段の確定
 		if(count==1&&text[p][s][0]!='?'){
 			isChange=true;
 			mat[p][no]=mat[p][s]-sum1;
 			text[p][no][0]='0';
		}
 		//全部集計の確認
 		if(count==0&&text[p][s][0]=='?'){
 			isChange=true;
 			mat[p][s]=sum1;
 			text[p][s][0]='0';
 		}
 		
 		//右端列の確定
 		for(int r=0;r<p;r++){
 			count=0;
 			sum1=0;
 			for(int c=0;c<s;c++){
 				if(text[r][c][0]!='?'){
 					sum1+=mat[r][c];
 				}else{
 					count++;
 					break;
 				}
			}
 			if(count==0&&text[r][s][0]=='?'){
 				isChange=true;
  				mat[r][s]=sum1;
				text[r][s][0]='0';
 			}
 		}
 		//下段の確定
 		for(int c=0;c<s;c++){
 			count=0;
 			sum1=0;
 			for(int r=0;r<p;r++){
 				if(text[r][c][0]!='?'){
 					sum1+=mat[r][c];
  				}else{
 					count++;
 					break;
 				}
 			}
 			if(count==0&&text[p][c][0]=='?'){
 				text[p][c][0]='0';
 				mat[p][c]=sum1;
 				isChange=true;
 			}
 		}
 		
 		//for(int r=0;r<=p;r++){
 		//	for(int c=0;c<=s;c++){
 		//		printf("%4d",mat[r][c]);
 		//	}
		//	printf("\n");
 		//}
 		//int a;
  		//scanf("%d",&a);
 		if(isChange==false)break;
 	}
 	int allOK=true;
 	for(int r=0;r<=p;r++){
 		for(int c=0;c<=s;c++){
 			//printf("%5d",mat[r][c]);
 			if(text[r][c][0]=='?')allOK=false;
 		}
 	}
 	if(turn>0)printf("\n");
 	if(allOK==false){
 		printf("NO\n");
 		return ;
   	}
 	for(int r=0;r<=p;r++){
  		for(int c=0;c<=s;c++){
 			//printf("%5d",mat[r][c]);
 			if(first[r][c][0]=='?')printf("%d\n",mat[r][c]);
 		}
 	}
 	
 }
 
 int main(){
 	int p,s,c=0;
 	while(1){
 		scanf("%d",&p);
 		if(p==0)break;
 		scanf("%d",&s);
 		calc(p,s,c);
 		c++;
 	}
 }












*1119　　Exploring Caves
縦か横のみに移動するロボの移動データから、最も原点からロボが離れた時かつｘ座標が最も大きくなる点を求めよという問題。

中学生でも解ける問題から大学生でも悩む問題まで幅広くそろっているのが会津大学オンラインジャッジの特徴。
今日はこの通り中学生でも解ける問題を見つけたのでこまめに正答数を稼ぐ。
リニアに読み込むだけでいいので楽だ。


 #include<stdio.h>
 void setData(){
	int x=0,y=0,dx,dy,len,ans=0,ansX=0,ansY=0;	
	while(1){
		scanf("%d %d",&dx,&dy);
		if(dx==0&&dy==0)break;
		x+=dx;
		y+=dy;
		len=x*x+y*y;
		if(len>ans|| (len==ans&&x>ansX)){
			ansX=x;
			ansY=y;
			ans=len;
		}
	}
	printf("%d %d\n",ansX,ansY);
 }
 int main(){
	int n;
	scanf("%d",&n);
	while(n--)setData();
 }

*1111　Cyber Guardian
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1111
パケットフィルタリングの実装をこれ以上できないほど簡素にした問題。
ｎ個のパケットルールとｍ個の通信許可の質問が与えられる。
パケットルールはpermit(通信ＯＫ)なアドレスと通信拒否すべきアドレス(deny)でＦｒｏｍからＴｏへ送信される場合をＯＫか拒否をあらわす。
後から提示されたルールほど優先順位が高いとして検査し、パケットルールで通信Ｏｋなアドレスト判明したら通信可としてそれを表示。
通信不可能なアドレスであることが判明したらそれは表示しない。
どのルールにも引っかからないアドレスは通信拒否とせよ。
通信可の通信データの数を表示しそのあと通信内容を到着順に表示せよ。


解法
この問題英語の読解がどうしてもできず他人のコードを少しだけ読んでしまいました。
題意さえつかめれば後は簡単ですが自力で解けなかったのは少し悔しいところです。




 #include<stdio.h>
 #include<string>
 #include<vector>
 #include<iostream>
 
 bool isOk(std::string str1,std::string str2){
 	for(int i=0;i<str2.size();i++){
 		if(str2[i]!='?'&&str1[i]!=str2[i]){
 			return false;
 		}
 	}
 	return true;
 }
  
 void check(int n,int m){
 	std::string str1,str2,str3;
 	std::vector<std::string> To,From,Type,ansMes;
 	for(int i=0;i<n;i++){
 		std::cin>>str1>>str2>>str3;
 		Type.push_back(str1);
 		From.push_back(str2);
 		To.push_back(str3);
 	}
 	for(int i=0;i<m;i++){
 		std::cin>>str1>>str2>>str3;
 		for(int j=Type.size()-1;j>=0;j--){
 			if(isOk(str1,From[j])==true&&isOk(str2,To[j])==true){
 				if(Type[j]=="permit"){
 					ansMes.push_back(str1+" "+str2+" "+str3);
 				}
 				break;
 			}
 		}
 	}
 	std::cout<<ansMes.size()<<"\n";
 	for(int i=0;i<ansMes.size();i++){
 		std::cout<<ansMes[i]<<"\n";
 	}
 }
 
 int main(){
 	int n,m;
 	
 	while(1){
 		scanf("%d %d",&n,&m);
 		if(n==0&&m==0)break;
 		check(n,m);
 	}
 }




*1115　Multi-column List
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1115
指定された行数、幅、列数、列の隙間に最低限入れる.の数の設定で与えられた文章をカラム割して表示する問題。


解法
一行ずつデータを読んで一ページ分テキストを読んだら出力して改ページする状態遷移マシーンにデータを食わせるだけです。
次の行に遷移するデータと改行だけのデータの読み込みに注意するくらいですね。


 #include<stdio.h>
 #include<string.h>
 
 void outPutAndClear(char plens[101][60],int plen,int wSize){
  	for(int i=0;i<plen;i++)printf("%s\n",plens[i]);
 	printf("#\n");
 	memset(plens,'.',101*60);
 	for(int i=0;i<plen;i++){
 		plens[i][wSize]='\0';
 	}
 }
 
 void calc(int plen){
 	int cnum,width,cspace;
 	scanf("%d %d %d",&cnum,&width,&cspace);
 	int wSize=cnum*width+cspace*(cnum-1);
 	char plens[101][60];
 	char text[1002],c,t;
 	int lineNo=0;
 	memset(plens,'.',sizeof(plens));
 	for(int i=0;i<plen;i++){
 		plens[i][wSize]='\0';
 	}
 	scanf("%c",&c);
 	while(1){
 		scanf("%c",&c);
 		if(c=='?'){
 			if(lineNo>0){
 				outPutAndClear(plens,plen,wSize);
 			}
 			printf("?\n");
 			break;
  		}
 		if(c=='\n'){
 			lineNo++;
 			if(lineNo>=plen*cnum){
 				outPutAndClear(plens,plen,wSize);
 				lineNo=0;
 			}
 			continue;
 		}
 		text[0]=c;
 		int p=1;
 		while(1){
 			scanf("%c",&c);
 			if(c=='\n')break;
 			text[p++]=c;
 		}
 		text[p]='\0';
 		for(int i=0;i*width<strlen(text);i++){
 			int colP=(lineNo/plen)*(width+cspace);
 			int copySize=width>strlen(text)-i*width?strlen(text)-i*width:width;
 			memcpy(&plens[lineNo%plen][colP],&text[i*width],copySize);
 			lineNo++;
 			if(lineNo>=plen*cnum){
 				outPutAndClear(plens,plen,wSize);
 				lineNo=0;
 			}
 		}
 	}
 	
 }
 
 int main(){
 	int plen;
 	while(1){
 		scanf("%d",&plen);
 		if(plen==0)break;
 		calc(plen);
 	}
 }






*1117　Missing Numbers
？マークで表示された集計表データが複数与えられる。
？の部分を確定できるなら表の左上から順番に？に入るデータを一行ずつ表示せよ。
できないならＮＯと表示せよ。
出力はアウトプットの間に改行を一つ出力すること。

解法
数値データの行内か列内で？が一つならその部分を確定できます。
集計列か集計行のデータ内で？が一つならその部分を確定できます。
集計列と集計行から見て全集計の部分がだけ？ならその部分を確定できます。
確定できる部分を全部確定していって、確定できなくなるまでこれを続けます。
最後に全部確定できたかチェックして左上から表示するだけです。
賢い方法を思いつかなかったので全部の場合を地道にチェックしています。


 #include<stdio.h>
 #include<stdlib.h>
 #include<string.h>
 
 void calc(int p,int s,int turn){
 	char first[102][102][10],text[102][102][10];
 	int mat[102][102];
 	for(int r=0;r<=p;r++){
 		for(int c=0;c<=s;c++){
 			scanf("%s",first[r][c]);
 			if(first[r][c][0]!='?')sscanf(first[r][c],"%d",&mat[r][c]);
 		}
 	}
 	memcpy(text,first,sizeof(first));
 	while(1){
 		bool isChange=false;
 		int sum,sum1;
 		bool commitOK;
 		for(int r=0;r<p;r++){
 			for(int c=0;c<s;c++){
 				commitOK=true;
 				sum1=0;
 				if(text[r][c][0]=='?'&&text[p][c][0]!='?'){
 					sum=mat[p][c];
 					for(int dr=0;dr<p;dr++){
 						if(dr==r)continue;
 						if(text[dr][c][0]=='?')commitOK=false;
 						else sum1+=mat[dr][c];
 					}
 					if(commitOK==true){
 						text[r][c][0]='0';
 						mat[r][c]=sum-sum1;
 						isChange=true;
 					}
 				}
 				commitOK=true;
 				sum1=0;
 				if(text[r][c][0]=='?'&&text[r][s][0]!='?'){
 					sum=mat[r][s];
 					for(int dc=0;dc<s;dc++){
 						if(dc==c)continue;
 						if(text[r][dc][0]=='?')commitOK=false;
 						else sum1+=mat[r][dc];
 					}
 					if(commitOK==true){
						text[r][c][0]='0';
 						mat[r][c]=sum-sum1;
 						isChange=true;
 					}
 				}
 			}
 		}
 		int count=0,no;
 		sum1=0;
 		//右端列の確認
 		for(int r=0;r<p;r++){
 			if(text[r][s][0]=='?'){
 				count++;
 				no=r;
 			}else{
 				sum1+=mat[r][s];
 			}
 		}
 		//右端列の確定
 		if(count==1&&text[p][s][0]!='?'){
 			isChange=true;
 			mat[no][s]=mat[p][s]-sum1;
 			text[no][s][0]='0';
 		}
 		//全部集計の確定
 		if(count==0&&text[p][s][0]=='?'){
 			isChange=true;
 			mat[p][s]=sum1;
 			text[p][s][0]='0';
 		}
 		
 		//下段の確認
 		count=0,sum1=0;
 		for(int c=0;c<s;c++){
 			if(text[p][c][0]=='?'){
 				count++;
 				no=c;
 			}else{
 				sum1+=mat[p][c];
 			}
 		}
 		//下段の確定
 		if(count==1&&text[p][s][0]!='?'){
 			isChange=true;
 			mat[p][no]=mat[p][s]-sum1;
 			text[p][no][0]='0';
		}
 		//全部集計の確認
 		if(count==0&&text[p][s][0]=='?'){
 			isChange=true;
 			mat[p][s]=sum1;
 			text[p][s][0]='0';
 		}
 		
 		//右端列の確定
 		for(int r=0;r<p;r++){
 			count=0;
 			sum1=0;
 			for(int c=0;c<s;c++){
 				if(text[r][c][0]!='?'){
 					sum1+=mat[r][c];
 				}else{
 					count++;
 					break;
 				}
			}
 			if(count==0&&text[r][s][0]=='?'){
 				isChange=true;
  				mat[r][s]=sum1;
				text[r][s][0]='0';
 			}
 		}
 		//下段の確定
 		for(int c=0;c<s;c++){
 			count=0;
 			sum1=0;
 			for(int r=0;r<p;r++){
 				if(text[r][c][0]!='?'){
 					sum1+=mat[r][c];
  				}else{
 					count++;
 					break;
 				}
 			}
 			if(count==0&&text[p][c][0]=='?'){
 				text[p][c][0]='0';
 				mat[p][c]=sum1;
 				isChange=true;
 			}
 		}
 		
 		//for(int r=0;r<=p;r++){
 		//	for(int c=0;c<=s;c++){
 		//		printf("%4d",mat[r][c]);
 		//	}
		//	printf("\n");
 		//}
 		//int a;
  		//scanf("%d",&a);
 		if(isChange==false)break;
 	}
 	int allOK=true;
 	for(int r=0;r<=p;r++){
 		for(int c=0;c<=s;c++){
 			//printf("%5d",mat[r][c]);
 			if(text[r][c][0]=='?')allOK=false;
 		}
 	}
 	if(turn>0)printf("\n");
 	if(allOK==false){
 		printf("NO\n");
 		return ;
   	}
 	for(int r=0;r<=p;r++){
  		for(int c=0;c<=s;c++){
 			//printf("%5d",mat[r][c]);
 			if(first[r][c][0]=='?')printf("%d\n",mat[r][c]);
 		}
 	}
 	
 }
 
 int main(){
 	int p,s,c=0;
 	while(1){
 		scanf("%d",&p);
 		if(p==0)break;
 		scanf("%d",&s);
 		calc(p,s,c);
 		c++;
 	}
 }












*1119　　Exploring Caves
縦か横のみに移動するロボの移動データから、最も原点からロボが離れた時かつｘ座標が最も大きくなる点を求めよという問題。

中学生でも解ける問題から大学生でも悩む問題まで幅広くそろっているのが会津大学オンラインジャッジの特徴。
今日はこの通り中学生でも解ける問題を見つけたのでこまめに正答数を稼ぐ。
リニアに読み込むだけでいいので楽だ。


 #include<stdio.h>
 void setData(){
	int x=0,y=0,dx,dy,len,ans=0,ansX=0,ansY=0;	
	while(1){
		scanf("%d %d",&dx,&dy);
		if(dx==0&&dy==0)break;
		x+=dx;
		y+=dy;
		len=x*x+y*y;
		if(len>ans|| (len==ans&&x>ansX)){
			ansX=x;
			ansY=y;
			ans=len;
		}
	}
	printf("%d %d\n",ansX,ansY);
 }
 int main(){
	int n;
	scanf("%d",&n);
	while(n--)setData();
 }