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

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

AOJ81~90 - (2011/08/22 (月) 12:22:51) の最新版との変更点

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

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

 *0081 A Symmetric Point
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0081
 平面上の直線P1P2と点P3が与えられるので、P1P2に対するP3の線対称な点を表示せよという問題。
 教科書通りに線対称行列を書いてみましたがこの問題は色々な解法があると思います。
 
 
  #include<stdio.h>
  #include<math.h>
  int main(){
 	double xs[3],ys[3],vx,vy,x,y,len,sin1,cos1,sin2,cos2;
 	while(scanf("%lf,%lf,%lf,%lf,%lf,%lf",&xs[0],&ys[0],&xs[1],&ys[1],&xs[2],&ys[2])!=EOF){
 		vx=xs[1]-xs[0];
 		vy=ys[1]-ys[0];
 		len=sqrt(vx*vx+vy*vy);
 		sin1=vy/len;
 		cos1=vx/len;
 		sin2=2*sin1*cos1;
 		cos2=cos1*cos1-sin1*sin1;
 		vx=xs[2]-xs[0];
 		vy=ys[2]-ys[0];
 		x=vx*cos2+vy*sin2+xs[0];
 		y=vx*sin2-vy*cos2+ys[0];
 		printf("%lf %lf\n",x,y);
 	}
  }
 
 
 
 ----
 *0082 Flying Jenny
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0082
 メリーゴーランドを停止してお客さんを乗せる問題。
 メリーゴーランドは一人乗りの馬、二人乗りの、4人乗りと乗り物があり周囲で待っているお客さんは目の前の乗り物に即座に乗ります。
 この時定員オーバーで即座に乗れない人数を最小化する止め方を探してください。
 解法
 ただただ原始的に回して乗れない人数が最小化されるポイントを探すだけです。
 
  #include<stdio.h>
  #include<set>
  void calc(int m[8]){
 	int c[]={1,4,1,4,1,2,1,2},ans=2000000000,sum,ansNo=99999999,nowNo,t,p,ansPoint;
 	
 	for(int i=0;i<8;i++){
 		sum=nowNo=0;
 		for(int j=0;j<8;j++){
 			p=(i+j)%8;
 			nowNo*=10;
 			nowNo+=c[p];
 			t=m[j]-c[p];
 			sum+=t>0?t:0;
 		}
 		if(sum<ans || (sum==ans && ansNo>nowNo)){
 			ansNo=nowNo;
  			ans=sum;
 			ansPoint=i;
 		}
 	}
 	printf("%d",c[ansPoint]);
 	for(int i=1;i<8;i++) printf(" %d",c[(ansPoint+i)%8]);
 	printf("\n");
  }
  int main(){
 	int m[8];
 	while(1){
 		for(int i=0;i<8;i++){
 			if(scanf("%d",&m[i])==EOF) return 0;
 		}
 		calc(m);
 	}
  }
 
 
 
 *0083 Era Name Transformation
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0083
 西暦を元号に変換するという問題。
 解法
 年月日を数字と見ればこの問題は判別が簡単になります。
 月日はかわらないので年で分岐するだけです。
 
 
  #include<stdio.h>
  int main(){
 	int y,m,d,v;
 	char *s;
 	while(scanf("%d %d %d",&y,&m,&d)!=EOF){
 		v=y*10000+m*100+d;
 		if(v<18680908){
 			printf("pre-meiji\n");
 		}else if(v<19120730){
 			printf( "meiji %d %d %d\n",y-1867,m,d);
 		}else if(v<19261225){
 			printf("taisho %d %d %d\n",y-1911,m,d);
 		}else if(v<19890108){
 			printf( "showa %d %d %d\n",y-1925,m,d);
 		}else{
 			printf("heisei %d %d %d\n",y-1988,m,d);
 		}
 	}
  }
 
 
 *0084 Search Engine
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0084
 英単語の文章が区切り文字付きで与えられるのでそれから3~6文字までの単語を切り出して表示せよという問題。
 解法
 ただ単に [, .] と単語を交互に読むだけで済みます。
 
 
  #include<stdio.h>
  #include<string.h>
  int main(){
 	char word[1025],first=0,len;
 	while(scanf("%[^ .,]",word)!=EOF){
 		len=strlen(word);
 		if(2<len && len<7){
 			if(first==0){
 				first=1;
 			}else{
 				printf(" ");
 			}
 			printf("%s",word);
 		}
 		if(scanf("%[., ]",word)==EOF) break;
 	}
 	printf("\n");
  }
 
 
 
 
 ----
 *0085 Joseph's Potato
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0085
 ジョセフのおいもという古典問題です。
 輪になりk人ごとに輪から一人ずつ抜けていき最後に残った人がお芋を食べるというゲームです。
 
 解法
 人数が少ないので単純にシミュレーションしても解けます。
 それでは芸がないのでhttp://d.hatena.ne.jp/eha_s/20101201/1291129877を参考にコードを書いてみました。
 原理は曖昧です。
 (,,,((k%2+k)%3+k)%4+,,,)+k)%n;
 という数式が答えを導くようなのですが私には原理がよくわかりませんでした。
 
 
  #include<stdio.h>
  int f(int n,int k){
 	if(n==1) return 0;
 	return (f(n-1,k)+k)%n;
  }
  int main(){
 	int n,k;
 	scanf("%d %d",&n,&k);
 	while(n!=0 || k!=0){
 		printf("%d\n",f(n,k)+1);
 		scanf("%d %d",&n,&k);
 	}
  }
 
 
 
 
 ----
 *0086 Patrol
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0086
 地点とそれをつなぐ道、出発点とゴールが与えられるので全ての道を通りゴールにたどり着くルートがあるかを調べる問題。
 解法
 単なる一筆書きの問題なのでオイラーの定理を適用します。
 出発点とゴールに入る道の数が奇数でそれ以外の点に入る道の数は偶数なら巡回することができます。
 この問題は地点が連番で100番以下になっていることを利用して解きます。
 
  #include <stdio.h>
  bool solve(){
  int map[104]={0},m1,m2;
-
 	while(1){
 		if(scanf("%d %d",&m1,&m2)==EOF){
 			return false;
 		}
 		if(m1==0 && m2==0){
 			break;
 		}
 		map[m1]++;
 		map[m2]++;
 	}
 	char *c="OK";
 	if(map[1]%2!=1 && map[2]%2!=1){
 		c="NG";
 	}else{
 		for(int i=3;i<104;i++){
 			if(map[i]%2==1){
 				c="NG";
 				break;
 			}
 		}
 	}
 	printf("%s\n",c);
 	return true;
  }
  int main()
  {
 	while(solve()){
 	}	
  }
 
 
 
 
 ----
 *0087 Strange Mathematical Expression
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0087
 逆ポーランド記法で数式が与えらるのでその数式の計算結果を表示せよという問題。
 解法
 数字をスタックに積んでいき、四則演算にあったらスタックから数字を取り出して計算して結果をスタックに戻す作業を繰り返すことで簡単に計算できます。
  ,-12のような頭に-のつく数字を忘れるなどのポカミスに注意したい問題。
 
 
  #include<stdio.h>
  #include<stack>
  #include<string.h>
  bool set(){
 	char text[80],t;
 	std::stack<double> calc;
 	double d1,d2;
 	
 	while(1){
 		if(scanf("%s",text)==EOF) return false;
 		t=text[0];
 		if(('0'<=t && t<='9') || t=='.' || strlen(text)>1){
 			sscanf(text,"%lf",&d1);
 			calc.push(d1);
 		}else if(calc.size()>1){
 			d1=calc.top();
 			calc.pop();
 			d2=calc.top();
 			calc.pop();
 			if(t=='+'){
 				d2=d2+d1;
 			}else if(t=='*'){
 				d2=d2*d1;
 			}else if(t=='/'){
 				d2=d2/d1;
 			}else if(t=='-'){
 				d2=d2-d1;
 			}
 			calc.push(d2);
 		}
 		if(scanf("%c",&t)==EOF){
 			printf("%lf",calc.top());
 			return false;
 		}
 		if(t=='\n') break;
 	}
 	printf("%lf\n",calc.top());
 	return true;
  }
  int main(){
 	while(set()){
 	}
  }
 
 
 
 
 
 ----
 *0088 The Code A Doctor Loved
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0088
-ただひたすら表を作るのがめんどくさいだけの問題。
-アルゴリズムは速度より短さより奇麗さ重視で作成。
+コード表に従って文字列をコードに変換せよという問題。
+
+解法
+変換表をテーブル化しておき後は順番に読み込んで変換するだけです。
+非常に小さなコードサイズで実装している人もいるのでこの問題は賢い方法があるのかもしれません。
 
 
  #include <iostream>
  #include <map>
  #include <string>
  using namespace std;
  map<char,string> d;
  map<string,string> o;
  string calcNo(int no){
 	string ans="01234";
 	for(int i=0;i<5;i++){
 		ans[4-i]=(no&1)+'0';
 		no=no>>1;
 	}
 	return ans;
  }
  void setData2(){
 	for(int i=0;i<26;i++){
 		o[calcNo(i)]='A'+i;
 	}
 	o["11010"]=' ';
 	o["11011"]='.';
 	o["11100"]=',';
 	o["11101"]='-';
 	o["11110"]='\'';
 	o["11111"]='?';
  }
  void setData(){
 	d[' ']="101";
 	d['\'']="000000";
 	d[',']="000011";
 	d['-']="10010001";
 	d['.']="010001";
 	d['?']="000001";
 	d['A']="100101";
 	d['B']="10011010";	
 	d['C']="0101";
 	d['D']="0001";
 	d['E']="110";
 	d['F']="01001";
 	d['G']="10011011";
 	d['H']="010000";
 	d['I']="0111";
 	d['J']="10011000";
 	d['K']="0110";
 	d['L']="00100";
 	d['M']="10011001";
 	d['N']="10011110";
 	d['O']="00101";
 	d['P']="111";
 	d['Q']="10011111";
 	d['R']="1000";	
 	d['S']="00110";
 	d['T']="00111";
 	d['U']="10011100";
 	d['V']="10011101";
 	d['W']="000010";
 	d['X']="10010010";
 	d['Y']="10010011";
 	d['Z']="10010000";
  }
  int main(){
 	setData();
 	setData2();
 	string text,text2,text3;
 	int len;
 	while(1){
 		text=text2=text3="";
 		getline(cin,text);
 		if(cin.eof()==true)return 0;
 		len=text.size();
 		for(int i=0;i<len;i++){
 			text2.append(d[text[i]]);
 		}
 		len=text2.size()%5;
 		if(len>0) for(int i=len;i<5;i++) text2.append("0");
 		len=text2.size();
 		for(int i=0;i<len;i+=5){
 			text3.append(o[text2.substr(i,5)]);
 		}
 		cout<<text3<<"\n";
 	}
  }
 
 
 
 
 
 ----
 *0089 The Shortest Path on A Rhombic Path
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0089
-無意味に計算量とメモリ使用量を抑えたコードを書いてみた。
-意外と短くかけたので満足。
-この問題が難しく見えたなら、菱形をすこし斜めから見ると格子になるということを利用して解くとよい。
+菱形に並んだ数字が与えられるので菱形の上から下まで行くときに最も値の計が大きくなる経路を探すという問題です。
 
