UVa 107 The Cat in the Hat

題目連結
題意：
　　一隻高度H的貓可以呼叫N個小貓幫手(N是我們要算的)，其每個小貓高度為 H*(1/(N+1))，每隻小貓可以在呼叫它的幫手N隻，身高為H*(1/(N+1))^2，一直下去，直到呼叫的小貓高度為1後，就不能再呼叫幫手了，因此這些高度為1的最矮的貓(worker cats)要把工作作完。
　　
　　現在題目給定兩個數：

• 第一個數為最高的貓(一開始只有一隻最高的貓)的高度H
• 第二個數為高度為1的貓(worker cats)的數量W，
• 求出沒有工作的貓的數量(全部-W)以及這些貓的身高總合。

想法：
　　首先最高的貓呼叫幫手後，產生N隻，高度為H*(1/(N+1))，我們假設呼叫k次直到身高為1後停止，可得出兩個等式：

• H * (1/(N+1))^k = 1
• N^k = W

因此解出N以及k後即可知道每次呼叫多少貓以及身高變為多少，將等式移項取log：

• k * log(N+1) = log(H)
• k * log(N) = log(W)

我們將第一式除以第二式消除k，然後使用binary search找出N値，接下來就能求出答案了。

	#include <cstdio>
	#include <cmath>
	using namespace std;
	typedef long long int llt;
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	int H,W;
	while (scanf("%d%d",&H,&W) != EOF){
	if (!H && !W) break;
	// klog(N+1) = logH
	// klogN = logW
	// 第一式除以第二式
	double C = log(H) / log(W);
	int L = 1, R = 2147483645, mid = (L + R)/2;
	while (L != R){
	if (log(mid+1) / log(mid) - C > 0.000000000001) L = mid+1;
	else if (log(mid+1) / log(mid) - C < -0.000000000001) R = mid;
	else break;
	mid = (L + R) / 2;
	}
	int N = mid;
	int k = round (log(H) / log(N+1));
	// 不要用logW/logN避免N=1的情況，使用round四捨五入
	// N和k已經有了，剩下只是統計數量和高度
	llt notWorking = 0;
	llt totalHeight = 0;
	W = 1;
	for (int i = 0; i < k; i++){
	notWorking += W;
	totalHeight += (H * W);
	W *= N;
	H /= (N+1);
	}
	printf("%lld %lld\n",notWorking, totalHeight+(H * W));
	}
	return 0;
	}

view raw [UVa] 107 The Cat in the Hat.cpp hosted with ❤ by GitHub