SRM462 Div1 Easy(250), Div2 Medium(500) AgeEncoding

AgeEncoding

基数が大きくなるほど表す年齢も大きくなるので、二分探索。例外処理が面倒。

蝋燭が0000ならば、-1。蝋燭が0001のとき年齢が1ならば-2、年齢が1以上ならば-1。蝋燭が0101のように最後の１本と他に１本以上立っていて、年齢が1ならば-1。

#include <string>

using namespace std;

class AgeEncoding
{
    double check( string candle, double base );
public:
    double getRadix( int age, string candlesLine );
};

double AgeEncoding::getRadix( int age, string candlesLine )
{
    //  例外
    int n = (int)candlesLine.size();

    int num = 0;    //  最後の1本を除く蝋燭の本数
    for ( int i=0; i<n-1; i++ )
        if ( candlesLine[i] == '1' )
            num++;

    if ( num == 0  &&  candlesLine[n-1] == '0' )
    {
        return -1;
    }
    else if ( num == 0  &&  candlesLine[n-1] == '1' )
    {
        if ( age == 1 )
            return -2;
        else
            return -1;
    }
    else if ( num > 0  &&  candlesLine[n-1] == '1' )
    {
        if ( age == 1 )
            return -1;
    }

    //  二分探索
    double l = 0;
    double r = age;

    for ( int i=0; i<100; i++ )
    {
        double m = ( l + r ) / 2;
        if ( check( candlesLine, m ) < age )
            l = m;
        else
            r = m;
    }

    return r;
}

//  基数baseでcandleが表す年齢を返す
double AgeEncoding::check( string candle, double base )
{
    double a = 0;
    double b = 1;

    for ( int i=(int)candle.size()-1; i>=0; i-- )
        a += b * (candle[i]-'0'),
        b *= base;

    return a;
}