Statistics

Problem Statement for "DiskCut"

Problem Statement

The process of producing silicon chips is long and complex. Special care must be taken when cutting a delicate silicon disk. A contractor has hired you to work just in this area. As it turns out, his cutting machine can make only one type of cut: one that starts in the center of the disc, ends at the perimeter and has a length equal to the radius. Such a cut can easily ruin the entire piece being cut. Because of this, the area of the piece being cut is also the price of the cut. Consider an example where you must cut a disk whose area is 100 into 3 pieces whose areas are 33%, 33% and 34% of the disk. The best way to cut them is by first making two cuts around the 34% piece, which costs 100 units per cut. Then make a single cut on the remaining piece of size 66 to get two 33% pieces, which costs 66 units. Thus, the minimum cost would be 266 units of money.

Write a method named minCost that takes an int area and an int[] percent, and returns the minimum cost of cutting a disk of size area into different pieces with sizes from percent. Note that the order of the elements of percent is unimportant, as you only need to achieve the required percentages.

Definition

Class:
DiskCut
Method:
minCost
Parameters:
int, int[]
Returns:
double
Method signature:
double minCost(int area, int[] percent)
(be sure your method is public)

Notes

  • Your return value must have a relative or absolute error less than 1e-9.

Constraints

  • area will be between 1 and 1000, inclusive.
  • percent will have between 2 and 50 elements, inclusive.
  • Each element in percent will be between 1 and 100, inclusive.
  • The elements in percent will sum up to 100.

Examples

  1. 4

    {25,25,25,25}

    Returns: 12.0

    The best way to cut these pieces is by first making two cuts, resulting in two 50% pieces. Then, cut each piece in half. All this costs just 12.0 units.

  2. 5

    {20,20,20,20,20}

    Returns: 17.0

  3. 2

    {50,50}

    Returns: 4.0

  4. 1

    {10, 40, 30, 20}

    Returns: 2.9

  5. 1

    {11, 11, 11, 11, 11, 11, 11, 11, 12}

    Returns: 4.22

  6. 1

    {12, 12, 12, 12, 12, 12, 12, 16}

    Returns: 4.0

  7. 10

    {20,20,30,30}

    Returns: 30.0

  8. 10

    {40,10,20,10,20}

    Returns: 32.0

  9. 100

    {33,33,34}

    Returns: 266.0

  10. 1000

    {2,1,1,1,1,1,1,1,1,1,1,3,1,1,1,1,1,1,1,1,1,1,1,4,1,1,1,1,1,1,1,1,1,15,1,1,1,1,1,1,1,2,1,1,1,1,1,1,30,1}

    Returns: 5480.0

    Some random test.

  11. 100

    {90,3,4,2,1}

    Returns: 219.0

  12. 100

    {90,4,3,2,1}

    Returns: 219.0

  13. 1000

    {2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2}

    Returns: 6720.0

    probably largest return value

  14. 100

    {33,33,34}

    Returns: 266.0

    example in statement

  15. 68

    {9,13,34,35,9}

    Returns: 213.52

  16. 52

    {19,30,14,19,18}

    Returns: 172.64

  17. 476

    {6,21,11,24,38}

    Returns: 1508.92

  18. 433

    {5,8,13,12,62}

    Returns: 1195.08

  19. 893

    {5,26,12,35,22}

    Returns: 2830.81

  20. 387

    {11,35,13,7,34}

    Returns: 1215.18

  21. 241

    {4,36,20,27,13}

    Returns: 763.97

  22. 96

    {28,18,11,27,16}

    Returns: 313.92

  23. 284

    {35,22,35,7,1}

    Returns: 860.52

  24. 47

    {12,23,18,17,30}

    Returns: 154.63

  25. 792

    {8,30,7,28,27}

    Returns: 2494.8

  26. 628

    {9,5,32,11,18,25}

    Returns: 2128.92

  27. 729

    {20,14,38,10,18}

    Returns: 2361.96

  28. 38

    {30,21,14,10,9,16}

    Returns: 132.62

  29. 54

    {18,23,28,12,19}

    Returns: 178.2

  30. 421

    {23,26,6,10,5,11,19}

    Returns: 1524.02

  31. 295

    {13,1,8,30,48}

    Returns: 834.85

  32. 872

    {5,16,11,18,24,26}

    Returns: 3034.56

  33. 801

    {9,22,19,21,4,14,11}

    Returns: 2963.7

  34. 289

    {19,28,19,12,22}

    Returns: 956.59

  35. 238

    {9,13,7,30,6,35}

    Returns: 797.3

  36. 845

    {19,2,19,12,11,16,4,17}

    Returns: 3253.25

  37. 253

    {18,7,41,2,32}

    Returns: 746.35

  38. 241

    {7,8,4,23,22,2,23,9,2}

    Returns: 906.16

  39. 123

    {27,31,14,4,24}

    Returns: 391.14

  40. 995

    {3,24,2,13,3,1,21,12,5,16}

    Returns: 3840.7

  41. 890

    {16,4,12,16,16,11,10,4,11}

    Returns: 3631.2

  42. 551

    {8,3,20,4,16,13,18,16,2}

    Returns: 2165.43

  43. 778

    {4,15,14,3,6,4,12,12,2,20,8}

    Returns: 3267.6

  44. 389

    {17,11,8,11,19,7,12,3,7,5}

    Returns: 1629.91

  45. 334

    {10,13,3,9,11,12,6,10,6,3,12,5}

    Returns: 1496.32

  46. 969

    {6,20,17,15,10,20,6,6}

    Returns: 3759.72

  47. 932

    {13,17,9,9,9,13,4,15,11}

    Returns: 3849.16

  48. 491

    {31,21,1,7,30,2,8}

    Returns: 1625.21

  49. 121

    {15,17,17,6,3,12,11,11,8}

    Returns: 494.89

  50. 1000

    {2,7,6,2,10,13,13,5,12,12,4,3,11}

    Returns: 4490.0

  51. 646

    {9,4,9,1,15,10,12,7,8,4,7,14}

    Returns: 2874.7

  52. 606

    {20,11,14,6,2,2,11,14,1,8,11}

    Returns: 2533.08

  53. 477

    {16,3,2,12,1,21,22,10,9,4}

    Returns: 1884.15

  54. 680

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

    Returns: 3427.2

  55. 789

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

    Returns: 3992.34

  56. 178

    {4,4,14,26,25,27}

    Returns: 587.4

  57. 461

    {17,50,3,3,4,16,7}

    Returns: 1456.76

  58. 205

    {9,3,2,15,21,1,6,2,7,1,12,21}

    Returns: 838.45

  59. 288

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

    Returns: 1460.16

  60. 199

    {10,10,11,11,12,7,13,10,12,4}

    Returns: 857.69

  61. 607

    {14,5,10,16,2,4,12,14,1,1,9,1,11}

    Returns: 2628.31

  62. 370

    {18,27,13,23,1,18}

    Returns: 1280.2

  63. 147

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

    Returns: 748.23

  64. 195

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

    Returns: 1035.45

  65. 515

    {17,12,2,11,9,2,11,10,17,9}

    Returns: 2147.55

  66. 923

    {40,6,4,8,31,11}

    Returns: 2925.91

  67. 158

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

    Returns: 854.78

  68. 885

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

    Returns: 4779.0

  69. 882

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

    Returns: 4348.26

  70. 826

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

    Returns: 4749.5

  71. 854

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

    Returns: 4278.54

  72. 976

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

    Returns: 5690.08

  73. 485

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

    Returns: 2774.2

  74. 870

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

    Returns: 5011.2

  75. 197

    {6,19,6,8,5,1,3,17,21,7,7}

    Returns: 819.52

  76. 990

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

    Returns: 5395.5

  77. 271

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

    Returns: 1539.28

  78. 498

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

    Returns: 2868.48

  79. 217

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

    Returns: 1249.92

  80. 567

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

    Returns: 2579.85

  81. 739

    {2,12,8,1,11,12,9,3,9,1,7,3,5,10,7}

    Returns: 3451.13

  82. 751

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

    Returns: 3965.28

  83. 554

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

    Returns: 2930.66

  84. 368

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

    Returns: 2219.04

  85. 100

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

    Returns: 562.0

  86. 1000

    {3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 2, 2 }

    Returns: 6560.0

  87. 1

    {10, 40, 20, 30 }

    Returns: 2.9

  88. 100

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

    Returns: 507.0

  89. 1

    {10, 40, 30, 20 }

    Returns: 2.9

  90. 15

    {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

    Returns: 100.8

  91. 1000

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 51 }

    Returns: 4790.0

  92. 40

    {5, 5, 5, 5, 7, 5, 8, 60 }

    Returns: 124.8

  93. 1

    {5, 5, 6, 6, 39, 39 }

    Returns: 3.05

  94. 1000

    {3, 5, 7, 9, 6, 30, 40 }

    Returns: 3280.0

  95. 39

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 51 }

    Returns: 186.81

  96. 1

    {1, 10, 1, 10, 1, 10, 1, 10, 1, 10, 1, 10, 1, 10, 1, 10, 1, 10, 1 }

    Returns: 4.74

  97. 1

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

    Returns: 6.3

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: