Skip to content

Instantly share code, notes, and snippets.

@walterhuangsz
Created November 14, 2012 03:01
Show Gist options
  • Save walterhuangsz/4070008 to your computer and use it in GitHub Desktop.
Save walterhuangsz/4070008 to your computer and use it in GitHub Desktop.
Monkey carry banana
namespace MonkeyMoveBanana
{
class Program
{
static void Main(string[] args)
{
int left = CalculateMaxBananaLeft(50, 100, 50, 1);
Console.WriteLine(left);
Console.ReadKey();
}
/* 微博@陈利人 面试题
一个小猴子边上有100 根香蕉,它要走过50 米才能到家,每次它最多搬50 根香蕉,每走1 米就要吃掉一根,请问它最多能把多少根香蕉搬到家里。
*/
static int CalculateMaxBananaLeft(int maxCarry, int totalBanana, int distance, int consume)
{
int left = totalBanana;
int movedDistance = 0;
int remainder = 0;
int quotient = 0;
int moveTimePerUnit = 0;
int costPerUnit = 0;
while (left > maxCarry && movedDistance < distance)
{
remainder = left % maxCarry;
quotient = left / maxCarry;
moveTimePerUnit = remainder == 0 ? quotient : quotient + 1;
costPerUnit = consume * (moveTimePerUnit * 2 - 1);
movedDistance++;
left = left - costPerUnit;
if (left - maxCarry <= costPerUnit)
{
break;
}
}
left = maxCarry - (distance - movedDistance) * consume;
return left;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment