TopCoder Statistics - Problem Statement

Problem Statement

As a serious strategy-games player, you decided to solve one of the most common problems - attacking your opponent's guard towers.

Before the attack, you've got myUnits soldiers. Each soldier in a single round inflicts 1 hit point of damage to one of the towers.
Your opponent doesn't have any soldiers. However, he's got numT towers with hpT hit points each. Each tower kills attackT of your soldiers per round.

The course of one round:
1. Each soldier in your army attacks a tower of your choice for 1 hit point of damage. When a tower loses all its hit points, it is destroyed. You can pick the tower independently for each soldier.
2. Your opponent attacks. He will kill k*attackT of your soliders, where k is the number of remaining towers.

Your task is to destroy all the towers. If it is possible, return the minimum number of rounds you need to do this. Otherwise return -1.

Definition

Class:: Towers
Method:: attack
Parameters:: int, int, int, int
Returns:: int
Method signature:: int attack(int myUnits, int hpT, int attackT, int numT)
(be sure your method is public)

Notes

More than one soldier can attack the same tower in the same round.

Constraints

myUnits will be between 1 and 1000000, inclusive.
hpT, attackT, numT will each be between 1 and 10000, inclusive.

Examples

13

2

3

8

Returns: 2

Round 1: - Your soldiers destroy 6 towers leaving one tower with 1 hit point and one tower with 2 hit points. - Your opponent attacks and kills 2*3=6 of your soldiers. Round 2: - You have 7 soldiers remaining, which is more than enough to take out the 3 hit points of the remaining towers.
10

6

8

2

Returns: 2
10

6

9

2

Returns: -1
1

1

1

1

Returns: 1
10000

10

2

2789

Returns: 10
1000000

10000

10000

10000

Returns: -1
10000

2

1

9999

Returns: 8
1000000

10000

111

999

Returns: 36
1000000

10000

1

10000

Returns: 301
1000000

1271

1271

1271

Returns: 5
10001

10000

1

100

Returns: 493
140

10000

1

1

Returns: -1
141

10000

1

1

Returns: 137
547

10000

1

2

Returns: 39
546

10000

1

2

Returns: 39
1733

547

1

2

Returns: 1
2

1

1

1

Returns: 1
2

1

1

3

Returns: 2
6181

1

1

10000

Returns: 6
6180

1

1

10000

Returns: -1
6200

1

1

10000

Returns: 4
500001

2

1

5000

Returns: 1
3661

1

2

5000

Returns: 4
632709

8018

1

7097

Returns: 336
661962

7039

1

7926

Returns: 307
263221

7878

1

2978

Returns: 326
853699

8090

1

9543

Returns: 451
573713

8659

1

6189

Returns: 336
882173

9380

1

9133

Returns: 326
339724

9906

1

3423

Returns: 343
863490

9316

1

8981

Returns: 356
404662

8186

1

4488

Returns: 314
896257

8420

1

9797

Returns: 310
582915

5727

32

1413

Returns: 92
395954

157

3242

2638

Returns: 2
441796

1372

2370

454

Returns: 4
651367

5807

4010

202

Returns: 7
708288

93

5424

7744

Returns: 2
986052

918

348

2362

Returns: 9
313551

189

7303

1700

Returns: 2
312910

754

6009

461

Returns: 2
194927

397

7279

516

Returns: 2
33210

246

9980

138

Returns: 2
471282

2742

1043

377

Returns: -1
412113

782

2732

649

Returns: -1
15749

18

6472

877

Returns: -1
320828

2090

4618

205

Returns: -1
813199

1900

5808

539

Returns: -1
923549

150

4716

6346

Returns: -1
105293

1526

8551

79

Returns: -1
299879

504

8434

628

Returns: -1
229925

1250

5029

221

Returns: -1
263400

3618

1673

149

Returns: -1
500551

1139

100

1718

Returns: 15
519634

9717

98

548

Returns: 23
684597

4044

7

3682

Returns: 34
334999

9423

231

245

Returns: 31
960860

9966

183

759

Returns: 26
236718

6895

1

2851

Returns: 244
346910

9979

2

2470

Returns: 268
376391

2548

9

2496

Returns: 38
760428

7346

76

1059

Returns: 27
432552

5134

35

1058

Returns: 38
550847

687

21

5004

Returns: 43
952800

6639

6

4844

Returns: 144
904770

2807

12

5093

Returns: 82
850997

4832

54

1429

Returns: 11
154315

674

1

5896

Returns: 56
272141

4269

33

756

Returns: 42
821589

5414

210

848

Returns: 18
855366

3384

5

5286

Returns: 29
386321

9011

1

2614

Returns: 72
506179

2060

75

1401

Returns: 15
95561

9586

1

976

Returns: 297
118901

4026

1

1766

Returns: 109
446778

706

4

8728

Returns: 65
768248

2322

2

7876

Returns: 30
871905

2414

160

1582

Returns: 11
663952

1315

34

3402

Returns: 44
531054

1219

4

7819

Returns: 68
890578

8811

712

409

Returns: 15
135163

6164

8

619

Returns: 118
930726

3364

27

3229

Returns: 62
995064

10000

1

10000

Returns: 794
926842

9075

1

9780

Returns: 899
926841

9075

1

9780

Returns: -1
903429

8486

1

9860

Returns: 920
903428

8486

1

9860

Returns: -1
1000000

3

10000

10000

Returns: 1
1

1

1

2

Returns: -1
1

1

2

1

Returns: 1
1

1

2

2

Returns: -1
1

2

1

1

Returns: -1
1

2

1

2

Returns: -1
1

2

2

1

Returns: -1
1

2

2

2

Returns: -1
2

1

1

2

Returns: 1
2

1

2

1

Returns: 1
2

1

2

2

Returns: 1
2

2

1

1

Returns: 1
2

2

1

2

Returns: -1
2

2

2

1

Returns: 1
2

2

2

2

Returns: -1
8

8

1

2

Returns: 3
2

3

1

2

Returns: -1
1

10

10

10

Returns: -1
2

3

2

1

Returns: -1
11

7

8

2

Returns: 2
99

100

1

1

Returns: 2
10

2

2

10

Returns: -1
9

5

1

4

Returns: 3
5

10

5

1

Returns: -1
2

1

2

3

Returns: -1
100

101

10

3

Returns: 6

Statistics

Problem Statement for "Towers"

Problem Statement

Definition

Notes

Constraints

Examples