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

AOJ2031～2040 - (2013/03/26 (火) 15:11:59) の編集履歴(バックアップ)

---

2031　Hyper Rock-Scissors-Paper

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2031
最大１０００人で15種類の手のあるじゃんけんを行う。
各人の出した手が与えられるので勝利した手を答えよ。
アイコの場合Drawと答えよ。

解法
全員同じ手の場合アイコになることに気づきさえすれば簡単な問題です。
ある手が勝っているとは、その手に勝ってる手が一つもないということでそれを検証するだけです。
勝ってる手がいなければアイコとなります。

#include<stdio.h>
#include<string>
#include<map>
#include<set>
#include<iostream>
std::string text[15]={"Rock","Fire","Scissors","Snake","Human","Tree","Wolf","Sponge","Paper","Air","Water","Dragon","Devil","Lightning","Gun"};
std::map<std::string,int> toNum;

void check(int n){
	int hit[15]={0};
	std::string str;
	for(int i=0;i<n;i++){
		std::cin>>str;
		hit[toNum[str]]=1;
	}
	int sum=0;
	for(int i=0;i<15;i++){
		sum+=hit[i];
}
	if(sum==1){
		printf("Draw\n");
		return ;
	}
	for(int i=0;i<15;i++){
 		if(hit[i]==0)continue;
		bool ok=true;
		for(int j=1;j<=7;j++){
			if(hit[(i+15-j)%15]==1){
 				ok=false;
			}
		}
		if(ok==true){
			std::cout<<text[i]<<"\n";
 			return ;
		}
	}
	printf("Draw\n");
}

int main(){
	for(int i=0;i<15;i++){
		toNum[text[i]]=i;
	}
 	int n;
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		check(n);
	}
}

2039　Space Coconut Crab II

三角形の周長Ｌが整数で与えられるので周長Ｌかつ三辺が全部素数になる三角形の数を答えよという問題。
周長は30000までとする。

解法
賢い方法を思いつきません。
素数表を求め全探索してみました。

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
const int up=30010;
std::vector<int> sosuu;
bool so[up+1];
void setSo(){
	int i2;
	memset(so,true,sizeof(so));
	so[0]=so[1]=false;
	for(int i=4;i<=up;i+=2)so[i]=false;
	sosuu.push_back(2);
 	for(int i=3;i<=up;i+=2){
		if(so[i]==false)continue;
 		sosuu.push_back(i);
		i2=i*2;
		for(int j=i*3;j<=up;j+=i2){
			so[j]=false;
		}
	}
}  
int table[up]={0};
int main(){
	setSo();
	std::vector<int>::iterator itA,itB,itC,itU;
	for(itA=sosuu.begin();itA!=sosuu.end();itA++){
		int a=(*itA);
		for(itB=itA;itB!=sosuu.end();itB++){
			int b=(*itB);
 			itU=std::lower_bound(sosuu.begin(),sosuu.end(),b+a);
			for(itC=itB;itC!=itU;itC++){
				int c=(*itC);
				if(a+b+c>=up||a+b<=c)break;
				table[a+b+c]++;
			}
 		}
	}
	int t;
	while(1){
		scanf("%d",&t);
		if(t==0)break;
		printf("%d\n",table[t]);
	}
}