UVa : 107


// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <sstream>
#include <set>
#include <math.h>
#define N 1000000
using namespace std;

double power (double x, double y)
{
    double result = 1;

    for ( double i = 1; i <= y; i++ ) {
        result *= x;
    }

    return result;
}

int powerOf2 (double h)
{
    int p = 0;
    while ( true ) {
        int res = power (2, p);
        if ( res > h )
            return p - 1;
        p++;
    }
}

int main ()
{
    long double H;
    long double x;

    while ( cin >> H >> x ) {
        if ( H == 0 && x == 0 )
            break;

        if ( H == 1 ) {
            printf ("0 1\n");
            continue;
        }
        if ( x == 1 ) {
            int t = powerOf2 (H);

            int k = 0;
            while ( H >= 1 ) {
                k += H;
                H /= 2;
            }
            printf ("%d %d\n", t , k);
            continue;
        }

        double n = 2.0;
        long double rightSide = log (H) / log (x);

        while ( fabs (log (n + 1) / log (n) - rightSide) > 1e-12  )
            n += 1;

        //cout << n << endl;

        int generation = 0;
        int dummy = (int)x;
        while ( dummy % (int)n != 1 ) {
            dummy /= (int)n;
            generation++;
        }

        int notWorking = 0;
        generation--;
        while ( generation > -1) {
            notWorking += (int)ceil (pow (n, generation));
            generation--;
        }

        double totalHeight = 0;
        int p = 0;
        double height = H;
        while ( power (n, p) <= x ) {
            totalHeight += (height * power (n, p));
            height /= (n + 1);
            p++;
        }

        printf ("%d %0.lf\n", notWorking, totalHeight);

    }

    return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s