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

「AOJ31～40」(2011/09/06 (火) 10:46:03) の最新版変更点

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

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

*0031　Weight
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0031&lang=jp
天秤で物の重さを測る問題です。
左に物、右に錘をおいて計り釣り合う重さの組み合わせを出力してください。

この問題は錘の重さが1、２，４，８、16、、、と2^nであることを利用して解きます。
重さを2進数に直すとそのまま使う錘の組み合わせになっているのでそのまま出力します。


 #include<stdio.h>
 int main(){
	int n,p,c;
	while(scanf("%d",&n)!=EOF){
		p=c=1;
		while(n!=0){
			if(n&1==1){
				printf("%s%d",c==1?"":" ",p);
				c=2;
			}
			n/=2;
			p*=2;
		}
		printf("\n");
	}
 }





----
*0032　Plastic Board
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0032&lang=jp
平行四辺形のボードが流れてきます。
斜辺と2辺の長さが与えられるのでそのデータより長方形か菱形かをチェックして、各々の数を数えるという問題です。

解法
平行四辺形の型以外来ないので、形のチェックはしなくて済むというのがポイントです。
なので3平方の定理で直角三角形か調べ、でないなら菱形か調べ、でないなら何もしないというコードを書きます。


 #include <stdio.h>
 int main(void){
	int a,b,c,d=0,r=0;
	while(scanf("%d,%d,%d",&a,&b,&c)!=EOF){
		a*a+b*b==c*c?r++:a==b?d++:a;
	}
	printf("%d\n%d\n",r,d);
 }




---- 
*0033 Ball
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0033
1～10までの番号が書かれたボールがランダムな順番でくるので右の筒に入れるか左に筒にいれるかします。
ボールは筒の上端にあるボールの数より小さい時のみ入れることができ、でないなら入れることができません。
ボールの並びが与えられるので全部のボールを筒にいれられるならＹＥＳでないならＮＯと出力してください。

解法
右の筒が左の筒より大きくなるように入れるという条件のもとボールを入れていくと上手くいきます。
右が7で左が4で、新しいボールが8なら。
右にいれると8,4.
左に入れると7,8で右に入れた方がこのあとより多くのボールが入る。
よって右に入るか調べて駄目なら左に入るか調べてだめならお手上げ。
という操作を繰り返すことで答えが出ます。
これをコード化するだけです。


 #include<stdio.h>
 int main(){
	int r,l,f,n,i,j,b;	
	scanf("%d",&n);
	for(i=0;i<n;i++){
		r=l=f=0;
		for(j=0;j<10;j++){
			scanf("%d",&b);
			(b>r?r:b>l?l:f)=b;
		}
		printf("%s\n",f==0?"YES":"NO");
	}
 }






----
*0034　Railway Lines
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0034
一直線の路線上の両端から電車が出発します。
電車の速度と駅間の長さが与えらるので電車がどの区間ですれ違うか出力するという問題です。

解法
すれ違うまでの時間tはt=路線の長さ/(v1+v2)で与えられ、ｔ秒目の位置は
l=ｔ*ｖ１で与えられます。
後はlがどの位置か調べるだけです。


 #include <stdio.h>
 int main(){
	double l[11],v1,v2,s;
	l[0]=0;
	while(scanf("%lf,",&l[1])!=EOF){
		for(int i=2;i<11;i++){
			scanf("%lf,",&l[i]);
			l[i]+=l[i-1];
		}
		scanf("%lf,%lf",&v1,&v2);
		s=v1*l[10]/(v1+v2);
		for(int i=1;i<11;i++){
			if(s<=l[i]){
				printf("%d\n",i);
				break;
			}
		}
	}
 }






----
*0035　Is it Convex?
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0035
四角形の座標が与えられるのでそれが凸多角形であるかないかを判別するコードをかけという問題です。

解法
多角形の線上を点が動いて一周する時凸多角形なら、頂点上での回転角の正負が常に正か負となるというのを利用して解けば簡単です。
少し変更すれば一般のＮ多角形の場合のヘコミも検出できるコードです。
多角形の極限として閉曲線になる時、閉曲線にくぼみがないなら曲率の正負が入れ替わらないという問題と結び付くので中々興味深い問題です。


 #include <stdio.h>
 int main(){
	double xs[4],ys[4],a,t;
	int p,np,ans;
	while(scanf("%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf",&xs[0],&ys[0],&xs[1],&ys[1],&xs[2],&ys[2],&xs[3],&ys[3])!=EOF){
		ans=a=t=0;
		for(int i=0;i<4;i++){
			p=(i+3)%4;
			np=(i+1)%4;
			t=(xs[i]-xs[p])*(ys[np]-ys[i])-(ys[i]-ys[p])*(xs[np]-xs[i]);
			if(a*t<0){
				ans=1;
				break;
			}else{
				a=t;
			}
		}
		if(ans==0){
			printf("YES\n");
		}else{
			printf("NO\n");
		}
	}
 }






----
*0036　A Figure on Surface
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0036
8*8マスの升目にブロックが置かれているのでそれがどの形か判別せよという問題。
私は非常にまずいコードを書いてしまいました。
このコードは反面教師として読んでください。

 #include <stdio.h>
 bool setMap();
 int xs[7][4]={{0,1,0,1},{0,0,0,0},{0,1,2,3},{0,0,-1,-1},{0,1,1,2},{0,0,1,1},{0,1, 0,-1}};
 int ys[7][4]={{0,0,1,1},{0,1,2,3},{0,0,0,0},{0,1, 1, 2},{0,0,1,1},{0,1,1,2},{0,0, 1, 1}};
 int map[12][12];

 int main(void)
 {
	while(setMap()){
	}
 }
 bool setMap(){
	char t;
	int sx,sy;
	bool hitCell=false;
	for(int i=0;i<8;i++){
		for(int j=0;j<8;j++){
			scanf(" %c",&t);
			map[i+1][j+1]=t-'0';
			if(t=='1' && hitCell==false){
				sx=j+1;
				sy=i+1;
				hitCell=true;
			}
		}
	}
	bool hit;
	for(int i=0;i<7;i++){
		hit=true;
		for(int k=0;k<4;k++){
			if(map[sy+ys[i][k]][sx+xs[i][k]]==0){
				hit=false;
				break;
			}
		}
		if(hit==true){
			printf("%c\n",i+'A');
			break;
		}
	}
	if(scanf("%c",&t)==EOF){
		return false;
	}
	if(scanf("%c",&t)==EOF){
		return false;
	}

	return true;
 }








----
*0037　Path on a Grid
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0037
壁に手をつきながら歩く人がいる。
壁の配置が与えられるので、その壁に沿って歩いた時の彼の移動方向を表示せよという問題。

解法
自力でパターン分けするのがめんどくさかったので
http://blog.livedoor.jp/kenyoi/archives/3995712.html
をそのまま参考にリンク先コードを縮めて作りました。
一見壁のどちら側にいるかが問題で向き*壁のどちらがわ＝8通りになるように思えます。
しかしこの問題見た目より簡単です。
図の上を北と見ると北に進んでいる時は必ず壁の西側に、南に進んでいる時は壁の東側に
東に進んでいる時は壁の北側に、西に進んでいる時は壁の南側にいるので実は4通り
のむきだけ考えればいいのです。


 #include <iostream>
 using namespace std;
 int map[11][7]={0},type=0,x=2,y=1;//type=0東向き、1南向き、２西向き、３北向き
 char a[4],b[5];
 void init(){
	for(int i=1; i<=9; i++){
		if(i%2){
			cin>>a;
			for(int n=0; n<4; n++)map[i][n+1] = char(a[n])-'0';
		}
		else {
			cin>>b;
			for(int m=0; m<5; m++)map[i][m+1] = char(b[m])-'0';
		}			
	}
 }
 int cxs[]={0,0,0,-1};
 int cys[]={-1,0,1,0};
 int dxs[]={ 0,1,0,-1};
 int dys[]={-2,0,2, 0};
 char muki[]="URDL";
 void Round(){
	int p;
	for(int i=type;i<4+type;i++){
		p=i%4;
		if(map[y+cys[p]][x+cxs[p]]==1){
			type=(p+3)%4;
			cout<<muki[p];
			x+=dxs[p];
			y+=dys[p];
			return;
		}
	}
	type=4;
 }
 void solve(){
	while(!(x==1&&y==1)){
		Round();
		if(type==4) break;
	}
 }
 int main(){
	init();
	cout<<'R';
	solve();
	cout<<"\n";	
    return 0;  
 }






*0038　Poker Hand
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0038
トランプのポーカーのカードデータ5枚が与えられます。
数値のみを考慮してどの役ができているか判別してくださいという問題。

解法
今回私は力づくでパタン分けして求めました。
特に特筆する内容もありません。
この問題役を求めるための簡単な2重ループ式があるそうですが知らなかったので自力で解きました。


 #include<stdio.h>
 #include<map>
 #include <algorithm>
 #include <string>
 int main(){
	int k[5],t;
	std::map<int,int> memo;
	while(scanf("%d,%d,%d,%d,%d",&k[0],&k[1],&k[2],&k[3],&k[4])!=EOF){
		memo.clear();
		for(int i=0;i<5;i++){
			t=k[i];
			if(memo.find(t)==memo.end()){
				memo[t]=1;
			}else{
				memo[t]++;
			}
		}
		std::sort(k,k+5);
		int m[5];
		std::string ya;
		std::map<int ,int>::iterator it;
		if(memo.size()==5){
			//ストレートまたは豚
			if((k[0]+1==k[1] && k[1]+1==k[2] && k[2]+1==k[3] && k[3]+1==k[4]) || (k[0]==1 && k[1]==10 && k[2]==11 && k[3]==12 && k[4]==13)){
				ya="straight";
			}else{
				ya="null";
			}
		}else if(memo.size()==2){
			//フルハウスまたはフォーカード
			it=memo.begin();
			m[0]=(*it).second;
			it++;
			m[1]=(*it).second;
			if((m[0]==2&&m[1]==3)||(m[0]==3&&m[1]==2)){
				ya="full house";
			}else{
				ya="four card";
			}
		}else if(memo.size()==3){
			//トゥーペアまたはスリーカード
			it=memo.begin();
			int max=0,l;
			while(it!=memo.end()){
				l=(*it).second;
				max=max>l?max:l;
				it++;
			}
			if(max==3){
				ya="three card";
			}else{
				ya="two pair";
			}
		}else if(memo.size()==4){
			//ワンペア
			ya="one pair";
		}
		printf("%s\n",ya.c_str());
	}
 }








----
*0039　Roman Figure
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0039
ローマ数字が与えられるので現在の10進数に直して出力してくださいという問題。
工夫も何もありません、状態遷移マシーンに食わせて愚直に求めています。
後ろから読んで、手前より大きければ二文字読んで引きます。
手前より同じか小さければ一文字読んで足します。
ローマ数字が一文字の場合に注意しましょう。


 #include <stdio.h>
 #include <string.h>
 #include <map>
 int main(void){
	int n;
	int sum;
	char in[102];
	std::map<char,int> nos;
	nos['I']=1;
	nos['V']=5;
	nos['X']=10;
	nos['L']=50;
	nos['C']=100;
	nos['D']=500;
	nos['M']=1000;
	while(scanf("%s",in)!=EOF){
		n=strlen(in);
		sum=0;
		if(n==1){
			printf("%d\n",nos[in[0]]);
			continue;
		}
		int i;
		for(i=n-1;i>=1;){
			if(nos[in[i-1]]>=nos[in[i]]){
				sum+=nos[in[i]];
				i--;
			}else{
				sum+=nos[in[i]]-nos[in[i-1]];
				i-=2;
			}
		}
		if(i==0){
			sum+=nos[in[i]];	
		}		
		
		printf("%d\n",sum);
	}
 }







----
*0040　Affine Cipher
アフィン暗号で暗号化された文字を複合化する問題です。
暗号前野文章にはthatかthisが含まれているのでそれを手がかりに複合します。

解法
愚直に全探索しても間に合うので全複合を試すだけです。
この時無意味な複合は排除してnum[]にある値だけを試します。



 #include<stdio.h>
 #include<string.h>
 char calc(char t,int a,int b){
	if(t>='a' && 'z'>=t){
		return ((t-'a')*a+b)%26+'a';
	}
	return t;
 }
 int main(){
	char cThat[5]="that",cThis[5]="this",text[257],ntext[257];
	int num[]={0,1,3,5,7,9,11,15,17,19,21,23,25},len,n;
	bool hit;
	scanf("%d",&n);
	for(int l=0;l<n;l++){
		scanf(" %[^\n]",text);
		len=strlen(text);
		hit=false;
		memset(ntext,'\0',257);
		for(int i=0;i<13;i++){
			for(int j=0;j<26;j++){
				for(int k=0;k<len;k++){
					ntext[k]=calc(text[k],num[i],j);
				}
				if(strstr(ntext,cThat)!=NULL || strstr(ntext,cThis)!=NULL){
					hit=true;
					break;
				}
			}
			if(hit==true) break;
		}
		printf("%s\n",ntext);
	}
 }

*0031　Weight
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0031&lang=jp
天秤で物の重さを測る問題です。
左に物、右に錘をおいて計り釣り合う重さの組み合わせを出力してください。

この問題は錘の重さが1、２，４，８、16、、、と2^nであることを利用して解きます。
重さを2進数に直すとそのまま使う錘の組み合わせになっているのでそのまま出力します。


 #include<stdio.h>
 int main(){
	int n,p,c;
	while(scanf("%d",&n)!=EOF){
		p=c=1;
		while(n!=0){
			if(n&1==1){
				printf("%s%d",c==1?"":" ",p);
				c=2;
			}
			n/=2;
			p*=2;
		}
		printf("\n");
	}
 }





----
*0032　Plastic Board
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0032&lang=jp
平行四辺形のボードが流れてきます。
斜辺と2辺の長さが与えられるのでそのデータより長方形か菱形かをチェックして、各々の数を数えるという問題です。

解法
平行四辺形の型以外来ないので、形のチェックはしなくて済むというのがポイントです。
なので3平方の定理で直角三角形か調べ、でないなら菱形か調べ、でないなら何もしないというコードを書きます。


 #include <stdio.h>
 int main(void){
	int a,b,c,d=0,r=0;
	while(scanf("%d,%d,%d",&a,&b,&c)!=EOF){
		a*a+b*b==c*c?r++:a==b?d++:a;
	}
	printf("%d\n%d\n",r,d);
 }




---- 
*0033 Ball
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0033
1～10までの番号が書かれたボールがランダムな順番でくるので右の筒に入れるか左に筒にいれるかします。
ボールは筒の上端にあるボールの数より小さい時のみ入れることができ、でないなら入れることができません。
ボールの並びが与えられるので全部のボールを筒にいれられるならＹＥＳでないならＮＯと出力してください。

解法
右の筒が左の筒より大きくなるように入れるという条件のもとボールを入れていくと上手くいきます。
右が7で左が4で、新しいボールが8なら。
右にいれると8,4.
左に入れると7,8で右に入れた方がこのあとより多くのボールが入る。
よって右に入るか調べて駄目なら左に入るか調べてだめならお手上げ。
という操作を繰り返すことで答えが出ます。
これをコード化するだけです。


 #include<stdio.h>
 int main(){
	int r,l,f,n,i,j,b;	
	scanf("%d",&n);
	for(i=0;i<n;i++){
		r=l=f=0;
		for(j=0;j<10;j++){
			scanf("%d",&b);
			(b>r?r:b>l?l:f)=b;
		}
		printf("%s\n",f==0?"YES":"NO");
	}
 }






----
*0034　Railway Lines
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0034
一直線の路線上の両端から電車が出発します。
電車の速度と駅間の長さが与えらるので電車がどの区間ですれ違うか出力するという問題です。

解法
すれ違うまでの時間tはt=路線の長さ/(v1+v2)で与えられ、ｔ秒目の位置は
l=ｔ*ｖ１で与えられます。
後はlがどの位置か調べるだけです。


 #include <stdio.h>
 int main(){
	double l[11],v1,v2,s;
	l[0]=0;
	while(scanf("%lf,",&l[1])!=EOF){
		for(int i=2;i<11;i++){
			scanf("%lf,",&l[i]);
			l[i]+=l[i-1];
		}
		scanf("%lf,%lf",&v1,&v2);
		s=v1*l[10]/(v1+v2);
		for(int i=1;i<11;i++){
			if(s<=l[i]){
				printf("%d\n",i);
				break;
			}
		}
	}
 }






----
*0035　Is it Convex?
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0035
四角形の座標が与えられるのでそれが凸多角形であるかないかを判別するコードをかけという問題です。

解法
多角形の線上を点が動いて一周する時凸多角形なら、頂点上での回転角の正負が常に正か負となるというのを利用して解けば簡単です。
少し変更すれば一般のＮ多角形の場合のヘコミも検出できるコードです。
多角形の極限として閉曲線になる時、閉曲線にくぼみがないなら曲率の正負が入れ替わらないという問題と結び付くので中々興味深い問題です。


 #include <stdio.h>
 int main(){
	double xs[4],ys[4],a,t;
	int p,np,ans;
	while(scanf("%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf",&xs[0],&ys[0],&xs[1],&ys[1],&xs[2],&ys[2],&xs[3],&ys[3])!=EOF){
		ans=a=t=0;
		for(int i=0;i<4;i++){
			p=(i+3)%4;
			np=(i+1)%4;
			t=(xs[i]-xs[p])*(ys[np]-ys[i])-(ys[i]-ys[p])*(xs[np]-xs[i]);
			if(a*t<0){
				ans=1;
				break;
			}else{
				a=t;
			}
		}
		if(ans==0){
			printf("YES\n");
		}else{
			printf("NO\n");
		}
	}
 }






----
*0036　A Figure on Surface
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0036
8*8マスの升目にブロックが置かれているのでそれがどの形か判別せよという問題。
私は非常にまずいコードを書いてしまいました。
このコードは反面教師として読んでください。

 #include <stdio.h>
 bool setMap();
 int xs[7][4]={{0,1,0,1},{0,0,0,0},{0,1,2,3},{0,0,-1,-1},{0,1,1,2},{0,0,1,1},{0,1, 0,-1}};
 int ys[7][4]={{0,0,1,1},{0,1,2,3},{0,0,0,0},{0,1, 1, 2},{0,0,1,1},{0,1,1,2},{0,0, 1, 1}};
 int map[12][12];
 int main(void)
 {
	while(setMap()){
	}
 }
 bool setMap(){
	char t;
	int sx,sy;
	bool hitCell=false;
	for(int i=0;i<8;i++){
		for(int j=0;j<8;j++){
			scanf(" %c",&t);
			map[i+1][j+1]=t-'0';
			if(t=='1' && hitCell==false){
				sx=j+1;
				sy=i+1;
				hitCell=true;
			}
		}
	}
	bool hit;
	for(int i=0;i<7;i++){
		hit=true;
		for(int k=0;k<4;k++){
			if(map[sy+ys[i][k]][sx+xs[i][k]]==0){
				hit=false;
				break;
			}
		}
		if(hit==true){
			printf("%c\n",i+'A');
			break;
		}
	}
	if(scanf("%c",&t)==EOF){
		return false;
	}
	if(scanf("%c",&t)==EOF){
		return false;
	}
	return true;
 }








----
*0037　Path on a Grid
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0037
壁に手をつきながら歩く人がいる。
壁の配置が与えられるので、その壁に沿って歩いた時の彼の移動方向を表示せよという問題。

解法
自力でパターン分けするのがめんどくさかったので
http://blog.livedoor.jp/kenyoi/archives/3995712.html
をそのまま参考にリンク先コードを縮めて作りました。
一見壁のどちら側にいるかが問題で向き*壁のどちらがわ＝8通りになるように思えます。
しかしこの問題見た目より簡単です。
図の上を北と見ると北に進んでいる時は必ず壁の西側に、南に進んでいる時は壁の東側に
東に進んでいる時は壁の北側に、西に進んでいる時は壁の南側にいるので実は4通り
のむきだけ考えればいいのです。


 #include <iostream>
 using namespace std;
 int map[11][7]={0},type=0,x=2,y=1;//type=0東向き、1南向き、２西向き、３北向き
 char a[4],b[5];
 void init(){
	for(int i=1; i<=9; i++){
		if(i%2){
			cin>>a;
			for(int n=0; n<4; n++)map[i][n+1] = char(a[n])-'0';
		}
		else {
			cin>>b;
			for(int m=0; m<5; m++)map[i][m+1] = char(b[m])-'0';
		}			
	}
 }
 int cxs[]={0,0,0,-1};
 int cys[]={-1,0,1,0};
 int dxs[]={ 0,1,0,-1};
 int dys[]={-2,0,2, 0};
 char muki[]="URDL";
 void Round(){
	int p;
	for(int i=type;i<4+type;i++){
		p=i%4;
		if(map[y+cys[p]][x+cxs[p]]==1){
			type=(p+3)%4;
			cout<<muki[p];
			x+=dxs[p];
			y+=dys[p];
			return;
		}
	}
	type=4;
 }
 void solve(){
	while(!(x==1&&y==1)){
		Round();
		if(type==4) break;
	}
 }
 int main(){
	init();
	cout<<'R';
	solve();
	cout<<"\n";	
    return 0;  
 }






*0038　Poker Hand
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0038
トランプのポーカーのカードデータ5枚が与えられます。
数値のみを考慮してどの役ができているか判別してくださいという問題。

解法
今回私は力づくでパタン分けして求めました。
特に特筆する内容もありません。
この問題役を求めるための簡単な2重ループ式があるそうですが知らなかったので自力で解きました。


 #include<stdio.h>
 #include<map>
 #include <algorithm>
 #include <string>
 int main(){
	int k[5],t;
	std::map<int,int> memo;
	while(scanf("%d,%d,%d,%d,%d",&k[0],&k[1],&k[2],&k[3],&k[4])!=EOF){
		memo.clear();
		for(int i=0;i<5;i++){
			t=k[i];
			if(memo.find(t)==memo.end()){
				memo[t]=1;
			}else{
				memo[t]++;
			}
		}
		std::sort(k,k+5);
		int m[5];
		std::string ya;
		std::map<int ,int>::iterator it;
		if(memo.size()==5){
			//ストレートまたは豚
			if((k[0]+1==k[1] && k[1]+1==k[2] && k[2]+1==k[3] && k[3]+1==k[4]) || (k[0]==1 && k[1]==10 && k[2]==11 && k[3]==12 && k[4]==13)){
				ya="straight";
			}else{
				ya="null";
			}
		}else if(memo.size()==2){
			//フルハウスまたはフォーカード
			it=memo.begin();
			m[0]=(*it).second;
			it++;
			m[1]=(*it).second;
			if((m[0]==2&&m[1]==3)||(m[0]==3&&m[1]==2)){
				ya="full house";
			}else{
				ya="four card";
			}
		}else if(memo.size()==3){
			//トゥーペアまたはスリーカード
			it=memo.begin();
			int max=0,l;
			while(it!=memo.end()){
				l=(*it).second;
				max=max>l?max:l;
				it++;
			}
			if(max==3){
				ya="three card";
			}else{
				ya="two pair";
			}
		}else if(memo.size()==4){
			//ワンペア
			ya="one pair";
		}
		printf("%s\n",ya.c_str());
	}
 }








----
*0039　Roman Figure
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0039
ローマ数字が与えられるので現在の10進数に直して出力してくださいという問題。
工夫も何もありません、状態遷移マシーンに食わせて愚直に求めています。
後ろから読んで、手前より大きければ二文字読んで引きます。
手前より同じか小さければ一文字読んで足します。
ローマ数字が一文字の場合に注意しましょう。


 #include <stdio.h>
 #include <string.h>
 #include <map>
 int main(void){
	int n;
	int sum;
	char in[102];
	std::map<char,int> nos;
	nos['I']=1;
	nos['V']=5;
	nos['X']=10;
	nos['L']=50;
	nos['C']=100;
	nos['D']=500;
	nos['M']=1000;
	while(scanf("%s",in)!=EOF){
		n=strlen(in);
		sum=0;
		if(n==1){
			printf("%d\n",nos[in[0]]);
			continue;
		}
		int i;
		for(i=n-1;i>=1;){
			if(nos[in[i-1]]>=nos[in[i]]){
				sum+=nos[in[i]];
				i--;
			}else{
				sum+=nos[in[i]]-nos[in[i-1]];
				i-=2;
			}
		}
		if(i==0){
			sum+=nos[in[i]];	
		}		
		
		printf("%d\n",sum);
	}
 }







----
*0040　Affine Cipher
アフィン暗号で暗号化された文字を複合化する問題です。
暗号前野文章にはthatかthisが含まれているのでそれを手がかりに複合します。

解法
愚直に全探索しても間に合うので全複合を試すだけです。
この時無意味な複合は排除してnum[]にある値だけを試します。



 #include<stdio.h>
 #include<string.h>
 char calc(char t,int a,int b){
	if(t>='a' && 'z'>=t){
		return ((t-'a')*a+b)%26+'a';
	}
	return t;
 }
 int main(){
	char cThat[5]="that",cThis[5]="this",text[257],ntext[257];
	int num[]={0,1,3,5,7,9,11,15,17,19,21,23,25},len,n;
	bool hit;
	scanf("%d",&n);
	for(int l=0;l<n;l++){
		scanf(" %[^\n]",text);
		len=strlen(text);
		hit=false;
		memset(ntext,'\0',257);
		for(int i=0;i<13;i++){
			for(int j=0;j<26;j++){
				for(int k=0;k<len;k++){
					ntext[k]=calc(text[k],num[i],j);
				}
				if(strstr(ntext,cThat)!=NULL || strstr(ntext,cThis)!=NULL){
					hit=true;
					break;
				}
			}
			if(hit==true) break;
		}
		printf("%s\n",ntext);
	}
 }