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値，接下來就能求出答案了。