-
Notifications
You must be signed in to change notification settings - Fork 0
/
uva107.cpp
46 lines (40 loc) · 1004 Bytes
/
uva107.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
int H, W;
while (cin >> H >> W)
{
if (!H && !W)
break;
double C = log(H) / log(W); //n¨Ï¥Îdouble!
//find N using binary search
int L = 1, R = 2147483645, N = (L + R) / 2;
double tar = log(N + 1) / log(N) - C; //n¨Ï¥Îdouble!
while (L != R)
{
if (tar > 1e-8)
L = N + 1;
else if (tar < -1e-8)
R = N;
else
break;
N = (L + R) / 2;
tar = log(N + 1) / log(N) - C;
}
//compute k
int k = round(log(H) / log(N + 1));// n¥Î¥|±Ë¤¤J!
int NWC = 0; //not working cat
int MC = 1; //more cat
int AH = H; //all height
for (int i = 0; i < k; ++i)
{
NWC += MC; //1+ ...+N^(k-1)
MC *= N;
H /= N + 1;
AH += H * MC;
}
cout << NWC << " " << AH << endl;
}
}