g*l
发帖数: 385 | 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' | g*********s
发帖数: 1782 | 2 脑筋急转弯？马多跑几趟，一边走一边卸货做下一次的储备？
【在 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
| k***s
发帖数: 277 | 3 基本思路应该是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*l
发帖数: 385 | 4 我也是怎么想的, 如果直接跑整趟, 那马有可能半道就没有能量了. 关键是怎么找中途
那些卸货点.
还是瞒难的题, 考算法还有情况考虑周到否. 我是上来就 assume 每次跑全程, 被指出
不对.
【在 g*********s 的大作中提到】
: 脑筋急转弯？马多跑几趟，一边走一边卸货做下一次的储备？
| g*l
发帖数: 385 | 5 面试官没有说应该用啥方法. 能用文字讲讲你的思路和这个等式吗?
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;
| P********l
发帖数: 452 | 6 binary search on the number of rounds. | g*l
发帖数: 385 | 7 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.
| h***n
发帖数: 276 | 8 需要澄清一下，马卸货以后返回去载下一次时还要吃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
| g*l
发帖数: 385 | 9 马只要移动, 就要消耗 nuts 做能量.
【在 h***n 的大作中提到】
: 需要澄清一下，马卸货以后返回去载下一次时还要吃nuts吗？
:
: 示即使 D*F>C, 结
: 一下, 谢先!
: 他换一道? 唉, 大概
| g*l
发帖数: 385 | 10 大侠, 解释一下. 我没想明白.
【在 P********l 的大作中提到】
: binary search on the number of rounds.
| | | c******n
发帖数: 4965 | 11 不就是那个绕圈加油的问题么？
答案都说了很多遍了
来面世官
提示即
下, 谢先!
他换一道?
唉,
【在 g*l 的大作中提到】
: 大侠, 解释一下. 我没想明白.
| c******n
发帖数: 4965 | 12 oh, 不是加油。
因为不论多重，cost 都是一样的，那就肯定尽量多背，
如果剩的不够capacity, 就都背走， 啦到max range, 然后recursively 解剩下的距离
你想难了
来面世官
提示即
下, 谢先!
他换一道?
唉,
【在 g*l 的大作中提到】
: 大侠, 解释一下. 我没想明白.
| g*l
发帖数: 385 | 13 给个 link ?
【在 c******n 的大作中提到】
: 不就是那个绕圈加油的问题么？
: 答案都说了很多遍了
:
: 来面世官
: 提示即
: 下, 谢先!
: 他换一道?
: 唉,
| c******n
发帖数: 4965 | 14 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 ?
| g*l
发帖数: 385 | 15 尽量多背没错, 但走多远? 啥是 max range. 我怎么觉得是你想简单了. 如果你解释不
清, 上 code 我
应该明白.
【在 c******n 的大作中提到】
: oh, 不是加油。
: 因为不论多重，cost 都是一样的，那就肯定尽量多背，
: 如果剩的不够capacity, 就都背走， 啦到max range, 然后recursively 解剩下的距离
: 你想难了
:
: 来面世官
: 提示即
: 下, 谢先!
: 他换一道?
: 唉,
| g*l
发帖数: 385 | 16 刚发, 才发现你已经上 code 了. 让我看看.
【在 g*l 的大作中提到】
: 尽量多背没错, 但走多远? 啥是 max range. 我怎么觉得是你想简单了. 如果你解释不
: 清, 上 code 我
: 应该明白.
| k*****e
发帖数: 22013 | 17 这个显然不对啊。
走过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*l
发帖数: 385 | 18 好象不太对哦! 你这个是假设一次都能背动. 但是马每次也许只能背很小 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*l
发帖数: 385 | 19 另外, 你没有考虑到最后一趟并不需要往返跑. 看来我没做出来, 并不冤枉. 大牛也有
疏漏的地方.
冒犯了, 别拍我, 赶紧跑... :-)
【在 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********e
发帖数: 1972 | | | | g*l
发帖数: 385 | 21 那为啥不是 半公里半公里般? 我决的是要慢慢般, 只是具体多慢没想好.
【在 h********e 的大作中提到】
: 一公里一公里的搬，每公里的最后一车要注意算？
| D*****7
发帖数: 766 | 22 我有一点想法了，大家来看看到底对不对。
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**********e
发帖数: 1145 | 23 这题有很强的递归性。
我的思路是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******n
发帖数: 4965 | 24 有意思， 这是个数学题
我开始的方法没有特别错， 我想的时候老把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******n
发帖数: 4965 | 25 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******n
发帖数: 4965 | 26 啊，好像对的，
e^(-DK) > (2)^(-2Dk) = 每次吃一半的解法
【在 c******n 的大作中提到】
: err .... 不对了。。
: 挪的距离也得算啊。
:
: ' 是
: /
| l**********n
发帖数: 12 | 27 //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*l
发帖数: 385 | 28 多谢楼上几位大侠指点! 属我愚钝, 觉得说得都在理, 但不很确信拿个是完全正确的.
来个 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**********e
发帖数: 1145 | 29 其实我之前的帖子有一些错误.
例如，我的假设是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*l
发帖数: 385 | 30 感觉有错误. 你算 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*l
发帖数: 385 | 31 虽然我认为还有错, 但大侠的总体分析还是很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**********e
发帖数: 1145 | 32 感觉有错误. 你算 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**********e
发帖数: 1145 | 33 这个等式中的后半部分是比较剩下的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*l
发帖数: 385 | 34 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***s
发帖数: 277 | 35 看了网站上的解答，应该是在第一步的结束的时候，剩下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**********e
发帖数: 1145 | 36 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**********e
发帖数: 1145 | 37 正解！
我还没仔细想好怎么证明，但是觉得应该可以用数学来证明这是最优解。
一些常见面试题的答案与总结 -
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**********e
发帖数: 1145 | 38 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**********e
发帖数: 1145 | 39 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*l
发帖数: 385 | 40 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****2
发帖数: 12 | 41 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 (j
so 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];
} |
|
