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

AOJ81~90 - (2011/08/15 (月) 16:29:25) のソース

*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
ただただ原始的に回して乗れない人数の最小ポイントを求めるだけ。

#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
ただ単に [, .] と単語を交互に読むだけ。

 #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のような頭に-のつく数字を忘れて2度も不正解を喰らう、こういうポカミスはよくないなあ。
簡単な問題なのに残念。


 #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
無意味に計算量とメモリ使用量を抑えたコードを書いてみた。
意外と短くかけたので満足。
この問題が難しく見えたなら、菱形をすこし斜めから見ると格子になるということを利用して解くとよい。


#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
シールが一枚の場合を忘れて一度不正解を喰らってしまう。
ちゃんと注意書きまであるのにはまる可能性もある問題。


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