網頁

2014年2月9日 星期日

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

1 則留言: