Statistics

Problem Statement for "MaxMinTreeGame"

Problem Statement

MaxMinTreeGame is a game for two players. The game is played on a tree. The tree has N nodes, labeled 0 through N-1. Each node of the tree also has an integer cost.

The players take alternating turns. In her turn, the current player starts by choosing one edge of the tree and erasing it. This necessarily divides the tree into two components. The current player then decides which of the components to keep, and erases the other component completely.

The game ends when there is only one node left. The cost of that node is the result of the game. The first player (i.e., the one that starts the game) wants to maximize the result. Naturally, the second player's goal is to minimize the result.

You are given a int[] edges that describes the structure of the tree. For each i between 0 and N-2, inclusive, the tree contains an edge between the vertices i+1 and edges[i]. You are also given a int[] costs. For each i between 0 and N-1, inclusive, the cost of vertex i is costs[i].

Return the result of the game, assuming that both players play optimally.

Definition

Class:
MaxMinTreeGame
Method:
findend
Parameters:
int[], int[]
Returns:
int
Method signature:
int findend(int[] edges, int[] costs)
(be sure your method is public)

Constraints

  • The number of nodes in the tree N will be between 2 and 50, inclusive.
  • edges will contain exactly N-1 elements.
  • For each i, edges[i] will be between 0 and i, inclusive.
  • costs will contain exactly N elements.
  • Each element of costs will be between 0 and 1,000,000,000, inclusive.

