AOJ81～90 - c21coterie @ ウィキ

0081　A Symmetric Point

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0081
平面上の直線Ｐ１Ｐ２と点Ｐ３が与えられるので、Ｐ１Ｐ２に対するＰ３の線対称な点を表示せよという問題。
教科書通りに線対称行列を書いてみましたがこの問題は色々な解法があると思います。

#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
ジョセフのおいもという古典問題です。
輪になりｋ人ごとに輪から一人ずつ抜けていき最後に残った人がお芋を食べるというゲームです。

解法
人数が少ないので単純にシミュレーションしても解けます。
それでは芸がないので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=' ';
	memo[y][x]=0;
	if(max<x) max=x;
       if(max>x) d=1;
               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);
}
}