※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

2086 !

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

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


#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まで8種類がランダムに、アルファベット小文字も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);
	}
}