「AOJ61～70」の編集履歴（バックアップ）一覧はこちら

AOJ61～70 - (2011/08/12 (金) 22:23:09) の１つ前との変更点

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

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

*0061　Rank Checker
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0061
チームデータを確保してベクターに確保。
ソートして上位チームの番号と順位をＭａｐに保存。
愚直に実装、もう少し賢い方法がありそうだけど？


#include<stdio.h>
#include<vector>
#include<map>
#include <algorithm>
struct team{
	int no,p;
	bool operator<(const team t)const {
		return p>t.p;
	}
};

int main(){
	std::vector<team> teams;
	team t;
	do{
		scanf("%d,%d",&t.no,&t.p);
		teams.push_back(t);
	}while(t.no!=0 && t.p!=0);
	std::sort(teams.begin(),teams.end());
	std::vector<team>::iterator it=teams.begin();
	int rank=1,p=(*it).p;
	std::map<int,int> memo;
	while(it!=teams.end()){
		if(p==(*it).p){
			memo[(*it).no]=rank;
		}else{
			p=(*it).p;
			rank++;
			memo[(*it).no]=rank;
		}
		it++;
	}
	while(scanf("%d",&p)!=EOF){
		printf("%d\n",memo[p]);
	}
}





----
*0062 What is the Bottommost?
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0062
最初、一段ずつちまちま計算するコードで正答。
他の人のコードをみてこちらのコードに変更。
何個めの数字が最下段に行くまでに何回足されるかを計算するとcomになるという性質を利用して最アセプト。

#include<stdio.h>
int main(){
	char t[11];
	int sum,com[]={1,10,45,120,210};
	while(scanf("%s",t)!=EOF){
		sum=0;
		for(int i=0;i<5;i++) sum+=com[i]*(t[i]+t[9-i]-96);
		printf("%d\n",sum%10);
	}
}




----
*0063　Palindrome
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0063
普通にアセプト。
stdには、配列をリバースするメソッドがあるのでそれを使うともっと簡単になるらしい。

#include<stdio.h>
#include<string.h>
int main(){
	char text[101];
	bool ok;
	int len,ans=0;
	while(scanf("%s",text)!=EOF){
		ok=true;
		len=strlen(text);
		for(int i=0;i<len/2;i++){
			if(text[i]!=text[len-i-1]){
				ok=false;
				break;
			}
		}
		ans+=ok?1:0;
	}
	printf("%d\n",ans);
}





----
*0064　Secret Number
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0064
状態遷移マシンを作って簡単にアセプト。
一行ずつでなく一文字ずつ読み込めばもっとコードがシンプルになるようだ。
状態遷移マシンとしてみた場合一番簡単な部類に入ると思う。


#include<stdio.h>
#include<string.h>
int main(){
	char t[81];
	int len,mod,sum=0,ans=0;
	while(scanf("%s",t)!=EOF){
		len=strlen(t);
		mod=0;
		sum=0;
		for(int i=0;i<len;i++){
			if('0'<=t[i] && t[i]<='9'){
				sum*=10;
				sum+=t[i]-'0';
			}else{
				ans+=sum;
				sum=0;
			}
		}
		ans+=sum;
	}
	printf("%d\n",ans);
}





----
*0065　Trading
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0065
今月の取引と先月の取引を別々にカウント。
月データが複数になった場合はvector<map<int,int>>のようなコードが必要になる？
愚直に実装したがもう少し簡単なコードになるような気もする。

#include<stdio.h>
#include<map>


int main(){
	int no,day;
	char re[3];
	std::map<int,int> now,old;
	
	while(1){
		scanf("%d,%d",&no,&day);
		if(now.find(no)==now.end()){
			now[no]=1;
		}else{
			now[no]++;
		}
		scanf("%[\n]",re);
		if(re[1]!='\0') break;
	}
	while(scanf("%d,%d",&no,&day)!=EOF){
		if(old.find(no)==old.end()){
			old[no]=1;
		}else{
			old[no]++;
		}
	}
	std::map<int,int>::iterator it=old.begin();
	while(it!=old.end()){
		if(now.find((*it).first)!=now.end()){
			printf("%d %d\n",(*it).first,(*it).second+now[(*it).first]);
		}
		it++;
	}
}







