PKU演習問メモ(4/6 part2)

No. Title 分類・解法
2845 01000001 Straight forward
2602 Superlong sums Straight forward
3210 Coins Simple Math
3157 Java vs C++ String manipulation
1657 Distance on Chessboard Simple Math


これで352問。来週の月曜夜までに400問に乗せておきたい。
授業始まるけど、残ってるのはだんだん重い問題が多くなってきたし、PKUやってる時間あるかな……


以下問題概要、解法など

2845 01000001

問題概要

与えられた二進数同士の和を二進数で出力せよ。
結果の先頭に0を出力してはならない。

解法

80桁と64bitに入らないのでC++の人は配列かなにかで足し算する。
先頭の0を出力してはならないが0+0の場合は例外。


入力の先頭には0が来うるという罠。

ソースコード
int main()
{
	int CS; cin>>CS;
	rep(cs,CS)
	{
		char s1[81],s2[81];
		cin>>s1>>s2;
		
		int l1=strlen(s1),l2=strlen(s2),len;
		reverse(s1,s1+l1); reverse(s2,s2+l2);
			
		bool a[81]={0};
		bool c=0;
		for(len=0;len<max(l1,l2)||c;len++)
		{
			int t=c;
			if(len<l1)t+=s1[len]-'0';
			if(len<l2)t+=s2[len]-'0';
			
			a[len]=t&1;
			c=t>>1;
		}
		while(len>1&&a[len-1]==0)len--;
		
		char ans[82]; ans[len]='\0';
		rep(i,len)ans[len-i-1]=a[i]+'0';
		
		cout<<cs+1<<" "<<ans<<endl;
	}
	return 0;
}

2602 Superlong sums

問題概要

与えられた2つのn桁の数を足し算せよ。ただしn<=1000000である。

解法

筆算ぽくやればおk.繰り上がりに%演算子を使ったり、一桁ずつ出力したりするとTLEになりそうな気がする。(試してない)
二つの1-9までの数を足すので最大でも繰り上がりは1であることに留意。

ソースコード
int n,a,b;
int s[1000000]; char ans[10000001];

int main()
{
	scanf("%d",&n);
	rep(i,n)
	{
		scanf("%d%d",&a,&b);
		s[n-1-i]=a+b;
	}
	rep(i,n)if(s[i]>9)s[i+1]++,s[i]-=10;
	if(s[n])n++;
	
	ans[n]='\0';
	rep(i,n)ans[n-i-1]=s[i]+'0';
	
	printf("%s\n",ans);
	
	return 0;
}

3210 Coins

問題概要

n枚のコインがある。丁度k回だけコインをひっくり返すことで全てのコインの向きを揃えたい。
与えられたnに対して、コインの初期状態がどうであってもk回だけコインをひっくり返すことで全てのコインの向きが揃うような最小のkを出力せよ。そのようなkが存在しない場合は"No solution!"と出力せよ。
同じコインを二度以上ひっくり返しても良いものとする。

解法

嘘解法を書いてた気がしてきたので再考中。

3157 Java vs C++

問題概要

与えられた変数名を表す文字列をC形式(文字は全て小文字。複数単語からなる場合それらは_でつなぐ)ならばJava形式(複数単語の場合2番目以降の単語の頭文字を大文字にする)に、Java形式ならばC形式に変換せよ。

解法

コード参照。最初はC形式Java形式のどちらでもあると見て、矛盾が出たらその可能性を消していく。

ソースコード
int main()
{
	char buf[301],ans[301];
	gets(buf);
	int l=strlen(buf),len=0;
	
	bool cStyle=1,javaStyle=1;
	
	if(!('a'<=buf[0]&&buf[0]<='z'))javaStyle=cStyle=0;
	for(int i=1;i<l;i++)
	{
		if('A'<=buf[i]&&buf[i]<='Z')cStyle=0;
		else if(buf[i]=='_')
		{
			javaStyle=0;
			if(i+1>=l||buf[i+1]=='_')cStyle=0;
		}
		else if(!('a'<=buf[i]&&buf[i]<='z'))javaStyle=cStyle=0;
	}
	
	if(javaStyle==cStyle)
	{
		if(cStyle)puts(buf);
		else puts("Error!");
		return 0;
	}
	
	if(cStyle)
	{
		rep(i,l)if(buf[i]=='_')
			ans[len++]=buf[++i]+'A'-'a';
		else ans[len++]=buf[i];
	}
	else
	{
		rep(i,l)if('A'<=buf[i]&&buf[i]<='Z')
			ans[len++]='_',ans[len++]=buf[i]+'a'-'A';
		else ans[len++]=buf[i];
	}
	ans[len]='\0';
	puts(ans);
	
	return 0;
}

1657 Distance on Chessboard

問題概要

チェスボードの二点について、キング・クイーン・ルーク・ビショップで移動した時それぞれ最短の移動回数を求めよ。

解法

数学的に考察してもいいかもしれない。
ボードは8x8であり(十分狭い)、WA数を見るにキング・クイーンの移動回数がややこしそうなので幅優先探索で解いた。


↑ちょっと考えたら全然ややこしくなかった。頭悪いなあ。

ソースコード
#define ck(a) (0<=a&&a<8)

void push(queue<pi> &Q,int ny,int nx,int cy,int cx,int cost[8][8])
{
	if(!ck(ny)||!ck(nx))return;
	if(cost[ny][nx]<=cost[cy][cx]+1)return;
	
	cost[ny][nx]=cost[cy][cx]+1; Q.push(mp(ny,nx));
}

int main()
{
	int n; cin>>n;
	rep(N,n)
	{
		char s[3],t[3]; cin>>s>>t;
		int sy=s[0]-'a',sx=s[1]-'1',ty=t[0]-'a',tx=t[1]-'1';
		
		int k[8][8],q[8][8],r[8][8],b[8][8];
		rep(i,8)rep(j,8)k[i][j]=q[i][j]=r[i][j]=b[i][j]=inf;
		k[sy][sx]=q[sy][sx]=r[sy][sx]=b[sy][sx]=0;
		
		{
			queue<pi> Q; Q.push(mp(sy,sx));
			while(!Q.empty())
			{
				int cy=Q.front().first,cx=Q.front().second;
				Q.pop();
				if(cy==ty&&cx==tx)break;
				
				for(int ny=cy-1;ny<=cy+1;ny++)
				for(int nx=cx-1;nx<=cx+1;nx++)
				push(Q,ny,nx,cy,cx,k);
			}
		}
		{
			queue<pi> Q; Q.push(mp(sy,sx));
			while(!Q.empty())
			{
				int cy=Q.front().first,cx=Q.front().second;
				Q.pop();
				if(cy==ty&&cx==tx)break;
				rep(i,15)
				{
					push(Q,cy+i-7,cx,cy,cx,q);
					push(Q,cy,cx+i-7,cy,cx,q);
					push(Q,cy+i-7,cx+i-7,cy,cx,q);
					push(Q,cy+i-7,cx-i+7,cy,cx,q);
				}
			}
		}
		{
			queue<pi> Q; Q.push(mp(sy,sx));
			while(!Q.empty())
			{
				int cy=Q.front().first,cx=Q.front().second;
				Q.pop();
				if(cy==ty&&cx==tx)break;
				rep(i,15)
				{
					push(Q,cy+i-7,cx,cy,cx,r);
					push(Q,cy,cx+i-7,cy,cx,r);
				}
			}
		}
		{
			queue<pi> Q; Q.push(mp(sy,sx));
			while(!Q.empty())
			{
				int cy=Q.front().first,cx=Q.front().second;
				Q.pop();
				if(cy==ty&&cx==tx)break;
				rep(i,15)
				{
					push(Q,cy+i-7,cx+i-7,cy,cx,b);
					push(Q,cy+i-7,cx-i+7,cy,cx,b);
				}
			}
		}
		
		int ans[4]={k[ty][tx],q[ty][tx],r[ty][tx],b[ty][tx]};
		rep(i,4)
		{
			if(ans[i]==inf)cout<<"Inf";
			else cout<<ans[i];
			cout<<(i==3?"\n":" ");
		}
	}
	return 0;
}