作者mikek (rabbit)
看板ck47th320
標題Re: [問題] 又一個演算法的問題
時間Sat Mar 26 07:29:17 2005
※ 引述《changkh (留學生涯)》之銘言：
: ※ 引述《cabin (牧野流星)》之銘言：
: : 嗯...題目我解釋一下, 你看對不對
: : 假設有一個社區要挖井。為了讓每一口井平均分配，有以下的規則：
: : 如果只有一口井的話
: : 這口井要在(0, 1)之間。
: : 如果再加一口變成二口井的話
: : 這二口井中的第一口要在(0, 1/2)之間，第二口要在(1/2, 1)之間。
: : 如果二口井再加一口變成三口井的話
: : 這三口井中的第一口要在(0, 1/3)之間，第二口要在(1/3, 2/3)之間，
: : 第三口要在(2/3, 1)之間。
: : 如果總共有 i 口井的話
: : 這 i 口井要在(0, 1/i), (1/i, 2/i), ... ((i-1)/i, 1) 之間。
: : 而每一次挖井時舊的井的位置是不能改變的。
: : 我想題目應該是上面這樣才對
: 沒錯，就是這樣子。
: 所以覺得蠻難想的。
Sorry, I can't type Chinese right now.
I hope the solution below is correct. It's just for your information.
Assume there are n wells.
The position d(k) of the k-th well has to satisfy all of the following
conditions:
(k-1)/k < d(k) < k/k which is the valid interval if there are k wells
(k-1)/(k+1) < d(k) < k/(k+1) which is the valid interval if k+1 wells
...
(k-1)/n < d(k) < k/n which is the valid interval if there are n wells
Note that for all wells (i.e. k=1,2,3,...,n), the above inequalities must
hold.
Because (a) the left-hand part of the above inequalities are decreasing
, i.e. (k-1)/k < (k-1)/(k+1) < ... < (k-1)/n,
and (b) the right-hand part are also decreasing
, i.e. k/k < k/(k+1) < ... < k/n,
, we know the above conditions are all satisfied if and only if
(k-1)/k < k/n for all k in {1,2,...,n}.
It is straightforward that (k-1)/k < k/n is equivalent to
n < (k^2)/(k-1), for all k in {1,2,...,n}.
Note that (k^2)/(k-1) is increasing when k>2.
You can verify it by looking at its derivative.
So we only need to check k=1 (n<inf) and k=2 (n<4).
Therefore, the number of wells is at most 3 (n<4).
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 128.2.133.23