Codeforces #172 Div2. A. Word Capitalization, B. Nearest Fraction

CF172ではDiv1に参加し、Aだけ本番中に解けた。
さすがに１問だとレートは微減。
ではDiv2問題から復習。

http://codeforces.com/contest/281/problem/A
http://codeforces.com/contest/281/problem/B

A. Word Capitalization

単語を与えられるので先頭を大文字化せよ。
１文字目が小文字なら大文字化するだけ。
途中に空白文字があるわけでもないし、Div2とはいえ簡単すぎないか？

void solve() {
	int f,r,i,j,k,l,x,y,cur,tar;
	int L;
	char S[1003];
	
	GETs(S);
	if(islower(S[0])) S[0]+='A'-'a';
	_CO(S);
	
	return;
}

B. Nearest Fraction

分数x/yと整数Nが与えられる。N以下の数a,bを使い、x/yと最も近いa/bを求める。
bを1～Nでループで回して、一番近いaを答える。

x/y-a/b

=0とするとa=bx/yなので、その周辺のaについて最小値を更新するか比較する。

現在の暫定値がc/dとすると、|x/y-a/b|=|(bx-ay)/yb|<|(dx-cy)/yd|なら更新すればよい。

ll gcd(ll a, ll b) { return (b==0)?a:gcd(b,a%b);}

void solve() {
	int f,r,i,j,k,l,x,y,cur,tar;
	ll X,Y,N,A,B;
	double V;
	
	X=GETi();
	Y=GETi();
	N=GETi();
	
	V=X/(double)Y;
	ll NUM=0, DEN=1;
	double TV=0;
	
	for(B=1;B<=N;B++) {
		for(A=X*B/Y-3;A<=X*B/Y+3;A++) {
			ll N2=abs(X*B-A*Y);
			ll D2=B;
			ll TN=abs(X*DEN-NUM*Y);
			ll TD=DEN;
			
			if(N2*TD < D2*TN || ((N2*TD == D2*TN) && A<NUM)) {
				NUM=A;
				DEN=B;
			}
		}
		
	}
	
	X=gcd(NUM,DEN);
	_P("%lld/%lld\n",NUM/X,DEN/X);
	
	return;
}

まとめ

Aの簡単さに比べると、Bは若干厄介な問題。