----
*0067 The Number of Island
入力データの終了条件がよくわからないので何度も不正解を喰らってしまった問題。
問題自体は簡単だったし典型的な探索処理なのですが終了条件で手間取った。
なんか意地悪な問題。


#include<stdio.h>

int dxs[]={1,0,-1,0},dys[]={0,1,0,-1};
char map[12][13];

void saiki(int x,int y){
	int nx,ny;
	for(int i=0;i<4;i++){
		nx=x+dxs[i];
		ny=y+dys[i];
		if(nx<0 || 11<nx || ny<0 || 11<ny ||map[ny][nx]=='0') continue;
		map[ny][nx]='0';
		saiki(nx,ny);
	}
}

bool setMap(){
	for(int i=0;i<12;i++){
		if(scanf(" %12s",map[i])==EOF) return false;
    }
    int x,y,i,count=0;
    for(i=0;i<144;i++){
    	x=i%12;
    	y=i/12;
		if(map[y][x]=='1'){
			map[y][x]='0';
			count++;
			saiki(x,y);
		}
    }
    printf("%d\n",count);
    return true;
}
int main(){
	char s1;
	do{
		if(setMap()==false) break;
		if(scanf("%c",&s1)==EOF) break;
	}while(scanf("%c",&s1)!=EOF);
}

*0061　Rank Checker
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0061
チームデータを確保してベクターに確保。
ソートして上位チームの番号と順位をＭａｐに保存。
愚直に実装、もう少し賢い方法がありそうだけど？


#include<stdio.h>
#include<vector>
#include<map>
#include <algorithm>
struct team{
	int no,p;
	bool operator<(const team t)const {
		return p>t.p;
	}
};

int main(){
	std::vector<team> teams;
	team t;
	do{
		scanf("%d,%d",&t.no,&t.p);
		teams.push_back(t);
	}while(t.no!=0 && t.p!=0);
	std::sort(teams.begin(),teams.end());
	std::vector<team>::iterator it=teams.begin();
	int rank=1,p=(*it).p;
	std::map<int,int> memo;
	while(it!=teams.end()){
		if(p==(*it).p){
			memo[(*it).no]=rank;
		}else{
			p=(*it).p;
			rank++;
			memo[(*it).no]=rank;
		}
		it++;
	}
	while(scanf("%d",&p)!=EOF){
		printf("%d\n",memo[p]);
	}
}





----
*0062 What is the Bottommost?
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0062
最初、一段ずつちまちま計算するコードで正答。
他の人のコードをみてこちらのコードに変更。
何個めの数字が最下段に行くまでに何回足されるかを計算するとcomになるという性質を利用して最アセプト。

#include<stdio.h>
int main(){
	char t[11];
	int sum,com[]={1,10,45,120,210};
	while(scanf("%s",t)!=EOF){
		sum=0;
		for(int i=0;i<5;i++) sum+=com[i]*(t[i]+t[9-i]-96);
		printf("%d\n",sum%10);
	}
}




----
*0063　Palindrome
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0063
普通にアセプト。
stdには、配列をリバースするメソッドがあるのでそれを使うともっと簡単になるらしい。

#include<stdio.h>
#include<string.h>
int main(){
	char text[101];
	bool ok;
	int len,ans=0;
	while(scanf("%s",text)!=EOF){
		ok=true;
		len=strlen(text);
		for(int i=0;i<len/2;i++){
			if(text[i]!=text[len-i-1]){
				ok=false;
				break;
			}
		}
		ans+=ok?1:0;
	}
	printf("%d\n",ans);
}





----
*0064　Secret Number
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0064
状態遷移マシンを作って簡単にアセプト。
一行ずつでなく一文字ずつ読み込めばもっとコードがシンプルになるようだ。
状態遷移マシンとしてみた場合一番簡単な部類に入ると思う。


#include<stdio.h>
#include<string.h>
int main(){
	char t[81];
	int len,mod,sum=0,ans=0;
	while(scanf("%s",t)!=EOF){
		len=strlen(t);
		mod=0;
		sum=0;
		for(int i=0;i<len;i++){
			if('0'<=t[i] && t[i]<='9'){
				sum*=10;
				sum+=t[i]-'0';
			}else{
				ans+=sum;
				sum=0;
			}
		}
		ans+=sum;
	}
	printf("%d\n",ans);
}





----
*0065　Trading
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0065
今月の取引と先月の取引を別々にカウント。
月データが複数になった場合はvector<map<int,int>>のようなコードが必要になる？
愚直に実装したがもう少し簡単なコードになるような気もする。

#include<stdio.h>
#include<map>


int main(){
	int no,day;
	char re[3];
	std::map<int,int> now,old;
	
	while(1){
		scanf("%d,%d",&no,&day);
		if(now.find(no)==now.end()){
			now[no]=1;
		}else{
			now[no]++;
		}
		scanf("%[\n]",re);
		if(re[1]!='\0') break;
	}
	while(scanf("%d,%d",&no,&day)!=EOF){
		if(old.find(no)==old.end()){
			old[no]=1;
		}else{
			old[no]++;
		}
	}
	std::map<int,int>::iterator it=old.begin();
	while(it!=old.end()){
		if(now.find((*it).first)!=now.end()){
			printf("%d %d\n",(*it).first,(*it).second+now[(*it).first]);
		}
		it++;
	}
}







----
*0067 The Number of Island
入力データの終了条件がよくわからないので何度も不正解を喰らってしまった問題。
問題自体は簡単だったし典型的な探索処理なのですが終了条件で手間取った。
なんか意地悪な問題。


#include<stdio.h>

int dxs[]={1,0,-1,0},dys[]={0,1,0,-1};
char map[12][13];

void saiki(int x,int y){
	int nx,ny;
	for(int i=0;i<4;i++){
		nx=x+dxs[i];
		ny=y+dys[i];
		if(nx<0 || 11<nx || ny<0 || 11<ny ||map[ny][nx]=='0') continue;
		map[ny][nx]='0';
		saiki(nx,ny);
	}
}

bool setMap(){
	for(int i=0;i<12;i++){
		if(scanf(" %12s",map[i])==EOF) return false;
    }
    int x,y,i,count=0;
    for(i=0;i<144;i++){
    	x=i%12;
    	y=i/12;
		if(map[y][x]=='1'){
			map[y][x]='0';
			count++;
			saiki(x,y);
		}
    }
    printf("%d\n",count);
    return true;
}
int main(){
	char s1;
	do{
		if(setMap()==false) break;
		if(scanf("%c",&s1)==EOF) break;
	}while(scanf("%c",&s1)!=EOF);
}







----
*0068　Enclose Pins with a Rubber Band
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0068
一番外側を構成する線分に注目した時、線分を伸ばして直線にした場合、残りの点全てが直線の片方に集まる。
という条件を満たすので後は共通集合で解。
　
　#include<stdio.h>

void setData(int n){
	double xs[101],ys[101],vx1,vy1,vx2,vy2;
	bool hits[101];
	for(int i=0;i<n;i++){
		scanf("%lf,%lf",&xs[i],&ys[i]);
		hits[i]=false;
	}
	if(n<5){
		printf("%d\n",n-3);
		return ;
	}
	
	double d;
	for(int i=0;i<n-1;i++){
		for(int j=i+1;j<n;j++){
			if(j==i || (hits[i]&&hits[j])) continue;
			vx1=xs[j]-xs[i];
			vy1=ys[j]-ys[i];
			bool first=true;
			bool ok=true;
			for(int k=0;k<n;k++){
				if(i==k || j==k) continue;
				vx2=xs[k]-xs[i];
				vy2=ys[k]-ys[i];
				if(first==true){
					d=vx1*vy2-vx2*vy1;
					first=false;
				}else{
					if(d*(vx1*vy2-vx2*vy1)<=0){
						ok=false;
						break;
					}
				}
			}
			if(ok==true){
				hits[i]=hits[j]=true;
			}
		}
	}
	int ans=0;
	for(int i=0;i<n;i++){
		ans+=hits[i]?1:0;
	}
	printf("%d\n",n-ans);
}

int main(){
	int n;
	scanf("%d",&n);
	while(n!=0){
		setData(n);
		scanf("%d",&n);
	}
}