TopCoder Statistics - Problem Statement

Problem Statement

Inspired by the Dire Straits song, "Money for Nothing", you have decided to become a rock star. After a lengthy recording session, you have acquired:

a total of ff songs that start fast and end fast,
a total of fs songs that start fast and end slow,
a total of sf songs that start slow and end fast, and
a total of ss songs that start slow and end slow.

It remains only to determine which of these songs should go on your first album, and in what order they should appear. Of course, no song can appear on the album more than once.

Unfortunately, your record company has placed several restrictions on your album:

1. A song that ends fast may only be immediately followed by a song that starts fast.
2. A song that ends slow may only be immediately followed by a song that starts slow.
3. If you have at least one song that starts fast, then the first song on the album must start fast. Otherwise, this restriction can be ignored.

At this stage in your artistic career, you must do what your record company has ordered, but you do want to place as many songs as possible on the album.

Given ints ff, fs, sf, and ss, representing the quantities described above, return the maximum number of songs that can be placed on a single album without violating the record company's restrictions.

Definition

Class:: RockStar
Method:: getNumSongs
Parameters:: int, int, int, int
Returns:: int
Method signature:: int getNumSongs(int ff, int fs, int sf, int ss)
(be sure your method is public)

Constraints

ff, fs, sf, and ss will each be between 0 and 1000 inclusive.
At least one of ff, fs, sf or ss will be greater than 0.

Examples

100

0

0

200

Returns: 100

You must begin the album with one of your fast songs by the 3rd restriction. By the 1st restriction, each subsequent song must also now start fast.
0

0

20

200

Returns: 201

Since you do not have any songs that start fast, you may begin the album with a song that starts slow. You can use 201 songs by first using the 200 songs that start slow and end slow, then finishing the album with one song that starts slow and ends fast.
1

2

1

1

Returns: 5
192

279

971

249

Returns: 999
1000

1000

1000

1000

Returns: 4000
100

0

0

0

Returns: 100
0

100

0

0

Returns: 1
0

0

100

0

Returns: 1
0

0

0

100

Returns: 100
350

585

193

0

Returns: 737
304

711

174

823

Returns: 1476
989

147

0

0

Returns: 990
532

0

0

119

Returns: 532
57

451

166

602

Returns: 992
956

876

520

784

Returns: 2781
209

235

1

539

Returns: 751
297

392

1000

844

Returns: 1925
0

56

92

23

Returns: 135
485

838

588

276

Returns: 1938
1

745

458

744

Returns: 1662
225

361

609

385

Returns: 1332
657

345

990

803

Returns: 2150
141

1

505

63

Returns: 206
683

0

426

693

Returns: 683
475

178

582

878

Returns: 1709
756

569

405

504

Returns: 2071
0

835

1

475

Returns: 478
346

922

104

663

Returns: 1218
298

272

317

375

Returns: 1217
891

398

762

567

Returns: 2254
194

0

573

0

Returns: 194
1

123

198

627

Returns: 874
835

140

286

314

Returns: 1429
0

1

252

600

Returns: 602
14

115

853

0

Returns: 244
0

543

752

1

Returns: 1087
533

232

290

202

Returns: 1199
336

925

963

160

Returns: 2346
94

0

998

996

Returns: 94
769

290

0

932

Returns: 1702
635

466

604

202

Returns: 1769
738

375

721

829

Returns: 2317
351

699

189

905

Returns: 1635
149

691

612

80

Returns: 1454
977

43

615

868

Returns: 1931
852

1

174

569

Returns: 1423
820

0

79

155

Returns: 820
323

501

299

448

Returns: 1370
944

725

960

314

Returns: 2708
957

525

0

1

Returns: 959
0

0

2

0

Returns: 1
192

279

971

249

Returns: 999
10

1

0

10

Returns: 21
1000

888

889

988

Returns: 3764
0

0

0

200

Returns: 200
1

1

1

1

Returns: 4
0

0

0

1

Returns: 1
0

0

0

10

Returns: 10
0

1

0

1

Returns: 2
0

0

100

1

Returns: 2
0

0

0

1000

Returns: 1000
10

10

10

10

Returns: 40
0

1

2

0

Returns: 2
0

12

800

0

Returns: 24
0

0

0

3

Returns: 3
0

1

0

10

Returns: 11
1000

1000

1000

1000

Returns: 4000
0

5

1

6

Returns: 9
1

3

1

0

Returns: 4
0

0

467

2

Returns: 3
0

0

5

0

Returns: 1
0

0

6

0

Returns: 1
5

5

0

5

Returns: 11
0

2

1

0

Returns: 3
1

6

5

3

Returns: 15
2

2

2

2

Returns: 8
1

1

0

1

Returns: 3
1

0

1

1

Returns: 1
655

499

796

163

Returns: 1816
0

1

0

0

Returns: 1
3

0

5

4

Returns: 3
5

1

0

4

Returns: 10
0

2

0

0

Returns: 1
1

1

1

0

Returns: 3
0

1

3

1

Returns: 3
980

980

980

980

Returns: 3920

Statistics

Problem Statement for "RockStar"

Problem Statement

Definition

Constraints

Examples