UVa 107 - The Cat in the Hat (帽子里的猫) 解题报告

题目链接：http://uva.onlinejudge.org/external/1/107.html
题目翻译：http://luckycat.kshs.kh.edu.tw/homework/q107.htm

题目中有一段押韵的背景故事，”Why me?” 道出了这道题的意思，也就是大的猫不愿意干活儿，而是让它帽子里的小猫来干。有一个关键的值为 N，一只大的猫会让 N 只小猫来干活儿，而这 N 只小猫的身高便是大猫的 $\frac{1}{N+1}$。对于每一行输入数据，N 都是恒定的。根据题目的所求，不难看出这是一道数学向的题。

输出给出了第一只猫的身高（记为 H）和最后动手干活儿的猫的数量（记为 C）。由于最后一只猫的身高为 1，所以：$H \times \frac{1}{N+1} \times \frac{1}{N+1} \times \frac{1}{N+1} \times \cdots \times \frac{1}{N+1} = 1$，而 $1 \times N \times N \times N \times \cdots \times N = C$。

如果把任务被推的次数记为 k，那么在上面的第一个式子中，$\frac{1}{N+1}$ 乘了 k 遍；第二个式子中，N 也乘了 k 遍。整理一下可以得到：$(N+1)^k=H$ 和 $N^k=C$。

再来看看要输出的内容。第一项是没有干活儿的猫的数量（记为 S），也就等于所有猫的数量减去干活儿的猫的数量：

$\begin{aligned} S &= (1 + N + N^2 + N^3 + \cdots + N^{k-1} + N^k) - N^k \\ &= N^0 + N^1 + N^2 + N^3 + \cdots + N^{k-1} \\ \end{aligned}$

由等比数列求和公式得：

$\begin{aligned}S= \begin{cases} \frac{1-N^k}{1-N} = \frac{1-C}{1-N}, &N \neq 1 \cr 1 \times k = k, &N = 1 \end{cases} \end{aligned}$

第二项输出的是所有的猫的身高之和（记为 T），即：

$\begin{aligned} T &= 1 \cdot H + N \cdot H \cdot \frac{1}{N+1} + N^2 \cdot H \cdot (\frac{1}{N+1})^2 + \cdots + N^k \cdot H \cdot (\frac{1}{N+1})^k \\ &= H [(\frac{N}{N+1})^0 + (\frac{N}{N+1})^1 + (\frac{N}{N+1})^2 + \cdots + (\frac{N}{N+1})^k] \end{aligned}$

因为 $N \neq N + 1$，所以 $\frac{N}{N+1} \neq 1$，所以：

$\begin{aligned} T &= H \cdot \frac{1-(\frac{N}{N+1})^{k+1}}{1-\frac{N}{N+1}} \\ &= H \cdot \frac{1-(\frac{N}{N+1})^{k+1}}{\frac{1}{N+1}} \\ &= H \cdot (1-\frac{N^{k+1}}{(N+1)^{k+1}}) \cdot (N+1) \\ &= H \cdot (N+1-\frac{N^{k+1}}{(N+1)^k}) \\ &= HN + H - (N+1)^k \cdot \frac{N^{k+1}}{(N+1)^k} \\ &= HN + H - CN \\ &= (H-C)N + H \end{aligned}$

有了上面推出的结果，我们可以看到，只要能求出 N，就能够解决问题了。

怎么求 N 呢？当然是利用 $(N+1)^k=H$ 和 $N^k=C$ 啦。一开始我通过枚举 k 来求 N，结果交了 4 次都是 TLE。莫非被卡常数了？我决定试试直接枚举 N。先想办法把 k 干掉：

$\left\{ \begin{array}{l} (N+1)^k=H \Rightarrow k=\log_{N+1}H \\ N^k=C \Rightarrow k=\log_{N}C \end{array} \right. \Longrightarrow \log_{N+1}H = \log_{N}C$

由于 C 标准库中的对数函数是只有一个参数的，所以这里利用换底公式变换一下，好用底数为 e 的 log() 来求，顺便变成乘法：

$\log_{N+1}H = \log_{N}C \Longrightarrow \frac{\ln H}{\ln{(N+1)}} = \frac{\ln C}{\ln N} \Longrightarrow \ln H \cdot \ln N = \ln C \cdot \ln{(N+1)}$

只要找到一个 N，使得上面的等式成立就可以了。在写程序的时候，为了避开浮点误差，得改成等号的一边减去另一边，将得到的数的绝对值与一个接近零的数（如1E-9）的正数比较，如果前者小，则认为等式成立。当然，不要忘了 N=1 时输出的第一项应为 k（可用 $k=\log_{N+1}H = \log_2 H$ 来求）。

107_v1.cpp

#include <cstdio>
#include <cmath>
typedef long long num;
const double Min = 1e-9;
int main()
{
    num H, C;
    for (scanf("%lld%lld",&H,&C); (H|C)!=0; scanf("%lld%lld",&H,&C)) {
        num N;
        // 枚举 N
        for ( N = 0;
            fabs(log(H)*log(N)-log(C)*log(N+1)) > Min;
            N++
        ); // <-有分号哦
        printf("%lld %lld\n",
               N == 1 ? num(log2(H) + 0.5) : (1 - C) / (1 - N),
               (H - C) * N + H);
    }
    return 0;
}

上面代码的第 16 行加了 0.5 再进行强制类型转换算是一点点个人强迫症吧。

提交一下，通过了。但是！！！运行了 1.748s 啊！虽说时限是 3s，但我还是觉得这样太慢了。

看来题目的数据比较强。既然直接枚举 N 比较慢，那就二分吧。二分中比较麻烦的是确定初始范围以及缩小范围的条件。我选择的初始范围是 [0, C]。当 $\ln{H} \cdot \ln{N} > \ln{C} \cdot \ln(N+1) \Rightarrow \log_{N+1}H > \log_N C$ 时，应在中点左边找，反之则在中点右边找。（我是按照对数函数的图像来联想的，不确定这段推论是否正确。）

107_2.cpp

#include <cstdio>
#include <cmath>
typedef long long num;
const double Min = 1e-9;
int main()
{
    num H, C;
    for (scanf("%lld%lld",&H,&C); (H|C)!=0; scanf("%lld%lld",&H,&C)) {
        // 二分查找 N
        num N;
        num left = 0, right = C;
        while (true) {
            N = (left + right + 1) >> 1;	// 除以2时不要漏了+1
            double tmp = log(H) * log(N) - log(C) * log(N + 1);
            if (fabs(tmp) < Min)
                break;
            else if (tmp > 0)
                right = N;
            else
                left = N;
        }
        printf("%lld %lld\n",
               N == 1 ? num(log2(H) + 0.5) : (1 - C) / (1 - N),
               (H - C) * N + H);
    }
    return 0;
}

改成二分之后，运行时间降到了 0.099s。看来二分的效率还是不错的 :-)