Codeforces 172 Div2

A Word Capitalization

http://www.codeforces.com/problemset/problem/281/A
ほんとにやるだけ。
これはtoupper(char)を知っているかどうかで割とはやくかけるかどうか決まる。
toupperはcctypeにはいっていて、簡単に小文字から大文字に変換する関数。。
charの配列を100しか取ってない人がいたのでおいしくいただきました。

#include <iostream>
#include <string>
#include <cctype>

int main(){
    string s;
    cin >> s;
    s[0] = toupper(s[0]);
    cout << s << endl;
    return 0;
}

B Nearest Fraction

http://www.codeforces.com/problemset/problem/281/B
まず、分母を1からnまでのループを回す。その中で二分探索して、近い二つについて調べていく。
このアルゴリズムではO(nlogn)で求めることができる。

#include <iostream>
#include <complex>

using namespace std;

typedef long long ll;

int main(){
    ll x,y,n;
    cin >> x >> y >> n;


    ll reta,retb;
    double mini = 1000000000;
    for(ll b=1;b<=n;b++){
        ll lower = 0;
        ll upper = b*x + 1000;
        for(int i=0;i<100;i++){
            ll a = (lower+upper)/2;
            if(x * b < a * y){
                upper = a;
            }else{
                lower = a;
            }
        }
        if(mini > fabs((double)(b*x - lower*y) / (double)(y*b))){
            mini = fabs((double)(b*x - lower*y) / (double)(y*b));
            reta = lower;
            retb = b;
        }
        if(mini > fabs((double)(b*x - upper*y) / (double)(y*b))){
            mini = fabs((double)(b*x - upper*y) / (double)(y*b));
            reta = upper;
            retb = b;
        }
    }
    cout << reta << "/" << retb << endl;
    return 0;
}