UVa 107 - The Cat in the Hat

Contents

1. 1. Problem
2. 2. Solution
3. 3. Code

Problem

中文網址

Solution

H : 第一隻貓的高度
W : 在工作的貓
N : 每次變出的貓數
k : 變了幾次
最後工作的貓高度為 1 ，所以我們可以列出:
$$\begin{aligned} &1 = H \times {\frac1{(N+1)^k}}\\ &{(N+1)}^k = H \end{aligned}$$
先以 $(N+1)$ 為底取 log 再用換底公式後:
$$
k = \frac {log(H)}{log(N+1)}
$$

接著是貓咪總數量的部分，$1+N^1+N^2+\ldots+N^k = \frac {1-N^{k+1}}{1-N}$，用等比級數的公式去算。

我們知道最後工作的貓有幾隻 $W = N^k$ ，接著以 $N$ 為底取 log 再用換底公式後: $\frac{logW}{logN} = k$

藉由前面算出的，可以列出:

$$\begin{aligned} &\frac {logW}{logN} = \frac{logH}{log(N+1)} \\\\ &logW \times log(N+1) = logH \times logN \end{aligned}$$

此時 $W,H$ 都已知，所以去窮舉 $N$ ，再求出 $k$ 即可。而剛剛貓咪總數量減掉 $W$ 就等於沒在工作的了。

從第一隻開始，變出 $N$ 隻，每一隻高度為 $\frac{H}{N+1}$，以此類推下去。

總高度: $H+H(\frac{N}{N+1})+H(\frac{N}{N+1})^2+\ldots+H(\frac{N}{N+1})^k$

數學部分大概就這樣，要特別注意 N = 1 可能會使等比級數公式分母為零，還有 H = 1 時無法變出任何貓咪。
取 log 相除時要小心分母為零的情況。
小數點的精度問題。
一些轉型和 round() 要特別小心，麻煩的題目 TAT。

Code

UVa 107

#include<cstdio>
#include<cmath>
#define EPS 1e-6

int main()
{
	int H, W;
	while (scanf("%d%d", &H, &W) && H)
	{
		int N = 0, k;
		double logH = log((double)H), logW = log((double)W);
		if (H == 1)
		{
			puts("0 1");
			continue;
		}

		//log(W)*log(N+1) == log(H)*log(N)
		while (true)
		{
			N++;
			if (H % (N + 1))
				continue;

			double logn1 = log((double)N + 1);
			if (std::abs(logH*log((double)N) - logn1*logW) < EPS)
			{
				k = round(logH / logn1);
				break;
			}
		}

		double dN = N;
		int tot;
		if (N == 1)
			tot = k + 1;
		else
			tot = (1 - pow(dN, k + 1)) / (1 - dN);//1+N+N^2+N^3+...+N^k

		//H+H(N/(N+1))+H(N/(N+1))^2+...+H(N/(N+1))^k
		int tot_height = (int)round(H*(1 - pow(dN / (dN + 1), k + 1)) / (1 - (dN / (dN + 1))));
		printf("%d %d\n", tot - W, tot_height);
	}

	return 0;
}