Examples

  1. {0}

    {4,6}

    Returns: 6

    There is only one edge in this tree and the first player will choose it. After that she will keep the component containing the node with cost 6.

  2. {0,1}

    {4,6,5}

    Returns: 5

    One of the optimal moves for the first player is to remove the edge between nodes 0 and 1 and to keep the component containing nodes 1 and 2. The second player will then remove the remaining edge and keep the node with cost 5.

  3. {0,1,2,3}

    {0,1,0,1,0}

    Returns: 0

  4. {0,0,0}

    {5,1,2,3}

    Returns: 3

  5. {0,0}

    {3,2,5}

    Returns: 5

  6. {0,1,1,0,4,4,5,6,7}

    {4,9,2,4,2,7,8,5,2,7}

    Returns: 7

  7. {0,1,1,0,4}

    {5,1,6,3,1,10}

    Returns: 10

  8. {0,1,1,0,4,4}

    {1,10,6,6,7,6,7}

    Returns: 7

  9. {0,1,1,0,4,4,5}

    {8,10,5,3,2,2,9,4}

    Returns: 9

  10. {0,1,1,0,4,4,5,6}

    {7,7,10,1,2,1,1,10,4}

    Returns: 10

  11. {0,1,1,0,4,4,5,6,7}

    {4,9,2,4,2,7,8,5,2,7}

    Returns: 7

  12. {0,1,1,0,4,4,5,6,7,4}

    {7,4,3,8,8,5,8,9,10,7,10}

    Returns: 10

  13. {0,1,1,0,4,4,5,6,7,4,7}

    {2,5,6,3,4,6,5,4,9,7,1,9}

    Returns: 9

  14. {0,1,1,0,4,4,5,6,7,4,7,5}

    {6,9,1,10,1,4,4,10,10,8,1,7,8}

    Returns: 10

  15. {0,1,1,0,4,4,5,6,7,4,7,5,11}

    {5,5,9,8,1,1,2,8,9,2,1,1,4,8}

    Returns: 9

  16. {0,1,1,0,4,4,5,6,7,4,7,5,11,13}

    {3,10,4,6,5,9,4,7,10,5,8,3,4,3,1}

    Returns: 10

  17. {0,1,1,0,4,4,5,6,7,4,7,5,11,13,1}

    {1,10,10,4,9,10,7,5,2,1,3,5,2,6,9,3}

    Returns: 10

  18. {0,1,1,0,4,4,5,6,7,4,7,5,11,13,1,11}

    {10,3,4,5,4,2,4,6,4,7,6,10,1,9,3,3,7}

    Returns: 7

  19. {0,1,1,0,4,4,5,6,7,4,7,5,11,13,1,11,3}

    {8,6,10,4,1,4,1,9,6,2,6,1,9,5,8,1,2,2}

    Returns: 10

  20. {0,1,1,0,4,4,5,6,7,4,7,5,11,13,1,11,3,8}

    {4,6,7,3,2,5,2,7,2,3,3,3,2,8,5,2,7,4,5}

    Returns: 7

  21. {0,1,1,0,4,4,5,6,7,4,7,5,11,13,1,11,3,8,1}

    {8,4,8,2,3,8,10,2,5,2,2,3,1,4,1,2,7,10,10,4}

    Returns: 10

  22. {0,1,1,0,4,4,5,6,7,4,7,5,11,13,1,11,3,8,1,16,9}

    {7,4,10,4,1,7,5,6,6,10,9,6,3,6,7,6,1,10,6,1,4,3}

    Returns: 10

  23. {0,1,1,0,4,4,5,6,7,4,7,5,11,13,1,11,3,8,1,16,9,18,15,9}

    {7,4,10,4,9,6,4,7,10,4,7,5,2,1,3,9,9,6,8,6,8,6,2,9,4}

    Returns: 10

  24. {0,1,1,0,4,4,5,6,7,4,7,5,11,13,1,11,3,8,1,16,9,18,15,9,17,6,6}

    {6,9,8,3,8,2,9,5,8,6,9,1,4,4,9,9,10,1,4,1,8,2,1,4,1,4,6,5}

    Returns: 9

  25. {0,1,1,0,4,4,5,6,7,4,7,5,11,13,1,11,3,8,1,16,9,18,15,9,17,6,6,12}

    {5,9,7,3,1,1,3,3,1,3,4,5,4,2,6,7,9,6,1,10,7,3,3,4,6,6,3,7,3}

    Returns: 10

  26. {0,1,1,0,4,4,5,6,7,4,7,5,11,13,1,11,3,8,1,16,9,18,15,9,17,6,6,12,27,5}

    {3,7,6,7,10,2,6,4,5,2,6,2,3,4,6,10,6,7,1,4,8,10,8,4,2,10,1,1,8,5,3}

    Returns: 10

  27. {0,1,1,0,4,4,5,6,7,4,7,5,11,13,1,11,3,8,1,16,9,18,15,9,17,6,6,12,27,5,22,30,20,12}

    {5,9,5,1,5,3,3,3,4,3,9,10,3,1,9,7,7,9,6,1,1,8,1,9,4,7,9,8,7,8,8,5,8,2,2}

    Returns: 9

  28. {0,1,1,0,4,4,5,6,7,4,7,5,11,13,1,11,3,8,1,16,9,18,15,9,17,6,6,12,27,5,22,30,20,12,14,4,26}

    {8,3,7,1,4,5,5,4,8,2,6,5,1,1,8,5,9,3,4,8,7,10,2,10,6,1,4,5,8,8,1,1,4,9,3,10,7,8}

    Returns: 10

  29. {0,1,1,0,4,4,5,6,7,4,7,5,11,13,1,11,3,8,1,16,9,18,15,9,17,6,6,12,27,5,22,30,20,12,14,4,26,3,31,14}

    {8,3,4,4,1,4,5,6,1,1,3,5,2,5,10,8,6,1,9,3,3,4,4,8,2,2,6,8,9,8,2,9,2,1,9,3,4,4,2,4,5}

    Returns: 9

  30. {0,1,1,0,4,4,5,6,7,4,7,5,11,13,1,11,3,8,1,16,9,18,15,9,17,6,6,12,27,5,22,30,20,12,14,4,26,3,31,14,3,39,18}

    {4,1,6,7,4,1,6,6,8,5,10,3,8,10,9,2,1,6,3,5,6,2,8,10,5,8,3,3,6,7,3,2,9,10,9,3,5,3,1,5,8,9,8,6}

    Returns: 10

  31. {0,1,1,0,4,4,5,6,7,4,7,5,11,13,1,11,3,8,1,16,9,18,15,9,17,6,6,12,27,5,22,30,20,12,14,4,26,3,31,14,3,39,18,17,33}

    {6,9,3,6,6,6,7,6,6,1,1,9,10,4,4,3,2,1,8,7,4,4,1,9,7,5,10,8,2,10,2,9,1,5,10,1,6,7,7,8,2,2,7,3,1,7}

    Returns: 10

  32. {0,1,1,0,4,4,5,6,7,4,7,5,11,13,1,11,3,8,1,16,9,18,15,9,17,6,6,12,27,5,22,30,20,12,14,4,26,3,31,14,3,39,18,17,33,18}

    {10,2,9,1,1,3,9,7,6,4,4,3,6,9,10,6,4,7,7,7,3,5,5,10,2,5,2,4,8,9,6,8,3,4,5,6,1,2,4,2,4,7,5,4,2,4,1}

    Returns: 10

  33. {0,1,1,0,4,4,5,6,7,4,7,5,11,13,1,11,3,8,1,16,9,18,15,9,17,6,6,12,27,5,22,30,20,12,14,4,26,3,31,14,3,39,18,17,33,18,7}

    {10,6,3,1,2,9,10,7,1,7,1,3,10,3,5,8,6,8,4,5,6,3,4,7,1,5,9,1,6,10,5,10,5,10,7,4,1,2,5,10,4,3,6,8,9,1,2,8}

    Returns: 10

  34. {0,1,1,0,4,4,5,6,7,4,7,5,11,13,1,11,3,8,1,16,9,18,15,9,17,6,6,12,27,5,22,30,20,12,14,4,26,3,31,14,3,39,18,17,33,18,7,31}

    {9,9,6,5,5,1,3,2,10,3,4,8,8,4,6,7,6,3,9,6,7,4,3,10,6,4,1,8,4,7,1,5,5,9,7,6,6,5,5,5,8,3,6,1,9,3,9,9,2}

    Returns: 10

  35. {0,1,1,0,4,4,5,6,7,4,7,5,11,13,1,11,3,8,1,16,9,18,15,9,17,6,6,12,27,5,22,30,20,12,14,4,26,3,31,14,3,39,18,17,33,18,7,31,29}

    {2,7,4,6,6,8,10,5,3,5,6,9,3,3,4,3,9,9,6,3,1,3,4,4,6,6,5,4,2,5,7,5,4,6,3,8,6,10,6,7,10,2,9,10,5,10,1,10,9,7}

    Returns: 10

  36. {0,1,1,0,4,4,5,6,7,4,7,5,11,13,1,11,3,8,1,16,9,18,15,9,17,6,6,12,27,5,22,30,20,12,14,4,26,3,31,14,3,39,18,17,33,18,7,31,29}

    {705313920,947003012,131883460,532260578,128621514,344251342,41068677,7423146,528499796,461929654,554485848,545442203,76297464,40025128,81223170,135446064,256340856,998094512,273460125,69810647,655827782,883178959,513318609,940507999,101895842,466495353,279233230,848294288,776656627,392922500,648916774,295701332,647138905,377639521,966382907,854549185,594516988,184889472,558424126,360893118,204598833,979089057,690244395,119251579,290290067,175969003,859328777,504766057,89237328,49998781}

    Returns: 979089057

  37. {0,1,1,0,4,4,5,6,7,4,7,5,11,13,1,11,3,8,1,16,9,18,15,9,17,6,6,12,27,5,22,30,20,12,14,4,26,3,31}

    {703625310,481809662,340756839,467277644,85629411,344251342,41068677,7423146,528499796,461929654,554485848,545442203,76297464,40025128,81223170,135446064,256340856,998094512,273460125,69810647,655827782,883178959,513318609,940507999,101895842,466495353,279233230,848294288,776656627,392922500,648916774,295701332,647138905,377639521,966382907,854549185,594516988,184889472,558424126,360893118}

    Returns: 966382907

  38. {0,1,1,0,4,4,5,6,7,4,7,5,11,13,1,11,3,8,1,16,9,18,15,9,17,6,6,12,27}

    {275656031,435224701,367222558,400308666,809416067,639946484,870057027,474943544,371325801,497975563,945676211,350600941,707113442,227334306,287935952,892725141,135405809,510954123,842339883,923241784,613088900,342897052,482624575,985779399,440449404,63860621,467717258,510425315,855036402,868268625}

    Returns: 985779399

  39. {0,1,1,0,4,4,5,6,7}

    {232402,755800,583867,339607,875529,376544,631461,749851,945477,746468}

    Returns: 945477

  40. {0,1,1,0,4,4,5,6,7,4,7,5,11,13,1,11,3,8,1,16,9,18,15,9,17,6,6,12,27,5,22,30,20,12}

    {674938,605380,884976,314965,149004,888292,599059,47552,266799,256439,228797,509468,168705,604150,457585,135654,274931,14091,704334,510148,999094,396382,440435,426143,31357,495632,816985,705254,139759,679800,369451,531692,68455,627349,485643}

    Returns: 884976

  41. {0,1,1,0,4,4,5,6,7,4,7,5,11,13,1,11,3,8,1,16,9,18,15,9,17,6,6,12,27,5,22,30,20,12,14,4,26,3,31,14,3,39,18,17,33,18,7,31,29}

    {999011,514077,219519,535217,859302,251342,531551,826783,477982,675396,122342,223013,862065,892309,475416,663622,621479,900258,674854,386322,808551,131957,537597,127590,923299,344305,780802,273727,787572,42744,359078,775154,926927,960518,545003,466083,38783,408731,133168,860015,930149,499704,464205,41544,416106,532485,676592,217110,572032,708849}

    Returns: 930149

  42. {0 }

    {100, 1 }

    Returns: 100

  43. {0 }

    {5, 4 }

    Returns: 5

  44. {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9 }

    {6484, 11985, 22973, 25281, 1673, 2597, 28710, 29331, 31018, 31295, 15651, 21501, 6929, 25696, 10368, 18660, 31388, 24891, 23732, 13371, 2052, 5372, 20171, 21031, 31978, 18569, 675, 15201, 25139, 10248, 24411, 14301, 10262, 19105, 10249, 9385, 1139, 26501, 27819, 28951, 2919, 23599, 1889, 30494, 13853, 26602, 31193, 13054, 19431, 16531 }

    Returns: 31978

  45. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    {0, 12345, 24690, 37035, 49380, 61725, 74070, 86415, 98760, 111105, 123450, 135795, 148140, 160485, 172830, 185175, 197520, 209865, 222210, 234555, 246900, 259245, 271590, 283935, 296280, 308625, 320970, 333315, 345660, 358005, 370350, 382695, 395040, 407385, 419730, 432075, 444420, 456765, 469110, 481455, 493800, 506145, 518490, 530835, 543180, 555525, 567870, 580215, 592560, 604905 }

    Returns: 604905

  46. {0 }

    {6, 5 }

    Returns: 6

  47. {0, 1 }

    {100, 1, 1 }

    Returns: 100

  48. {0 }

    {100, 10 }

    Returns: 100

  49. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    {1000000000, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5555, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5 }

    Returns: 5555

  50. {0 }

    {2, 1 }

    Returns: 2

  51. {0, 1, 2, 1, 3, 3, 3, 3, 5, 5, 0, 2, 0, 1, 5, 15, 3, 7, 0, 2, 12, 7, 3, 11, 5, 12, 13, 2, 21, 2, 2, 18, 10, 6, 24, 27, 6, 24, 29, 18, 37, 1, 26, 28, 44, 14, 0, 16, 31 }

    {976932633, 516015443, 567510621, 627388619, 360309272, 153984314, 929948152, 889928394, 883531316, 779035539, 868603961, 132219388, 851621352, 99797645, 685487232, 923601601, 883753137, 696583820, 202344348, 498604144, 86228429, 154187423, 147411312, 729373211, 274955197, 384195211, 454872111, 884284962, 406865015, 415946944, 926530941, 583813972, 21034994, 517220739, 655095669, 197749294, 597913807, 183437060, 680995968, 918344842, 860333800, 956412673, 95388115, 492858696, 963398850, 600585651, 586074268, 862132801, 401882329, 237285756 }

    Returns: 956412673

  52. {0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9, 10, 10, 10, 11, 11, 11, 12, 12, 12, 13, 13, 13, 14, 14, 14, 15, 15, 15, 16 }

    {804289383, 846930886, 681692777, 714636915, 957747793, 424238335, 719885386, 649760492, 596516649, 189641421, 25202362, 350490027, 783368690, 102520059, 44897763, 967513926, 365180540, 540383426, 304089172, 303455736, 35005211, 521595368, 294702567, 726956429, 336465782, 861021530, 278722862, 233665123, 145174067, 468703135, 101513929, 801979802, 315634022, 635723058, 369133069, 125898167, 59961393, 89018456, 628175011, 656478042, 131176229, 653377373, 859484421, 914544919, 608413784, 756898537, 734575198, 973594324, 149798315, 38664370 }

    Returns: 973594324

  53. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48 }

    {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 0 }

    Returns: 1000000000

  54. {0, 1, 2, 3 }

    {1, 1, 0, 1, 0 }

    Returns: 1

  55. {0, 1, 1, 0, 4, 3, 5, 6, 8, 6, 4, 2, 0, 4, 3, 4, 0, 8, 13, 0, 17, 4, 21, 13, 2, 21, 3, 16, 2, 6 }

    {743314691, 849551810, 469786584, 542652638, 998162926, 546838875, 712009693, 183313489, 201398242, 159760440, 816249993, 412103839, 756764518, 195282969, 722460568, 450793610, 979780191, 953546232, 492197753, 367487969, 2676986, 641467344, 48946904, 443507707, 532147443, 592048652, 794863955, 220046203, 85488350, 830257761, 62190969 }

    Returns: 830257761

  56. {0, 1, 1 }

    {100, 1, 1, 1 }

    Returns: 100

  57. {0 }

    {6, 4 }

    Returns: 6

  58. {0 }

    {3, 2 }

    Returns: 3

  59. {0 }

    {5, 3 }

    Returns: 5

  60. {0, 0, 2, 0, 4, 5, 6, 3, 5, 3, 7, 0, 5, 5, 11, 6, 5, 8, 17, 16, 14, 6, 22, 22, 0, 24, 25, 24, 17, 8, 26, 12, 11, 5, 33, 30, 26, 20, 35, 4, 8, 20, 5, 19, 16, 20, 37, 15, 22 }

    {377174832, 447777244, 924408590, 614963386, 955387479, 55321788, 323320227, 933173354, 493782484, 347479765, 175868586, 668746446, 576554898, 189959767, 985226943, 901135959, 291063420, 939417234, 172123329, 8722391, 862112004, 911182459, 266778705, 451196679, 220725149, 181954350, 591413336, 149589250, 54422337, 694419047, 351460734, 242391751, 644273132, 590739719, 250292404, 659993018, 667651871, 28561301, 480330155, 222920739, 893539934, 782714554, 458665306, 706438062, 32367538, 108111300, 307709052, 837929962, 478665255, 979125541 }

    Returns: 979125541

  61. {0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9, 10, 10, 10, 11, 11, 11, 12, 12, 12, 13, 13, 13, 14, 14, 14, 15, 15, 15 }

    {15, 15, 15, 14, 14, 14, 13, 13, 13, 12, 12, 12, 11, 11, 11, 10, 10, 10, 9, 9, 9, 8, 8, 8, 7, 7, 7, 6, 6, 6, 5, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0 }

    Returns: 10

  62. {0, 0 }

    {100, 1, 2 }

    Returns: 2

  63. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    {581391213, 535458624, 70203113, 467368763, 580549280, 199035976, 668952417, 266751218, 135121620, 87864464, 628542551, 60849617, 717991698, 451628733, 185857648, 984404988, 181836943, 759389487, 392731482, 675078450, 182685869, 166682704, 122867569, 403095015, 868536530, 371192513, 627527407, 667723661, 685850032, 605563397, 567507429, 103397078, 376459494, 87206412, 934277025, 189483, 238411277, 847493313, 39751637, 736534566, 506481581, 496521309, 802026340, 946479257, 271589100, 144670581, 883496583, 299434361, 703049348, 398465351 }

    Returns: 984404988

  64. {0, 1 }

    {6, 5, 4 }

    Returns: 6

  65. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    {46456, 456, 464, 564, 564, 56, 456, 456, 456, 34, 346, 3456, 375, 576, 4567, 4567, 4567, 4567457, 457, 457, 45, 7457, 456, 456, 456, 456, 456, 45, 634, 653465, 3465, 3465, 65, 346, 456, 36, 36, 456, 546, 645, 564, 564, 564, 645, 456, 6, 6, 645, 645, 54 }

    Returns: 4567457

  66. {0 }

    {1, 0 }

    Returns: 1

  67. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    Returns: 50

  68. {0, 1, 1, 0, 4, 4, 3, 1, 3, 8, 6, 5, 11, 6, 7, 10, 8, 8, 9, 8, 17, 19, 1, 12, 16, 11, 26, 3, 6, 23, 29, 21, 5, 15, 1, 24, 30, 26, 22, 29, 14, 36, 17, 26, 18, 45, 34, 33, 1 }

    {31380, 4940, 26314, 21135, 24309, 850, 20356, 15681, 17026, 14086, 15763, 27344, 6367, 17424, 24145, 18495, 31702, 31394, 10362, 31595, 7068, 9387, 28301, 1533, 3, 1109, 17742, 28789, 11773, 23771, 27794, 12393, 29727, 699, 29531, 3857, 2723, 10113, 13209, 29418, 16479, 21302, 4287, 32491, 25920, 28710, 25719, 7273, 31, 257 }

    Returns: 32491

  69. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    {553814932, 74444440, 187489689, 441522285, 82498708, 514563208, 881570303, 744531397, 561560176, 913333601, 920353225, 416829255, 661905277, 506994575, 746467722, 704268515, 847178043, 467869411, 307304572, 904945613, 287233796, 676380819, 29155475, 835961062, 692601654, 59841304, 903804198, 142891224, 740357675, 306413442, 530312137, 923457186, 980989645, 838299207, 502746580, 864384418, 855297558, 79998116, 833150001, 427354891, 816930576, 901156597, 908333224, 188155383, 942254531, 954232860, 925886375, 641279236, 912357504, 97877213 }

    Returns: 980989645

  70. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100 }

    Returns: 100

  71. {0, 1, 2, 3 }

    {1, 1, 5, 1, 1 }

    Returns: 1

  72. {0, 0 }

    {3, 5, 2 }

    Returns: 5

  73. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46 }

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3 }

    Returns: 3

  74. {0, 1, 2, 1, 4, 4, 2, 3, 4, 5, 6, 3, 6, 11, 14, 3, 4, 6, 7, 5, 14 }

    {422056988, 500044513, 611465376, 317688651, 69549938, 484578281, 870118456, 813988315, 102802487, 536143117, 362284849, 844962515, 214710905, 759096744, 912825298, 84207599, 584013745, 305556212, 777634286, 556255213, 551141786, 474491572 }

    Returns: 777634286

  75. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    {62387, 97401, 30814, 61459, 56513, 49456, 75220, 31266, 43316, 83403, 69758, 60733, 81415, 57808, 6251, 52665, 28622, 79584, 52728, 85277, 88630, 57714, 35316, 87076, 43165, 59520, 86593, 62402, 61558, 996, 96479, 58792, 43386, 66699, 38422, 16297, 97003, 77922, 59079, 80097, 94851, 25785, 88287, 58206, 34263, 13515, 28991, 32561, 9536, 53076 }

    Returns: 97401

  76. {0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24 }

    {34214, 1243, 1342, 1324, 1432, 53, 324, 243, 243, 24, 24, 24, 452, 243, 24, 423, 2, 25, 243, 5, 243, 243, 243, 243, 243, 24, 42, 24, 24, 42, 4, 43, 5, 4, 2, 2, 4, 423, 42, 243, 42, 25, 235, 1243, 1324, 1324, 1324, 3124, 13243241, 3124421 }

    Returns: 13243241

  77. {0, 1, 2, 3 }

    {2, 5, 5, 0, 1 }

    Returns: 2

  78. {0, 1 }

    {1000, 10, 10 }

    Returns: 1000

  79. {0, 1 }

    {780502354, 853891887, 462836342 }

    Returns: 780502354

  80. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48 }

    {666967445, 291513429, 515800664, 982249943, 715846891, 230590222, 409169027, 180172481, 5603647, 698783128, 956038174, 384179927, 817516883, 371794165, 590523019, 441341235, 755155278, 662877686, 116772158, 922146814, 417161258, 92161116, 167118764, 970374290, 919366409, 260025352, 368688251, 284824140, 32011161, 514819332, 868125992, 865810561, 455563938, 611181266, 56912987, 95116018, 577385940, 731159274, 777977301, 890399452, 423590322, 780830240, 724846500, 713394008, 895124717, 432070130, 150298605, 279193873, 726830212, 562691987 }

    Returns: 666967445

  81. {0, 0, 2, 1, 0, 4, 1, 7, 5, 8, 10, 0, 6, 7, 7, 14, 12, 7, 18, 2, 2, 1, 3, 15, 24, 9, 7, 7, 6, 16, 17, 31, 2, 15, 6, 29, 5, 12, 26, 3, 14, 3, 10, 28, 26, 21, 35, 36, 27 }

    {292, 353, 295, 356, 817, 17, 818, 95, 455, 44, 837, 719, 18, 616, 164, 937, 580, 804, 829, 609, 322, 382, 348, 672, 613, 369, 993, 955, 617, 927, 899, 211, 578, 847, 254, 166, 842, 948, 40, 850, 31, 249, 170, 761, 841, 804, 170, 534, 753, 590 }

    Returns: 948

  82. {0, 0, 1, 2, 2, 2, 3, 1, 3, 5, 10, 7, 5, 8, 9, 9, 13, 14, 13, 14, 4, 19, 2, 3, 9, 7, 12, 25, 14, 4, 30, 21, 17, 18, 16, 29, 21, 8, 26, 2, 5, 38, 15, 26, 36, 18, 19, 14, 19 }

    {145, 63, 148, 146, 119, 52, 93, 120, 142, 118, 103, 60, 114, 56, 117, 136, 81, 59, 138, 69, 57, 14, 14, 114, 86, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 }

    Returns: 114

  83. {0, 0, 1 }

    {1, 100, 80, 70 }

    Returns: 80

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: