07年5月PD想催绿, 求解答 - 未名空间MITBBS历史存档

07年5月PD想催绿, 求解答# EB23 - 劳工卡

g*l2012-05-11 07:05

1 楼

公司名字不方便说, 签了 NDA. 开始以为很容易, 就是简单算数计算. 后来面世官提示即使 D*F>C, 结
果可能是大于零的. 我然后望 DP 方向想, 但当场没想出什么好方法, 有大牛给指点一下, 谢先!
碰到这样的题,面世官也不给很多提示, 大家都这么应付的? 干瞪眼想还是说不会,让他换一道? 唉, 大概
还是自己不够 smart, 牛公司去不了.
A pile of nuts is in an oasis, across a desert from a town. The pile
contains 'N' kg of nuts, and the town is 'D' kilometers away from the
pile.
The goal of this problem is to write a program that will compute 'X',
the maximum amount of nuts that can be transported to the town.
The nuts are transported by a horse drawn cart that is initially next
to the pile of nuts. The cart can carry at most 'C' kilograms of nuts
at any one time. The horse uses the nuts that it is carrying as fuel.
It consumes 'F' kilograms of nuts per kilometer traveled regardless
of how much weight it is carrying in the cart. The horse can load and
unload the cart without using up any nuts.
Your program should have a function that takes as input 4 real numbers
D,N,F,C and returns one real number: 'X'

s*22012-05-11 07:05

2 楼

07年5月PD.
11年10月RD (TSC)
惨不忍睹. 到目前为止还没拿卡. 想找议员帮助吹绿. 请问找CONGRESSMAN 还是找
SENATOR (JOHN KERRY 还是 SCOTT BROWN)更好? 这样做有没有帮助? 多谢大侠!

g*s2012-05-11 07:05

3 楼

脑筋急转弯？马多跑几趟，一边走一边卸货做下一次的储备？

【在 g*l 的大作中提到】

: 公司名字不方便说, 签了 NDA. 开始以为很容易, 就是简单算数计算. 后来面世官提示即使 D*F>C, 结
: 果可能是大于零的. 我然后望 DP 方向想, 但当场没想出什么好方法, 有大牛给指点一下, 谢先!
: 碰到这样的题,面世官也不给很多提示, 大家都这么应付的? 干瞪眼想还是说不会,让他换一道? 唉, 大概
: 还是自己不够 smart, 牛公司去不了.
: A pile of nuts is in an oasis, across a desert from a town. The pile
: contains 'N' kg of nuts, and the town is 'D' kilometers away from the
: pile.
: The goal of this problem is to write a program that will compute 'X',
: the maximum amount of nuts that can be transported to the town.
: The nuts are transported by a horse drawn cart that is initially next

g*g2012-05-11 07:05

4 楼

全面铺开，你也不知道那个会开花。反正闲着也是闲着

k*s2012-05-11 07:05

5 楼

基本思路应该是DP,细节还没想好
M(x,y,i) is maximum kg of nuts to transport 'x' kg nuts to distance 'y' in '
i' middle stops;
(stop means to transport all nuts to this point then to next stop)
M(x,y,0) can be calculated easily. (of course, F*2*y < C)
M(x,y,k) = max(M(M(x,y1,k-1), y2, 0)), y1+y2 = y;

【在 g*l 的大作中提到】

: 公司名字不方便说, 签了 NDA. 开始以为很容易, 就是简单算数计算. 后来面世官提示即使 D*F>C, 结
: 果可能是大于零的. 我然后望 DP 方向想, 但当场没想出什么好方法, 有大牛给指点一下, 谢先!
: 碰到这样的题,面世官也不给很多提示, 大家都这么应付的? 干瞪眼想还是说不会,让他换一道? 唉, 大概
: 还是自己不够 smart, 牛公司去不了.
: A pile of nuts is in an oasis, across a desert from a town. The pile
: contains 'N' kg of nuts, and the town is 'D' kilometers away from the
: pile.
: The goal of this problem is to write a program that will compute 'X',
: the maximum amount of nuts that can be transported to the town.
: The nuts are transported by a horse drawn cart that is initially next

g*g2012-05-11 07:05

6 楼

John Kerry相当重量级

【在 s***2 的大作中提到】

: 07年5月PD.
: 11年10月RD (TSC)
: 惨不忍睹. 到目前为止还没拿卡. 想找议员帮助吹绿. 请问找CONGRESSMAN 还是找
: SENATOR (JOHN KERRY 还是 SCOTT BROWN)更好? 这样做有没有帮助? 多谢大侠!

g*l2012-05-11 07:05

7 楼

我也是怎么想的, 如果直接跑整趟, 那马有可能半道就没有能量了. 关键是怎么找中途
那些卸货点.
还是瞒难的题, 考算法还有情况考虑周到否. 我是上来就 assume 每次跑全程, 被指出
不对.

【在 g*********s 的大作中提到】

: 脑筋急转弯？马多跑几趟，一边走一边卸货做下一次的储备？

s*22012-05-11 07:05

8 楼

如果USCIS同时收到三个INQUIRY, 这样会不会不好?

【在 g**********g 的大作中提到】

: 全面铺开，你也不知道那个会开花。反正闲着也是闲着

g*l2012-05-11 07:05

9 楼

面试官没有说应该用啥方法. 能用文字讲讲你的思路和这个等式吗?
M(x,y,k) = max(M(M(x,y1,k-1), y2, 0)), y1+y2 = y;

'

【在 k***s 的大作中提到】

: 基本思路应该是DP,细节还没想好
: M(x,y,i) is maximum kg of nuts to transport 'x' kg nuts to distance 'y' in '
: i' middle stops;
: (stop means to transport all nuts to this point then to next stop)
: M(x,y,0) can be calculated easily. (of course, F*2*y < C)
: M(x,y,k) = max(M(M(x,y1,k-1), y2, 0)), y1+y2 = y;

a*k2012-05-11 07:05

10 楼

Too late.
1. The June VB clearly states EB2-IC was "U" since early April. You will get
an answer of visa not available for your category. I had a SR placed on
April 13, and that is the answer.
2. It will take a while for congressman/senator to send out the inquiry
before June 1.

【在 s***2 的大作中提到】

: 07年5月PD.
: 11年10月RD (TSC)
: 惨不忍睹. 到目前为止还没拿卡. 想找议员帮助吹绿. 请问找CONGRESSMAN 还是找
: SENATOR (JOHN KERRY 还是 SCOTT BROWN)更好? 这样做有没有帮助? 多谢大侠!

P*l2012-05-11 07:05

11 楼

binary search on the number of rounds.

g*g2012-05-11 07:05

12 楼

没啥不好的。你怕啥。

【在 s***2 的大作中提到】

: 如果USCIS同时收到三个INQUIRY, 这样会不会不好?

g*l2012-05-11 07:05

13 楼

Can you write code to explain it?
I think when you have more rounds, you waste more nuts for horse; when you
have
less rounds, the horse may lack of energy. If you have a "middle" round,
which
direction you search? More rounds or less rounds?

【在 P********l 的大作中提到】

: binary search on the number of rounds.

g*g2012-05-11 07:05

14 楼

真的？
这帮丫挺真操蛋。
但是理论讲，是6月起才U，现在还是到2007.8.
他还是有理由的。

get

【在 a***k 的大作中提到】

: Too late.
: 1. The June VB clearly states EB2-IC was "U" since early April. You will get
: an answer of visa not available for your category. I had a SR placed on
: April 13, and that is the answer.
: 2. It will take a while for congressman/senator to send out the inquiry
: before June 1.

h*n2012-05-11 07:05

15 楼

需要澄清一下，马卸货以后返回去载下一次时还要吃nuts吗？

示即使 D*F>C, 结
一下, 谢先!
他换一道? 唉, 大概

【在 g*l 的大作中提到】

: 公司名字不方便说, 签了 NDA. 开始以为很容易, 就是简单算数计算. 后来面世官提示即使 D*F>C, 结
: 果可能是大于零的. 我然后望 DP 方向想, 但当场没想出什么好方法, 有大牛给指点一下, 谢先!
: 碰到这样的题,面世官也不给很多提示, 大家都这么应付的? 干瞪眼想还是说不会,让他换一道? 唉, 大概
: 还是自己不够 smart, 牛公司去不了.
: A pile of nuts is in an oasis, across a desert from a town. The pile
: contains 'N' kg of nuts, and the town is 'D' kilometers away from the
: pile.
: The goal of this problem is to write a program that will compute 'X',
: the maximum amount of nuts that can be transported to the town.
: The nuts are transported by a horse drawn cart that is initially next

s*22012-05-11 07:05

16 楼

多谢!
但为啥还有5月报绿的?

get

【在 a***k 的大作中提到】

: Too late.
: 1. The June VB clearly states EB2-IC was "U" since early April. You will get
: an answer of visa not available for your category. I had a SR placed on
: April 13, and that is the answer.
: 2. It will take a while for congressman/senator to send out the inquiry
: before June 1.

g*l2012-05-11 07:05

17 楼

马只要移动, 就要消耗 nuts 做能量.

【在 h***n 的大作中提到】

: 需要澄清一下，马卸货以后返回去载下一次时还要吃nuts吗？
:
: 示即使 D*F>C, 结
: 一下, 谢先!
: 他换一道? 唉, 大概

a*k2012-05-11 07:05

18 楼

1. got RFEs before 3/23
2. couples with one approval before 3/23
3. Case pulled out before 3/23

【在 s***2 的大作中提到】

: 多谢!
: 但为啥还有5月报绿的?
:
: get

g*l2012-05-11 07:05

19 楼

大侠, 解释一下. 我没想明白.

【在 P********l 的大作中提到】

: binary search on the number of rounds.

L*d2012-05-11 07:05

20 楼

根楼主在一条船上，是07年4月的。TSE。。。叹息呀

c*n2012-05-11 07:05

21 楼

不就是那个绕圈加油的问题么？
答案都说了很多遍了

来面世官
提示即
下, 谢先!
他换一道?
唉,

【在 g*l 的大作中提到】

: 大侠, 解释一下. 我没想明白.

c*i2012-05-11 07:05

22 楼

07/07,rfe 3/24/12. 没有消息，想催绿

c*n2012-05-11 07:05

23 楼

oh, 不是加油。
因为不论多重，cost 都是一样的，那就肯定尽量多背，
如果剩的不够capacity, 就都背走，啦到max range, 然后recursively 解剩下的距离
你想难了

来面世官
提示即
下, 谢先!
他换一道?
唉,

【在 g*l 的大作中提到】

: 大侠, 解释一下. 我没想明白.

r*n2012-05-11 07:05

24 楼

You only have 2 weeks left in May to get your case processed. Will
congressman respond quickly enough to catch this?

【在 s***2 的大作中提到】

: 07年5月PD.
: 11年10月RD (TSC)
: 惨不忍睹. 到目前为止还没拿卡. 想找议员帮助吹绿. 请问找CONGRESSMAN 还是找
: SENATOR (JOHN KERRY 还是 SCOTT BROWN)更好? 这样做有没有帮助? 多谢大侠!

g*l2012-05-11 07:05

25 楼

给个 link ?

【在 c******n 的大作中提到】

: 不就是那个绕圈加油的问题么？
: 答案都说了很多遍了
:
: 来面世官
: 提示即
: 下, 谢先!
: 他换一道?
: 唉,

D*n2012-05-11 07:05

26 楼

07/06, 连rfe都没有

【在 c****i 的大作中提到】

: 07/07,rfe 3/24/12. 没有消息，想催绿

c*n2012-05-11 07:05

27 楼

max_nuts(N,D,...) {
if ( D > C / (2*F) ) {
remaining_D = D - ( C/(2*F) );
remaining_N = N - C;
return max_nuts( remaining_N, remaining_D ,C, F)
} else {
return N - D * F ;
}
}

来面世
官提示即
下, 谢
先!
他换一道?
唉,
pile
the
'X',

【在 g*l 的大作中提到】

: 给个 link ?

c*s2012-05-11 07:05

28 楼

早该找了，下个月就U了。

【在 s***2 的大作中提到】

: 07年5月PD.
: 11年10月RD (TSC)
: 惨不忍睹. 到目前为止还没拿卡. 想找议员帮助吹绿. 请问找CONGRESSMAN 还是找
: SENATOR (JOHN KERRY 还是 SCOTT BROWN)更好? 这样做有没有帮助? 多谢大侠!

g*l2012-05-11 07:05

29 楼

尽量多背没错, 但走多远? 啥是 max range. 我怎么觉得是你想简单了. 如果你解释不
清, 上 code 我
应该明白.

【在 c******n 的大作中提到】

: oh, 不是加油。
: 因为不论多重，cost 都是一样的，那就肯定尽量多背，
: 如果剩的不够capacity, 就都背走，啦到max range, 然后recursively 解剩下的距离
: 你想难了
:
: 来面世官
: 提示即
: 下, 谢先!
: 他换一道?
: 唉,

s*22012-05-11 07:05

30 楼

收到议员回信, 说45天后没消息就再联系他们.
移民局简短回复,说我的CASE还在PENDING. Fingerprints and FBI namechecks are
current. 但他们还在处理09/09/11的CASE.
是不是彻底没戏啦? 6月份开始就要UNAVAILABLE了. 难到要等到十月才能绿?

【在 r********n 的大作中提到】

: You only have 2 weeks left in May to get your case processed. Will
: congressman respond quickly enough to catch this?

g*l2012-05-11 07:05

31 楼

刚发, 才发现你已经上 code 了. 让我看看.

【在 g*l 的大作中提到】

: 尽量多背没错, 但走多远? 啥是 max range. 我怎么觉得是你想简单了. 如果你解释不
: 清, 上 code 我
: 应该明白.

k*e2012-05-11 07:05

32 楼

这个显然不对啊。
走过C/F距离之后一个来回
起点的一个nuts都没有搬出去半步
白白吃掉了路上的C个nuts
做无用功。

【在 c******n 的大作中提到】

: max_nuts(N,D,...) {
: if ( D > C / (2*F) ) {
: remaining_D = D - ( C/(2*F) );
: remaining_N = N - C;
: return max_nuts( remaining_N, remaining_D ,C, F)
: } else {
: return N - D * F ;
: }
: }
:

g*l2012-05-11 07:05

33 楼

好象不太对哦! 你这个是假设一次都能背动. 但是马每次也许只能背很小 fraction of
N

【在 c******n 的大作中提到】

: max_nuts(N,D,...) {
: if ( D > C / (2*F) ) {
: remaining_D = D - ( C/(2*F) );
: remaining_N = N - C;
: return max_nuts( remaining_N, remaining_D ,C, F)
: } else {
: return N - D * F ;
: }
: }
:

g*l2012-05-11 07:05

34 楼

另外, 你没有考虑到最后一趟并不需要往返跑. 看来我没做出来, 并不冤枉. 大牛也有
疏漏的地方.
冒犯了, 别拍我, 赶紧跑... :-)

【在 c******n 的大作中提到】

: max_nuts(N,D,...) {
: if ( D > C / (2*F) ) {
: remaining_D = D - ( C/(2*F) );
: remaining_N = N - C;
: return max_nuts( remaining_N, remaining_D ,C, F)
: } else {
: return N - D * F ;
: }
: }
:

h*e2012-05-11 07:05

35 楼

一公里一公里的搬，每公里的最后一车要注意算？

g*l2012-05-11 07:05

36 楼

那为啥不是半公里半公里般? 我决的是要慢慢般, 只是具体多慢没想好.

【在 h********e 的大作中提到】

: 一公里一公里的搬，每公里的最后一车要注意算？

D*72012-05-11 07:05

37 楼

我有一点想法了，大家来看看到底对不对。
1) 这是一个递归的问题，而递归的结束条件就是N<=C，这时候一趟运了就是了，如果
剩下的路程长于C/F，那就是无解。
2) 在递归结束之前，我们都要进行往返运输，而且每次都要把尽可能多的Nuts运到尽
可能远的位置。
3) 马车的单程最长距离是：C/F，我们可以把这个距离看做1，而我们每次运输的距离
为X（容易可得：X<0.5）。
4) 每次运输的往返次数Y为：
Y = N/C + (N%C > C*2X) ? 1 : 0
这个等式中的后半部分是比较剩下的Nuts和途中的消耗，如果还不够消耗的就干脆不要
了。其中Y-1次是双程，最后1次是单程。
由此，每次运输后的Nuts数量为：
N = ((Y-1)*(1-2X) + (1-X)) * C = (Y - (2Y+1)*X) * C
5) 从效率的角度考虑，我们既不应该抛弃Nuts，也不应该不满载，也就是说我们应该
保证每次运输后的Nuts数量都是C的整数倍，或者说每次运输都只消耗一份数量为C的
Nuts（第一次运输为N%C），即
X=1/(2Y+1) or X=((N%C)/C)/(2Y+1)

i*e2012-05-11 07:05

38 楼

这题有很强的递归性。
我的思路是bottom up，
先解最基本（base case）的答案，
然后慢慢从base case扩展上去。
observations:
1) if N <= C, then max = N - D*F. When the nuts is less than the cart's
capacity, you of course put all of them in the cart and transport to the
destination in 1 shot. This proves our base case.
2) if N > C, then max(N, D) =
max( N - C, N - (N - C)/k ), if N % C == 0
max( N - (N % C), N - (N % C)/k ), otherwise.
where k = ( 2*( floor(N/C) - 1 ) + 1 ) * F
上面的公式看起来很复杂，其实思路搞懂了就不难推出公式。
Assume you have N kg of nuts, and it is greater than your capacity, C.
How should you fetch in a way that consumes the less nuts?
If you use some easy example, you would observe that no matter how much you subdivide, each KM of journey the horse consumes the same amount of energy. The key is making an observation that once it reaches a point, the horse would consume enough nuts such that the rest of nuts takes ONE less round to fetch. This is the key. Once you reach this point, you have obtain a maximum efficiency. Now, you have N'kms left, which is either N-C or N-(N%C). Then, solve for the N'kms left using the recursive property, and since our base case is solved, this solves the problem.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

c*n2012-05-11 07:05

39 楼

有意思，这是个数学题
我开始的方法没有特别错，我想的时候老把C 想成完全给马吃，不消耗的nuts,
其实如果是那样，基本就对了，递归的时候该成remaining_N = N - C -C' where C' 是
"货舱“ 的容积
现在的问题就是怎么把C 分成货舱和自己吃的nuts,
最简单的，假设N 很大很大，足够（用某种方法) 把大部分都拉到地儿，
而且C 相对 D/F 很小，所以马必须一次次拉
假设一次拉dX 距离，那起始 C 的豆子，就变成 C - dX * F * 2
这样马来来回回把所有豆子挪窝儿dX , 就变成了h = (1-kdX)=(C - dX * F * 2 ) /
C
这么多，
总共也是这样乘系数。
那如果走到头，一共是倒腾 ( D/ dX ) 次，最后的ratio 就是 h ^ ( D/ dX )
用基本微积分式子，这个是e^(-Dk)
为什么要一点点挪呢？过去的effective weight / cost 都是一样的，回来的
effective weight 是drop off 的weight, 走的月长， drop off weight 剩余的就
越少

cart's
the

【在 i**********e 的大作中提到】

: 这题有很强的递归性。
: 我的思路是bottom up，
: 先解最基本（base case）的答案，
: 然后慢慢从base case扩展上去。
: observations:
: 1) if N <= C, then max = N - D*F. When the nuts is less than the cart's
: capacity, you of course put all of them in the cart and transport to the
: destination in 1 shot. This proves our base case.
: 2) if N > C, then max(N, D) =
: max( N - C, N - (N - C)/k ), if N % C == 0

c*n2012-05-11 07:05

40 楼

err .... 不对了。。
挪的距离也得算啊。

' 是
/

【在 c******n 的大作中提到】

: 有意思，这是个数学题
: 我开始的方法没有特别错，我想的时候老把C 想成完全给马吃，不消耗的nuts,
: 其实如果是那样，基本就对了，递归的时候该成remaining_N = N - C -C' where C' 是
: "货舱“ 的容积
: 现在的问题就是怎么把C 分成货舱和自己吃的nuts,
: 最简单的，假设N 很大很大，足够（用某种方法) 把大部分都拉到地儿，
: 而且C 相对 D/F 很小，所以马必须一次次拉
: 假设一次拉dX 距离，那起始 C 的豆子，就变成 C - dX * F * 2
: 这样马来来回回把所有豆子挪窝儿dX , 就变成了h = (1-kdX)=(C - dX * F * 2 ) /
: C

c*n2012-05-11 07:05

41 楼

啊，好像对的，
e^(-DK) > (2)^(-2Dk) = 每次吃一半的解法

【在 c******n 的大作中提到】

: err .... 不对了。。
: 挪的距离也得算啊。
:
: ' 是
: /

l*n2012-05-11 07:05

42 楼

//solution for Java version
public int nutsLeftRecur(int D, int N, int F, int C){
//T: the times to transport N for horse with C
int T = N / C;
int remain = N % C;
if (remain != 0){
//one more time add to T to transport for horse
T++;
}
//two cases to exit this recursion:
// Case 1:
// destination arrived, return nuts left.
if (D == 0)
return N;
// Case 2:
// if nuts N (N<= C) left, so just need one time transportation,
// return the nuts left after transport distance D
// (possible the nuts left is negative)
if (T ==1)
return N - F * D;
// the next processing based on:
// 1. D != 0 and
// 2. need two or more times to transport the nuts.
// at start point, suppose it has exactly T*C nuts (or N),
// and after move to d miles away, suppose it has exactly (T-1)*C nuts
// For horse, (2 * T - 1) times transportation for the distance d will consume C (or c)
int c = N - (T - 1) * C;
int f = F * (2 * T - 1);
int d = c / f;
int r = c % f;
if (r != 0)
d++;
//consider the case:
// if d>= D and destination arrived first, so just moved D instead of d
if (d>= D){
d = D;
}
//N and D left after horse transport d
D = D - d;
N = N - d * f;
System.out.println();
System.out.println("\tN=" + N + "\tD=" + D + "\td=" + d + "\tT=" + T );
return nutsLeftRecur( D, N, F, C);
}

来面世官提示即

【在 g*l 的大作中提到】

: 那为啥不是半公里半公里般? 我决的是要慢慢般, 只是具体多慢没想好.

g*l2012-05-11 07:05

43 楼

多谢楼上几位大侠指点! 属我愚钝, 觉得说得都在理, 但不很确信拿个是完全正确的.
来个 poll 吧, 大伙觉得谁的方法对呢?

【在 i**********e 的大作中提到】

: 这题有很强的递归性。
: 我的思路是bottom up，
: 先解最基本（base case）的答案，
: 然后慢慢从base case扩展上去。
: observations:
: 1) if N <= C, then max = N - D*F. When the nuts is less than the cart's
: capacity, you of course put all of them in the cart and transport to the
: destination in 1 shot. This proves our base case.
: 2) if N > C, then max(N, D) =
: max( N - C, N - (N - C)/k ), if N % C == 0

i*e2012-05-11 07:05

44 楼

其实我之前的帖子有一些错误.
例如，我的假设是integer是错的.
liveInBoston 也犯了这个错误，题目说 N, D, C, F is real numbers.
另外，我也漏了一些细节部分.
例如，忘了处理当中间没油了的情况.
但是基本思路还是对的.
我已经把我解这道题的详细思路记录在这里:
http://www.ihas1337code.com/2011/01/nuts-in-oasis-interview-que
Below is my output for the sample test cases:
N: 1 D: 1 C: 1 F: 1 maxNuts: 0
N: 1 D: 2 C: 1 F: 1 maxNuts: 0
N: 1 D: 0.25 C: 1 F: 1 maxNuts: 0.75
N: 2 D: 1 C: 1 F: 1 maxNuts: 0.333333
N: 100 D: 10 C: 50 F: 1 maxNuts: 70
N: 100 D: 20 C: 50 F: 1 maxNuts: 46.6667
N: 100 D: 30 C: 50 F: 1 maxNuts: 36.6667
N: 150 D: 30 C: 50 F: 1 maxNuts: 46.6667
N: 175 D: 30 C: 50 F: 1 maxNuts: 50.7143
N: 555 D: 105 C: 50 F: 1 maxNuts: 4.26112
N: 553.4 D: 96.3 C: 34.5 F: 0.4 maxNuts: 60.6688
This is the code with lots of comments, you should be able to follow through
easily :)
#include
#include
using namespace std;
double getMaxNuts(double N, double D, double C, double F) {
// base case:
// We have the capacity to carry all nuts,
// so fetch all the nuts in one trip
if (N <= C) {
double nutsAtDestination = N - D*F;
return (nutsAtDestination >= 0.0) ?
nutsAtDestination :
0.0; // out of fuel!
}
// # trips you would travel back and forth
int numTrips = 2*(ceil(N/C) - 1) + 1;
// how many nuts you consume per km
double costPerKm = numTrips * F;
// remaining weight of nuts after consumption
double remainingNuts = C*(ceil(N/C) - 1.0);
// this is the distance you are able to travel before you
// reach ONE LESS round trip fetching nuts
// derived form eq: N - costPerKm * traveled = remainingNuts
double traveled = (N - remainingNuts) / costPerKm;
// we are able to travel greater (or equal) than the remaining distance
// so fetch the nuts right to the destination
if (traveled >= D)
return N - D*costPerKm;
// calculate recursively as we travel ONE less round trip now.
return getMaxNuts(remainingNuts, D-traveled, C, F);
}
void test(double N, double D, double C, double F) {
cout << "N: " << setw(5) << N << " D: " << setw(5) << D << " C: " <
< setw(5) << C << " F: " << setw(5) << F << " maxNuts: ";
cout << getMaxNuts(N, D, C, F) << endl;
}
int main() {
double N, D, C, F;
N = 1, D = 1, C = 1, F = 1;
test(N, D, C, F);
N = 1, D = 2, C = 1, F = 1;
test(N, D, C, F);
N = 1, D = 0.25, C = 1, F = 1;
test(N, D, C, F);
N = 2, D = 1, C = 1, F = 1;
test(N, D, C, F);
N = 100, D = 10, C = 50, F = 1;
test(N, D, C, F);
N = 100, D = 20, C = 50, F = 1;
test(N, D, C, F);
N = 100, D = 30, C = 50, F = 1;
test(N, D, C, F);
N = 150, D = 30, C = 50, F = 1;
test(N, D, C, F);
N = 175, D = 30, C = 50, F = 1;
test(N, D, C, F);
N = 555, D = 105, C = 50, F = 1;
test(N, D, C, F);
N = 553.4, D = 96.3, C = 34.5, F = 0.4;
test(N, D, C, F);
return 0;
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

g*l2012-05-11 07:05

45 楼

感觉有错误. 你算 costPerKm 用到了 numTrips, 这是包括了最后一趟的, 也就是说全
运走了, 没
有 remingingNuts. 但你在计算 traveled 是假设有 remainingNuts, 可是同时用的
costPerKm是以没有 remainingNuts 来算的. Circular logic?
// # trips you would travel back and forth
int numTrips = 2*(ceil(N/C) - 1) + 1;
// how many nuts you consume per km
double costPerKm = numTrips * F;
// remaining weight of nuts after consumption
double remainingNuts = C*(ceil(N/C) - 1.0);
// this is the distance you are able to travel before you
// reach ONE LESS round trip fetching nuts
// derived form eq: N - costPerKm * traveled = remainingNuts
double traveled = (N - remainingNuts) / costPerKm;

from.html

【在 i**********e 的大作中提到】

: 其实我之前的帖子有一些错误.
: 例如，我的假设是integer是错的.
: liveInBoston 也犯了这个错误，题目说 N, D, C, F is real numbers.
: 另外，我也漏了一些细节部分.
: 例如，忘了处理当中间没油了的情况.
: 但是基本思路还是对的.
: 我已经把我解这道题的详细思路记录在这里:
: http://www.ihas1337code.com/2011/01/nuts-in-oasis-interview-que
: Below is my output for the sample test cases:
: N: 1 D: 1 C: 1 F: 1 maxNuts: 0

g*l2012-05-11 07:05

46 楼

虽然我认为还有错, 但大侠的总体分析还是很sharp的, 对 recursion 看的很透. 迄今
为止我觉得是最
close 的解了. 当然我不知道正解是啥, 呵呵.

from.html

【在 i**********e 的大作中提到】

: 其实我之前的帖子有一些错误.
: 例如，我的假设是integer是错的.
: liveInBoston 也犯了这个错误，题目说 N, D, C, F is real numbers.
: 另外，我也漏了一些细节部分.
: 例如，忘了处理当中间没油了的情况.
: 但是基本思路还是对的.
: 我已经把我解这道题的详细思路记录在这里:
: http://www.ihas1337code.com/2011/01/nuts-in-oasis-interview-que
: Below is my output for the sample test cases:
: N: 1 D: 1 C: 1 F: 1 maxNuts: 0

i*e2012-05-11 07:05

47 楼

感觉有错误. 你算 costPerKm 用到了 numTrips, 这是包括了最后一趟的, 也就是说全
运走了, 没有 remingingNuts.
>> 当 remainingNuts 为零的时候，随即被再次调入 getMaxNuts 函数的时候，不要忘
了有 if (N <= C) 这个 base case 的检查。这时候 N 就是 remaining nuts，也就是
0. 这时候 N <= C 的条件必定满足，然后就检查是不是还有剩下的距离。如果还有的
话，那就返回0，因为马以经走不下去了。
我了解你对递归的不确定而感到困惑。递归的解法就是先从简单的例子开始解，然后由
此获取这个问题 (problem) 中的问题 (subproblems)。递归的难点就在于你怎么从一
个 problem 和另一个 subproblem 里寻找那个关系。只要能证明从这个关系把一个问
题引申到下一个 subproblem，问题就能迎刃而解，不用想的太复杂。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

i*e2012-05-11 07:05

48 楼

这个等式中的后半部分是比较剩下的Nuts和途中的消耗，如果还不够消耗的就干脆不要了。
>> 你上面这个情况，我也有考虑过。虽然感觉不值得拿，但是每一步你必须用贪心策略，把所有nuts都搬走。举个 counter example吧。
假设 N = 101kg，C = 50kg，F = 1，D = 10 km。
这时候，如果我问你，你现在一次最多能载 50kg，你选择跑多少次来回？相信很多人都会答两次，因为第三次还剩下 1kg，很不值对吧？
通常，人都会考虑载三轮（跑一个来回+最后一次跑一趟就够了)，把剩下的 1kg 索性不要好了，然后尽可能载得越远越好。
那如果这样呢？我决定载五轮（跑两个来回+最后一次跑一趟就够了），把所有都运送去下一站点。然后，我下一站点定位为从起始点的 0.2 km。跑了0.2 km，耗了总共 0.2 * 5 * 1 = 1 kg 的 nuts。这时候，我已经成功把 100 kg 的 nuts 成功运输到这一站点，而且还跑了比之前方法的多 0.2 km。再说，下一轮我就只需要载三轮而已，还省了一个来回！
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 D*****7 的大作中提到】

: 我有一点想法了，大家来看看到底对不对。
: 1) 这是一个递归的问题，而递归的结束条件就是N<=C，这时候一趟运了就是了，如果
: 剩下的路程长于C/F，那就是无解。
: 2) 在递归结束之前，我们都要进行往返运输，而且每次都要把尽可能多的Nuts运到尽
: 可能远的位置。
: 3) 马车的单程最长距离是：C/F，我们可以把这个距离看做1，而我们每次运输的距离
: 为X（容易可得：X<0.5）。
: 4) 每次运输的往返次数Y为：
: Y = N/C + (N%C > C*2X) ? 1 : 0
: 这个等式中的后半部分是比较剩下的Nuts和途中的消耗，如果还不够消耗的就干脆不要

g*l2012-05-11 07:05

49 楼

The code (in Java version) didn't work for my test case
D=1000, N=20000000, F=1, C=2000
I got "java.lang.StackOverflowError"

from.html

【在 i**********e 的大作中提到】

: 其实我之前的帖子有一些错误.
: 例如，我的假设是integer是错的.
: liveInBoston 也犯了这个错误，题目说 N, D, C, F is real numbers.
: 另外，我也漏了一些细节部分.
: 例如，忘了处理当中间没油了的情况.
: 但是基本思路还是对的.
: 我已经把我解这道题的详细思路记录在这里:
: http://www.ihas1337code.com/2011/01/nuts-in-oasis-interview-que
: Below is my output for the sample test cases:
: N: 1 D: 1 C: 1 F: 1 maxNuts: 0

k*s2012-05-11 07:05

50 楼

看了网站上的解答，应该是在第一步的结束的时候，剩下nut肯定是C的整倍数了。
而且每经过一个middle point的时候，下一步的round trip会少一个，直观上看
这个应该是最优的；步知道理论上能不能证明这一点。

要了。
人都会答两次，因为第三次还剩下 1kg，很不值对吧？
性不要好了，然后尽可能载得越远越好。
送去下一站点。然后，我下一站点定位为从起始点的 0.2 km。跑了0.2 km，耗了总共
0.2 * 5 * 1 = 1 kg 的 nuts。这时候，我已经成功把 100 kg 的 nuts 成功运输到这
一站点，而且还跑了比之

【在 i**********e 的大作中提到】

: 这个等式中的后半部分是比较剩下的Nuts和途中的消耗，如果还不够消耗的就干脆不要了。
: >> 你上面这个情况，我也有考虑过。虽然感觉不值得拿，但是每一步你必须用贪心策略，把所有nuts都搬走。举个 counter example吧。
: 假设 N = 101kg，C = 50kg，F = 1，D = 10 km。
: 这时候，如果我问你，你现在一次最多能载 50kg，你选择跑多少次来回？相信很多人都会答两次，因为第三次还剩下 1kg，很不值对吧？
: 通常，人都会考虑载三轮（跑一个来回+最后一次跑一趟就够了)，把剩下的 1kg 索性不要好了，然后尽可能载得越远越好。
: 那如果这样呢？我决定载五轮（跑两个来回+最后一次跑一趟就够了），把所有都运送去下一站点。然后，我下一站点定位为从起始点的 0.2 km。跑了0.2 km，耗了总共 0.2 * 5 * 1 = 1 kg 的 nuts。这时候，我已经成功把 100 kg 的 nuts 成功运输到这一站点，而且还跑了比之前方法的多 0.2 km。再说，下一轮我就只需要载三轮而已，还省了一个来回！
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