+解法
+メモリを抑えて順当に計算するだけです。
+菱形の幅が小さくなる部分でdを変更するのがポイントです。
+この式が難しく見えたなら菱形を斜めからみると格子になるということを利用して解けばよいでしょう。
 
  #include<stdio.h>
  int main(){
 	int memo[2][102]={0},y=1,x,t1,t2,max=0,d=0;
 	char re=' ';
 	scanf("%d",&memo[0][1]);
     x=3;
 	while(x>2){
 		x=1;
 		while(re!='\n'){
 			scanf("%d",&memo[y][x]);
 			scanf("%c",&re);
 			x++;
 		}
-        re=' ';
+                re=' ';
 		memo[y][x]=0;
 		if(max<x) max=x;
         if(max>x) d=1;
-        for(int i=0;i<x-1;i++){
+                for(int i=0;i<x-1;i++){
 			t1=memo[(y+1)%2][i+d]+memo[y][i+1];
 			t2=memo[(y+1)%2][i+1+d]+memo[y][i+1];
 			memo[y][i+1]=t1>t2?t1:t2;
 		}
 		y=(y+1)%2;
 	}
     printf("%d\n",memo[(y+1)%2][1]);
  }
 
 
 
 
 
 ----
 *0090 Overlaps of Seals
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0090
-シールが一枚の場合を忘れて一度不正解を喰らってしまう。
-ちゃんと注意書きまであるのにはまる可能性もある問題。
+10*10サイズの紙の上に半径1のシールが多数貼られています。
+シールの座標から最もシールが差なっている部分の枚数を答えよという問題。
+
+解法
+シールの交点を求め、その交点に何枚のシールが重なっているかを計算します。
+もっともシールの重なりが多い点が答えとなります。
+シールが一枚の場合を忘れないように実装しましょう。
 
 
  #include<stdio.h>
  #include<math.h>
  void calc(int n){
 	double xs[101],ys[101],vx,vy,len,px[2],py[2],cosA,cosB,sinA,sinB;
 	int ans=1;
 
 	for(int i=0;i<n;i++){
 		scanf("%lf,%lf",&xs[i],&ys[i]);
 	}
 	
 	
 	for(int i=0;i<n;i++){
 		for(int j=i+1;j<n;j++){
 			vx=(xs[j]-xs[i]);
 			vy=(ys[j]-ys[i]);
 			len=vx*vx+vy*vy;
 			//printf("(%lf)",len);
 			if(len>4.0) continue;
 			if(len==4.0){
 				px[0]=px[1]=(xs[i]+xs[j])/2.0;
 				py[0]=py[1]=(ys[i]+ys[j])/2.0;
 			}else{
 				sinB=sqrt(1.0-len/4.0);
 				len=sqrt(len);
 				
 				cosB=len/2.0;
 				cosA=vx/len;
 				sinA=vy/len;
 				
 				px[0]=cosB*cosA-sinB*sinA+xs[i];
 				py[0]=cosA*sinB+cosB*sinA+ys[i];
 				px[1]=cosB*cosA+sinB*sinA+xs[i];
 				py[1]=cosB*sinA-sinB*cosA+ys[i];
 			}
 			for(int l=0;l<2;l++){
 				int temp=0;
 				for(int k=0;k<n;k++){
 					if(k==i || k==j) temp++;
 					else temp+=((px[l]-xs[k])*(px[l]-xs[k])+(py[l]-ys[k])*(py[l]-ys[k]))<=1.0?1:0;
 				}
 				ans=ans>temp?ans:temp;
 			}
 		}
 	}
 	printf("%d\n",ans);
  }
  int main(){
 	int n=1;
 	while(1){
 		scanf("%d",&n);
 		if(n==0) break;
 		calc(n);
 	}
  }