「AOJ541~550」の編集履歴(バックアップ)一覧に戻る

AOJ541~550 - (2011/11/07 (月) 15:04:26) のソース

----
*0541 Walk
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0541
一定のルールで歩道を通る時最終的にどの地点に到達するかを答える問題。


解法
この問題はある地点を何回通るかということが重要となります。
スタート地点で考えてみましょう。
スタートが東で通る回数が1回のとき、2回のとき、、、n回のときと考えると。
nが奇数回目のときは必ず東に向かい、nが偶数回目のときは必ず南に向かいます。
この条件が全ての交差点で成り立ちます。
つまり、どの交差点も何回訪れたかで南か東かが決まります。
これを利用してスタートからn-1回目までの散歩を道路にまとめて流すと下記のようなコードとなります。
n-1回目までの結果、東南がどう変わったかを利用して最後のwhileが実行されます。




 #include<stdio.h>
 #include<string.h>
 int map[1002][1002];
 int memo[1002][1002];
 int h,w,n;
 void setData(){
	int x,y,t;
	for(y=0;y<h;y++){
		for(x=0;x<w;x++){
			scanf("%d",&map[y][x]);
		}
	}
	memset(memo,0,sizeof(memo));
	memo[0][0]=n-1;
	for(int y=0;y<h;y++){
		for(int x=0;x<w;x++){
			t=memo[y][x];
			if(map[y][x]==0){
				if(t%2==0){
					memo[y+1][x]+=t/2;
					memo[y][x+1]+=t/2;
				}else{
					map[y][x]=1;
					memo[y+1][x]+=t/2+1;
					memo[y][x+1]+=t/2;
				}
			}else{
				if(t%2==0){
					memo[y+1][x]+=t/2;
					memo[y][x+1]+=t/2;
				}else{
					map[y][x]=0;
					memo[y+1][x]+=t/2;
					memo[y][x+1]+=t/2+1;
				}
			}
		}
	}
	y=x=0;
	while(y<h && x<w){
		if(map[y][x]==0)y++;
		else 		x++;
	}
	printf("%d %d\n",y+1,x+1);
 }
 int main(){
	while(1){
		scanf("%d %d %d",&h,&w,&n);
		if(h==0 && w==0 && n==0) break;
		setData();
	}
 }


----
*0543 Receipt
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0543
レシートのデータで一つだけ金額がかすれているので残りの金額からかすれた部分の値段を求める問題。


解法
中学生にでも出題しそうな簡単な問題なので計算するだけです。 

 #include<stdio.h>
 int main(){
	int sum,all,i,t;
	while(1){
		scanf("%d",&all);
		if(all==0) break;
		i=9,sum=0;
		while(i--){
			scanf("%d",&t);
			sum+=t;
		}
		printf("%d\n",all-sum);
	}
 }



----
*0544 Sugoroku
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0544
すごろくの升目データとさいころの情報が与えられるので何手目でゴールできるかを答える問題。

解法
サイを振った後、升目の進む戻るで
ゴールを超えた升目を参照しないように注意さえすれば簡単な問題です。
コードをきれいにまとめられませんでした。

 #include<stdio.h>
 void setData(int n,int m){
	int map[1002];
	for(int i=1;i<=n;i++){
		scanf("%d",&map[i]);
	}
	int xai,nowP=1,ans;
	bool goal=false;
	for(int i=1;i<=m;i++){
		scanf("%d",&xai);
		if(goal==true) continue;
		nowP+=xai;
		if(n<=nowP){
			ans=i;
			goal=true;
			continue;
		}
		nowP+=map[nowP];
		if(n<=nowP){
			ans=i;
			goal=true;
		}
	}
	printf("%d\n",ans);
	
 }
 int main(){
	int n,m;
	while(1){
		scanf("%d %d",&n,&m);
		if(n==0 && m==0) break;
		setData(n,m);
	}
 }




----
*0545 Party
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0545
誰と誰が友達かの情報から、友達の友達が何人いるか答える問題です。

解法
友達の友達が実は単なる友達で探索が続く場合にさえ注意すれば再起探索で間に合う問題です。
素直に再起で実装しました。



 #include<stdio.h>
 #include<string.h>
 //簡単な問題なのでグローバル変数で手抜き
 const int max=502;
 bool con[max][max],moveOKs[max];
 int ans,n,m;
 void search(int deep,int no){
	//友達の友達が実は友達だった場合探索が続くので注意
	for(int i=2;i<=n;i++){
		if(con[no][i]){
			if(moveOKs[i]==true)ans++;
			moveOKs[i]=false;
			if(deep==0)search(deep+1,i);
		}
	}
 }
 void setData(){
	memset(con,    false, sizeof(con));
	memset(moveOKs,true , sizeof(moveOKs));
	moveOKs[1]=false;
	ans=0;
	int a,b;
	for(int i=0;i<m;i++){
		scanf("%d %d",&a,&b);
		con[a][b]=con[b][a]=true;
	}	
	search(0,1);
	printf("%d\n",ans);
 }
 int main(){
	while(1){
		scanf("%d %d",&n,&m);
		if(n==0 && m==0) break;
		setData();
	}
 }




----
*0546 Lining up the cards
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0546
10枚までの数字の書かれたカードの中から数枚選んでカードを並べるとき何通りの数が出来上がるか答えよという問題です。
 
解法
再起探索で全ての組み合わせを全生成し出来た数字を文字列としてstd::set<std::string> allに入れて重複を削除します。
後はall.sizeで答えが出ます。
グローバル変数を使わずに解いてみました。
実務ならグローバル変数はクラス内に隠されますし変数の受け渡し部分が煩わしくなるのであまり意味のないコードになりました。
素直にグローバル変数を使ったほうがよいという例です。


 #include <iostream> 
 #include<string>
 #include<set>
 #include<vector>
 #include<string.h>
 void saiki(	int deep,  std::string s,std::vector<std::string>& nums,
		bool moveOKs[11],  std::set<std::string>& all,  int k,  int n){
	if(k<=deep){
		//std::cout<<s<<"\n";
		all.insert(s);
	}else{
		for(int i=0;i<n;i++){
			if(moveOKs[i]==true){
				moveOKs[i]=false;
				saiki(deep+1,s+nums[i],nums,moveOKs,all,k,n);
				moveOKs[i]=true;
			}
		}
	}
 }
 void setData(int n,int k){
	std::set<std::string> all;
	std::vector<std::string> nums;
	std::string num;
	bool moveOKs[11];
	memset(moveOKs,true,11);
	for(int i=0;i<n;i++){
		std::cin>>num;
		nums.push_back(num);
	}
	saiki(0,"",nums,moveOKs,all,k,n);
	std::cout<<all.size()<<"\n";
 }
 int main(){
	int n,k;
	while(1){
		std::cin>>n>>k;
		if(n==0 && k==0) break;
		setData(n,k);
	}
 }