「AOJ241~250」の編集履歴(バックアップ)一覧に戻る

AOJ241~250 - (2012/07/11 (水) 15:08:09) の1つ前との変更点

追加された行は青色になります

削除された行は赤色になります。

 *0241 Quaternion Multiplication
 四元数の2つ組が与えられるので積を計算して返せという問題。
 マトリックスに対応表を作れば難しい式を書かなくて済みます。
 4元数の式を再帰下降構文解析で解釈し計算結果を出力せよという問題を出されたら100%解く自信がない。
 
 
  #include<stdio.h>
  #include<math.h>
  #include<string.h>
  //1=0,i=1,j=2,k=3,
  //-1=4,-i=5,-j=6,-k=7の対応表
  int set[4][4]={	{0,1,2,3},
 		{1,4,3,6},
 		{2,7,4,1},
 		{3,2,5,4}};
  void calc(){
 	//1,i,j,k,-1,-i,-j,-kに分けて集計する
 	int ans[8],k1[4],k2[4];
 	memset(ans,0,sizeof(ans));
 	for(int i=0;i<4;i++)scanf("%d",&k1[i]);
 	for(int i=0;i<4;i++)scanf("%d",&k2[i]);
 	for(int i=0;i<4;i++){
 		for(int j=0;j<4;j++){
 			ans[set[i][j]]+=k1[i]*k2[j];
 		}
 	}
 	//分けた分を整えて出す
 	for(int i=0;i<4;i++)printf("%s%d",i==0?"":" ",ans[i]-ans[4+i]);
 	printf("\n");
  }
  void setData(int n){
 	while(n--)calc();
  }
  int main(){
 	int n;
 	while(1){
 		scanf("%d",&n);
 		if(n==0)break;
 		setData(n);
+	}
+ }
+
+
+
+*0242 Input Candidates
+携帯電話の文字入力候補の簡易版を作る問題。
+入力された文字をMapを使ってカウントしてSetをつかって入力回数の多い順に並べ直すだけです。
+
+
+
+ #include<stdio.h>
+ #include<string>
+ #include<set>
+ #include<map>
+ struct WD{
+	int count;
+	std::string word;
+	bool operator<(const WD& wd)const{
+		if(count!=wd.count)return count>wd.count;
+		return word<wd.word;
+	}
+ };
+ void search(int n){
+	char w[22],c;
+	std::set<WD> memo[30];
+	std::set<WD>::iterator itS;
+	std::map<std::string,int> wdCount;
+	std::map<std::string,int>::iterator itM;
+	WD wd;
+	while(n){
+		scanf("%s%c",w,&c);
+		if(c=='\n')n--;
+		if(wdCount.find(w)==wdCount.end()){
+			wdCount[w]=1;
+		}else{
+			wdCount[w]++;
+		}
+	}
+	for(itM=wdCount.begin();itM!=wdCount.end();itM++){
+		wd.word=(*itM).first;
+		wd.count=(*itM).second;
+		c=wd.word[0]-'a';
+		memo[c].insert(wd);
+	}	
+	scanf("%s",w);
+	c=w[0]-'a';
+	if(memo[c].empty()){
+		printf("NA\n");
+	}else{
+		int count=0;
+		for(itS=memo[c].begin();count<5&&itS!=memo[c].end();itS++,count++){
+			printf("%s%s",count==0?"":" ",(*itS).word.c_str());
+		}
+		printf("\n");
+	}
+	
+ }
+ int main(){
+	int n;
+	while(1){
+		scanf("%d" ,&n);
+		if(n==0)break;
+		search(n);
 	}
  }