i*e2012-05-11 07:05

51 楼

Hint:
The function is a tail recursion.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 g*l 的大作中提到】

: The code (in Java version) didn't work for my test case
: D=1000, N=20000000, F=1, C=2000
: I got "java.lang.StackOverflowError"
:
: from.html

i*e2012-05-11 07:05

52 楼

正解！
我还没仔细想好怎么证明，但是觉得应该可以用数学来证明这是最优解。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

共

【在 k***s 的大作中提到】

: 看了网站上的解答，应该是在第一步的结束的时候，剩下nut肯定是C的整倍数了。
: 而且每经过一个middle point的时候，下一步的round trip会少一个，直观上看
: 这个应该是最优的；步知道理论上能不能证明这一点。
:
: 要了。
: 人都会答两次，因为第三次还剩下 1kg，很不值对吧？
: 性不要好了，然后尽可能载得越远越好。
: 送去下一站点。然后，我下一站点定位为从起始点的 0.2 km。跑了0.2 km，耗了总共
: 0.2 * 5 * 1 = 1 kg 的 nuts。这时候，我已经成功把 100 kg 的 nuts 成功运输到这
: 一站点，而且还跑了比之

i*e2012-05-11 07:05

53 楼

The stack does not have enough space to accommodate recursive calls that are
too deep. C++ would have the same problem too.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 g*l 的大作中提到】

: The code (in Java version) didn't work for my test case
: D=1000, N=20000000, F=1, C=2000
: I got "java.lang.StackOverflowError"
:
: from.html

i*e2012-05-11 07:05

54 楼

Straight conversion to iterative version. This would prevent stack from
overflowing.
double getMaxNutsIter(double N, double D, double C, double F) {
while (N > C) {
// # trips you would travel back and forth
int numTrips = 2*(ceil(N/C) - 1) + 1;
// how many nuts you consume per km
double costPerKm = numTrips * F;
// remaining weight of nuts after consumption
double remainingNuts = C*(ceil(N/C) - 1.0);
// this is the distance you are able to travel before you
// reach ONE LESS round trip fetching nuts
// derived form eq: N - costPerKm * traveled = remainingNuts
double traveled = (N - remainingNuts) / costPerKm;
// we are able to travel greater (or equal) than the remaining
distance
// so fetch the nuts right to the destination
if (traveled >= D)
return N - D*costPerKm;
N = remainingNuts;
D -= traveled;
}
double nutsAtDestination = N - D*F;
return (nutsAtDestination >= 0.0) ?
nutsAtDestination :
0.0; // out of fuel!
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

g*l2012-05-11 07:05

55 楼

This sounds right to me too!

共

【在 k***s 的大作中提到】

: 看了网站上的解答，应该是在第一步的结束的时候，剩下nut肯定是C的整倍数了。
: 而且每经过一个middle point的时候，下一步的round trip会少一个，直观上看
: 这个应该是最优的；步知道理论上能不能证明这一点。
:
: 要了。
: 人都会答两次，因为第三次还剩下 1kg，很不值对吧？
: 性不要好了，然后尽可能载得越远越好。
: 送去下一站点。然后，我下一站点定位为从起始点的 0.2 km。跑了0.2 km，耗了总共
: 0.2 * 5 * 1 = 1 kg 的 nuts。这时候，我已经成功把 100 kg 的 nuts 成功运输到这
: 一站点，而且还跑了比之

d*22012-05-11 07:05

56 楼

How about this DP:
/*Solution:
total # of one way trip (from start): t = (N-1)/C+1
move i km (from start), the total left nuts: x(i) = N - t*2*i*F
move from j km to i km (jso apply DP,
for i := [2,D]
for j := [1,i)
xij = x(j) - [(x(j)-1)/C+1] * 2 * (i-j) * F;
if(x(i) < xij)
x(i) = xij;
laststop[i] = j; //backtrack
*/
int GetMaxNuts(int D/*distance*/, int N /*# of nuts*/, int F /*fuel per km*/
, int C /*carry each round*/)
{
int* x = new int[D+1];
int* lastStop = new int[D+1];
int round = (N-1)/C+1;
for (int i=0; i<=D; i++)
{
x[i] = N-round*2*i*F;
lastStop[i] = 0;
}
for(int i=2; i<=D; i++)
{
for(int j=1; j{
int xij = x[j] - ((x[j]-1)/C+1) * 2 * (i-j) * F;
if(x[i] < xij)
{
x[i] = xij;
lastStop[i] = j;
}
}
}
return x[D];
}