「AOJ2081～2090」の編集履歴（バックアップ）一覧に戻る

AOJ2081～2090 - (2013/03/25 (月) 13:27:30) のソース

*2086　!
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2086
ｎ進数で表記された数ｍがある。
ｍ！をｎ進数で表したとき末尾にある0の数を答えよ。

解法
unsigned long long intでｍを数字になおして、後はｎ進数で表したとき末尾が0になるのはｍ！のなかにｎの素因数が何個あるか数えれば答えが出ます。


 #include<stdio.h>
 #include<string.h>
 #include<iostream>
 #include<map>
 void calcBase(int n,std::map<unsigned long long int,int>& base){
  	int ans=0;
	for(int i=2;i<=n;i++){
  		int p=0;
 		while(n%i==0){
 			n/=i;
 			p++;
 		}
 		if(p>0)base[i]=p;
 	}
 } 
  
 int main(){
 	int n;
 	char M[15];
 	std::map<unsigned long long int,int> base[37];
 	unsigned long long int num,p;
 	for(int i=8;i<=36;i++){
 		calcBase(i,base[i]);
 	}
 	while(1){
 		scanf("%d %s",&n,M);
 		if(n==0)break;
 		int len=strlen(M);
 		num=0;
 		p=1;
 		for(int i=len-1;i>=0;i--){
 			num+=(M[i]>='0'&&'9'>=M[i]?M[i]-'0':M[i]-'A'+10)*p;
 			p*=n;
  		}
 		
 		unsigned long long int t,b;
 		long long int ans=-1;
		for(std::map<unsigned long long int,int>::iterator it=base[n].begin();it!=base[n].end();it++){
  			t=0;
 			p=1;
 			b=(*it).first;
 			while(1){
 				p*=b;
 				t+=num/p;
 				if(num/p<b)break;
 			}
 			t/=(*it).second;
 			if(ans==-1||ans>t)ans=t;
 		}
 		std::cout<<ans<<"\n";
 	}
 }






*2089　Mysterious Dungeons
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2089
ダンジョンをⅠターンに一ます上下左右に移動して脱出する問題。
@が自分,<が出口＃は壁。
アルファベット大文字が岩で進入不可能。
アルファベット小文字がスイッチマスでスイッチのあるマスに入ると、同じ文字の大文字の岩が消える(aを踏んだらAが消える)。
岩が消えた状態でスイッチのあるマスに入ると岩が復活する(aに入るとAが復活する)。
アルファベット大文字はＡ～Ｚまで８種類がランダムに、アルファベット小文字もa～zまでランダムに出てくる。
スイッチだけ、岩だけしかない文字もある場合に注意すること。
最小移動数で出口まで到達するときの移動数を答えよ。


解法
スイッチ入ってる文字の組み合わせと今いるマスの組み合わせを点とみてグラフに翻訳すれば、後は動的計画法で一発です。


 #include<stdio.h>
 #include<string.h>
 #include<queue>
 
 struct S{
 	int x,y,turn;
 	int bits;
 }; 
 int memo[260][31][31];
 void search(int w,int h){
 	char map[32][32];
 	
 	int toNum[30]={0};
 	int bit=1;
	memset(memo,-1,sizeof(memo));
 	S s1,nextS;
 	std::queue<S> qu;
 	for(int i=0;i<h;i++){
 		scanf("%s",map[i]);
 		for(int j=0;j<w;j++){
 			char c1=map[i][j];
 			if(c1=='@'){
 				s1.x=j;
 				s1.y=i;
 				s1.turn=0;
 				s1.bits=0;
 				qu.push(s1);
 				map[i][j]='.';
  			}else if(c1=='.'||c1=='#'||c1=='<'){
 				//何もしない
 			}else{
 				//アルファベット
 				if('a'<=c1&&c1<='z'){
 					c1-='a';
 					if(toNum[c1]==0){
 						toNum[c1]=bit;
 						bit*=2;
 					}
 				}
 			}
 		}
 	}
 	int dxs[]={1,0,-1,0};
 	int dys[]={0,1,0,-1};
 	while(qu.empty()==false){
  		nextS=s1=qu.front();
 		qu.pop();
		//printf("(%d %d %d %d)",s1.x,s1.y,s1.bits,s1.turn);
  		if(map[s1.y][s1.x]=='<'){
 			printf("%d\n",s1.turn);
 			return ;
 		}
 		int turn=memo[s1.bits][s1.y][s1.x];
 		if(turn!=-1&&turn<=s1.turn)continue;
 		memo[s1.bits][s1.y][s1.x]=s1.turn;
 		nextS.turn++;
 		for(int i=0;i<4;i++){
 			nextS.x=s1.x+dxs[i];
 			nextS.y=s1.y+dys[i];
 			nextS.bits=s1.bits;
 			if(nextS.y<0||h<=nextS.y||nextS.x<0||w<=nextS.x)continue;
 			char c1=map[nextS.y][nextS.x];
 			if(c1=='#')continue;
 			if(c1=='.'||c1=='<'){
  				//何もしない
 			}else if('a'<=c1&&c1<='z'){
 				nextS.bits^=toNum[c1-'a'];
 			}else if('A'<=c1&&c1<='Z'){
 				if((nextS.bits&toNum[c1-'A'])==0)continue;
 			}
 			int turn=memo[nextS.bits][nextS.y][nextS.x];
 			if(turn!=-1&&turn<=nextS.turn)continue;
  			qu.push(nextS);
 		}
 	}
 	printf("-1\n");
 }
 
 int main(){
 	int w,h;
  	while(1){
 		scanf("%d %d",&w,&h);
 		if(w==0&&h==0)break;
 		search(w,h);
 	}
 }