蛋滴比赛

Question

您的挑战：

你在一座无限高的大楼的0楼。在任何一层楼，你都可以走到窗户前，扔一个鸡蛋。你的目标是找出鸡蛋能承受的最高楼层，而不会破裂。但是，您最多需要使用3个鸡蛋来解决这个问题，但是您需要尽量减少尝试的次数。

正式用语：

1. 您将得到一个函数f(n)，它返回未知X的bool(n <= X)，其中0 <= X
2. 您必须返回X的值(不直接访问它)
3. f(n)只能返回False最多的3次数(在单个测试用例中)。如果它返回的False更多，那么您的答案将被取消资格。

Restrictions

你的分数是你打给f(n)的电话总数(在下面的测试用例中)。

如果您愿意，您可以放弃传递一个函数，而只是简单地“模拟”上述情况。但是，您的求解算法必须对X一无所知。

您的算法不应该硬编码测试用例或最大X。如果我要重新生成这些数字，或者添加更多，您的程序应该能够处理它们(以类似的分数)。

如果您的语言不支持任意精度整数，则可以使用long数据类型。如果你的语言也不支持，那你就倒霉了。

使用以下方法的nth 生成测试用例：

g(n) = max(g(n-1)*random(1,1.5), n+1), g(0) = 0，或近似1.25^n

测试用例：

0,1,2,3,4,6,7,8,10,14,15,18,20,27,29,40,57,61,91,104,133,194,233,308,425,530,735,1057,1308,1874,2576,3162,3769,3804,4872,6309,7731,11167,11476,15223,15603,16034,22761,29204,35268,42481,56238,68723,83062,95681,113965,152145,202644,287964,335302,376279,466202,475558,666030,743517,782403,903170,1078242,1435682,1856036,2373214,3283373,4545125,6215594,7309899,7848365,8096538,10409246,15103057,20271921,22186329,23602446,32341327,33354300,46852754,65157555,93637992,107681394,152487773,181996529,225801707,324194358,435824227,579337939,600264328,827690923,1129093889,1260597310,1473972478,1952345052,1977336057,2512749509,3278750235,3747691805,5146052509

这是一个代码挑战，得分最低的人赢了！

Answer 1

Java，68985调用

public static long solve(Predicate<Long> eggSurvives) {
  long bestFloor = 0, e1 = 1, e2;

  for(long callsDone = 2; eggSurvives.test(e1); bestFloor = e1, e1 += callsDone * callsDone++);

  for(e2 = bestFloor;; bestFloor = e2) {
    e2 += Math.max((long)Math.sqrt(e1 - e2), 1);

    if(e2 >= e1 || !eggSurvives.test(e2)) {
      break;
    }
  }

  for(long e3 = bestFloor + 1; e3 < e2 && eggSurvives.test(e3); e3++) {
    bestFloor = e3;
  }

  return bestFloor;
}

测试结果：

0: 1 1: 4 2: 4 3: 4 4: 4 6: 6 7: 6 8: 6 10: 7 14: 6 15: 7 18: 7 20: 8 27: 10 29: 10 40: 10 57: 10 61: 9 91: 9 104: 11 133: 18 194: 20 233: 18 308: 18 425: 17 530: 17 735: 28 1057: 31 1308: 30 1874: 30 2576: 39 3162: 47 3769: 60 3804: 34 4872: 65 6309: 37 7731: 48 11167: 79 11476: 39 15223: 56 15603: 82 16034: 93 22761: 88 29204: 111 35268: 110 42481: 127 56238: 126 68723: 135 83062: 117 95681: 115 113965: 137 152145: 138 202644: 115 287964: 234 335302: 223 376279: 244 466202: 220 475558: 193 666030: 214 743517: 225 782403: 230 903170: 338 1078242: 223 1435682: 303 1856036: 384 2373214: 453 3283373: 542 4545125: 459 6215594: 525 7309899: 600 7848365: 388 8096538: 446 10409246: 466 15103057: 650 20271921: 822 22186329: 899 23602446: 698 32341327: 804 33354300: 1065 46852754: 1016 65157555: 1408 93637992: 1390 107681394: 1638 152487773: 1283 181996529: 1877 225801707: 2067 324194358: 1842 435824227: 3110 579337939: 2983 600264328: 1817 827690923: 2450 1129093889: 2981 1260597310: 3562 1473972478: 4237 1952345052: 2244 1977336057: 3585 2512749509: 2893 3278750235: 3101 3747691805: 5182 5146052509: 4107

测试程序：

import java.util.function.Predicate;

public class Eggs {
  private static long totalCalls;
  private static long calls;

  public static void main(String[] args) {
    for(long maxFloor : new long[] {0,1,2,3,4,6,7,8,10,14,15,18,20,27,29,40,57,61,91,104,133,194,233,308,425,530,735,1057,1308,1874,2576,3162,3769,3804,4872,6309,7731,11167,11476,15223,15603,16034,22761,29204,35268,42481,56238,68723,83062,95681,113965,152145,202644,287964,335302,376279,466202,475558,666030,743517,782403,903170,1078242,1435682,1856036,2373214,3283373,4545125,6215594,7309899,7848365,8096538,10409246,15103057,20271921,22186329,23602446,32341327,33354300,46852754,65157555,93637992,107681394,152487773,181996529,225801707,324194358,435824227,579337939,600264328,827690923,1129093889,1260597310,1473972478,1952345052,1977336057,2512749509L,3278750235L,3747691805L,5146052509L}) {
      long resultingFloor = solve(f -> {
        calls++;
        return f <= maxFloor;
      });

      if(resultingFloor != maxFloor) {
        throw new RuntimeException("Disqualified");
      }

      System.out.print(maxFloor + ": " + calls + " ");
      totalCalls += calls;
      calls = 0;
    }

    System.out.println("\nCalls = " + totalCalls);
  }

  public static long solve(Predicate<Long> eggSurvives) {
    long bestFloor = 0, e1 = 1, e2;

    for(long callsDone = 2; eggSurvives.test(e1); bestFloor = e1, e1 += callsDone * callsDone++);

    for(e2 = bestFloor;; bestFloor = e2) {
      e2 += Math.max((long)Math.sqrt(e1 - e2), 1);

      if(e2 >= e1 || !eggSurvives.test(e2)) {
        break;
      }
    }

    for(long e3 = bestFloor + 1; e3 < e2 && eggSurvives.test(e3); e3++) {
      bestFloor = e3;
    }

    return bestFloor;
  }
}

在优化过程中，我的目标是使每个鸡蛋的尝试次数大致相等。

• 根据迄今尝试的次数，第一个鸡蛋的楼层数会上升。
• 第二个鸡蛋跳过地板，其基础是可以留下的最大尝试次数的平方根(基于第一个鸡蛋建立的下限和上限)，因此第三个和最后一个鸡蛋的平均尝试次数平均应该与第二个鸡蛋的尝试相同。