Statistics

Problem Statement for "Candles"

Problem Statement

In Computer Science we hold weird ceremonies -- at each ceremony we display all our candles but only n of them are lit (yeah, a binary code). Unfortunately we have 2 different types of candles: we have n1 candles that each burn at the rate r1, and n2 candles that each burn at the rate r2. (The rates are in mm/hr.)

Before each ceremony we can choose which n of our candles will be the ones that are lit during the ceremony -- we do this in an attempt to keep our candles approximately the same length. Given n, n1, r1, n2, and r2 return the number of ceremonies required for us to return our candles to uniform length. If we can never achieve uniform length, return -1.

(You may assume that our candles are arbitrarily long or that our ceremonies are arbitrarily short so we won't completely burn up any candles.)

Definition

Class:
Candles
Method:
ceremonies
Parameters:
int, int, int, int, int
Returns:
int
Method signature:
int ceremonies(int n, int n1, int r1, int n2, int r2)
(be sure your method is public)

Constraints

  • n, n1, r1, n2, r2 will all be between 1 and 1000, inclusive.
  • n1+n2 will be greater than n.

Examples

  1. 5

    6

    5

    4

    5

    Returns: 2

    We have 6 type 1 candles and 4 type 2's and we burn 5 candles at each ceremony. Here they burn at the same rate, so we can burn any 5 of them during the first ceremony and the other five at the next ceremony.

  2. 3

    12

    4

    6

    2

    Returns: 8

    For the first 6 ceremonies we could burn fresh candles, 2 of type 1 and 1 of type 2. At that point the type 1 candles will be shorter than the type 2 candles. For the last 2 ceremonies burn 3 type 2 candles and then the other 3 type 2 candles -- all the candles will now be the same length.

  3. 19

    10

    1

    10

    10

    Returns: -1

    We don't have much choice here. In each ceremony we must burn all our candles except for 1. We will never be able to burn enough of the slower burning candles to get them as short as the others.

  4. 56

    50

    20

    60

    16

    Returns: 125

  5. 13

    7

    8

    9

    11

    Returns: 149

  6. 5

    1

    3

    5

    2

    Returns: 17

  7. 5

    9

    3

    4

    2

    Returns: 6

  8. 880

    480

    20

    480

    24

    Returns: 6

  9. 881

    480

    20

    480

    24

    Returns: -1

  10. 880

    480

    20

    480

    23

    Returns: 258

  11. 579

    1000

    888

    997

    991

    Returns: 1876336

  12. 1000

    1000

    1000

    1000

    1000

    Returns: 2

  13. 1000

    500

    500

    501

    500

    Returns: 1001

  14. 1000

    500

    500

    501

    501

    Returns: 501

  15. 1000

    500

    500

    501

    502

    Returns: -1

  16. 1000

    500

    500

    503

    502

    Returns: 1005

  17. 321

    787

    847

    935

    874

    Returns: 493261

  18. 643

    78

    206

    804

    117

    Returns: 174750

  19. 795

    556

    189

    760

    214

    Returns: 262624

  20. 255

    135

    385

    188

    689

    Returns: -1

  21. 215

    628

    177

    737

    521

    Returns: 457637

  22. 635

    307

    441

    715

    391

    Returns: 435352

  23. 891

    386

    337

    518

    171

    Returns: -1

  24. 954

    54

    953

    958

    596

    Returns: 472579

  25. 785

    754

    107

    338

    223

    Returns: 204308

  26. 319

    462

    904

    354

    518

    Returns: 279666

  27. 292

    105

    166

    484

    776

    Returns: -1

  28. 272

    206

    520

    793

    152

    Returns: 55459

  29. 761

    1

    177

    989

    219

    Returns: 58424

  30. 606

    653

    670

    869

    362

    Returns: 68218

  31. 508

    444

    577

    724

    580

    Returns: 168817

  32. 824

    346

    687

    655

    63

    Returns: -1

  33. 763

    744

    943

    485

    469

    Returns: 806291

  34. 389

    287

    915

    560

    134

    Returns: 550858

  35. 560

    550

    374

    337

    392

    Returns: 170819

  36. 385

    391

    899

    258

    386

    Returns: 382868

  37. 999

    592

    249

    871

    181

    Returns: 324031

  38. 567

    125

    894

    672

    574

    Returns: 48037

  39. 999

    1000

    999

    1000

    998

    Returns: 1997000

  40. 383

    719

    422

    896

    717

    Returns: 893635

  41. 999

    991

    997

    989

    995

    Returns: 1972078

  42. 1000

    999

    239

    998

    1

    Returns: 239521

  43. 531

    863

    124

    68

    136

    Returns: 31450

  44. 3

    3

    3

    1

    1

    Returns: -1

  45. 610

    693

    642

    176

    208

    Returns: -1

  46. 1000

    999

    998

    997

    996

    Returns: 199001

  47. 3

    2

    1

    2

    1

    Returns: 4

  48. 3

    2

    1

    2

    2

    Returns: 2

  49. 5

    7

    11

    5

    13

    Returns: 146

  50. 999

    500

    991

    500

    997

    Returns: -1

  51. 1

    1000

    999

    999

    1000

    Returns: 1998001

  52. 991

    993

    995

    997

    999

    Returns: 1984022

  53. 123

    234

    456

    567

    789

    Returns: 49242

  54. 1000

    1000

    1000

    501

    999

    Returns: 1500

  55. 7

    6

    4

    5

    3

    Returns: 38

  56. 3

    2

    2

    2

    1

    Returns: 2

  57. 18

    10

    1

    10

    10

    Returns: -1

  58. 2

    1000

    1000

    1000

    1

    Returns: 500500

  59. 2

    2

    2

    1

    1

    Returns: 2

  60. 724

    502

    74

    321

    107

    Returns: 107

  61. 6

    3

    3

    5

    4

    Returns: 9

  62. 340

    426

    935

    917

    574

    Returns: 1101919

  63. 9

    57

    58

    59

    61

    Returns: 6899

  64. 9

    9

    2

    1

    1

    Returns: -1

  65. 9

    5

    1

    5

    1

    Returns: 10

  66. 10

    2

    2

    9

    1

    Returns: 2

  67. 21

    24

    81

    55

    45

    Returns: 205

  68. 4

    2

    2

    3

    3

    Returns: 3

  69. 2

    3

    3

    1

    1

    Returns: 3

  70. 599

    497

    499

    498

    498

    Returns: 496008

  71. 983

    991

    977

    971

    997

    Returns: 1936694

  72. 999

    998

    997

    996

    995

    Returns: 1986022

  73. 923

    782

    725

    829

    528

    Returns: 1013921

  74. 569

    123

    456

    567

    789

    Returns: -1

  75. 10

    9

    2

    100

    3

    Returns: 227

  76. 6

    5

    1000

    5

    1

    Returns: -1

  77. 10

    1

    1

    99

    1

    Returns: 10

  78. 999

    999

    333

    917

    311

    Returns: 1850

  79. 384

    887

    916

    778

    794

    Returns: 708463

  80. 12

    9

    1

    4

    1

    Returns: 13

  81. 11

    7

    5

    6

    6

    Returns: 72

  82. 8

    5

    1000

    5

    999

    Returns: 9995

  83. 4

    100

    2

    1

    1

    Returns: 51

  84. 1000

    600

    1000

    600

    999

    Returns: 5997

  85. 491

    695

    84

    974

    524

    Returns: 111499

  86. 2

    2

    20

    2

    30

    Returns: 5

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: