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

2330 Earth Invasion Diary of Miyabi-sensei

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2330
コピーのドラキュラの中からオリジナルのドラキュラを見つける問題。
偽物金貨の問題と同じなので割り算するだけ。

#include<stdio.h>
int main(){
int n,c=0;
scanf("%d",&n);
n--;
while(n!=0){
	n/=3;
	c++;
}
printf("%d\n",c);
}


2331 A Way to Invite Friends

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2331
海に一緒に行く友達の数を決定する問題。

解法
友達を全部集めて2人で行きたい場合、3人で行きたい場合、、、m人で行きたい場合、、、n+1人で行きたい場合と挙手してもらいます。
挙手した人数がm人以上なら、そこからm人になるまで人数を減らせば答えと相成ります。


#include<stdio.h>
int add[100002]={0},dell[100002]={0};
int main(){
	int sum=1,n,ans=0,a,b;
	scanf("%d",&n);

	for(int i=0;i<n;i++){
		scanf("%d %d",&a,&b);
		add[a]++;
		dell[b+1]++;
	}
	for(int i=1;i<100002;i++){
		sum-=dell[i];
		sum+=add[i];
		if(i<=sum)ans=i;
	}
	printf("%d\n",ans-1);
}






2332 Space-Time Sugoroku Road

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2332
進む戻るのあるすごろくで最短ゴール手数が何手になるか答える問題。

解法
さいころを振った回数の少ないほうから優先して探すという条件のもと一度探索で通ったマスは二度使わないという条件で幅優先探索します。


#include<stdio.h>
#include<queue>
#include<string.h>
int memo[100010],board[100010];

struct S{
	int turn,p;
	bool operator<(const S& s)const{
		return turn>s.turn;
	}
};

 
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&board[i]);
	}
	memset(memo,-1,sizeof(memo));
	memo[1]=0;
	std::priority_queue<S> qu;
	S s,nextS;
	s.p=1;
	s.turn=0;
	qu.push(s);
	int ans=-1;
	while(qu.empty()==false){
		s=qu.top();
		qu.pop();
		if(ans!=-1&&s.turn>ans)break;
		if(board[s.p]!=0){
			int p2=s.p+board[s.p];
			if(p2>=n){
				if(ans==-1||ans>s.turn)ans=s.turn;
			}
			if(memo[p2]!=-1&&memo[p2]<=s.turn)continue;
 			memo[p2]=s.turn;
			s.p=p2;
			qu.push(s);
		}else{
			for(int i=1;i<=6;i++){
 				nextS.p=s.p+i;
				nextS.turn=s.turn+1;
				if(nextS.p>=n){
					if(ans==-1||ans>nextS.turn)ans=nextS.turn;
				}
				if(memo[nextS.p]!=-1&&memo[nextS.p]<=nextS.turn)continue;
				memo[nextS.p]=nextS.turn;
				qu.push(nextS);
			}
		}
	}
	printf("%d\n",ans);
}