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

2321～2330 - (2013/01/23 (水) 03:59:35) のソース

*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
海に一緒に行く友達の数を決定する問題。

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


 #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);
 }