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 building (barracks), which constantly produces new soldiers.

Before the attack, you've got myUnits soldiers. In a single round, each soldier can either kill one of your opponent's soldiers or inflict 1 hit point of damage to the barracks.
Your opponent doesn't have any soldiers initially. However, his barracks has barHp hit points and produces unitsPerRound soldiers per round.

The course of one round:
1. Each solider from your army either kills one of your opponent's soldiers or inflicts 1 hit point of damage to the barracks. Each soldier can choose to do something different. When the barracks loses all of its hit points, it is destroyed.
2. Your opponent attacks. He will kill k of your soldiers, where k is the number of remaining soldiers he has.
3. If the barracks are not yet destroyed, your opponent will produce unitsPerRound new soldiers.

Your task is to destroy the barracks and kill all your opponent's soldiers. If it is possible, return the minimum number of rounds you need to do this. Otherwise return -1.

Definition

Class:: Barracks
Method:: attack
Parameters:: int, int, int
Returns:: int
Method signature:: int attack(int myUnits, int barHp, int unitsPerRound)
(be sure your method is public)

Constraints

myUnits, barHp, unitsPerRound will each be between 1 and 5000, inclusive.

Examples

10

11

15

Returns: 4

Round 1: - All your soldiers attack the barracks, leaving it with 1 hit point. - Your opponent has no soldiers, so he cannot kill any of your soldiers. - Your opponent's army increases from 0 soldiers to 15 soldiers. Round 2: - One of your soldiers destroys the barracks. The other nine kill 9 of your opponent's soldiers. - Your opponent has 6 soldiers, so he kills 6 of your soldiers. - The barracks have been destroyed, so no new soldiers are produced. Round 3: - You have got 4 soldiers, so you decrease your opponent's army to 2 soldiers. - Your opponent kills 2 of your soldiers. - The barracks have been destroyed, so no new soldiers are produced. Round 4: - You kill 2 remaining soldiers.
1

2

1

Returns: -1
1

1

1

Returns: 1
25

200

10

Returns: 13
400

400

400

Returns: 1
399

400

400

Returns: 3
250

500

125

Returns: 3
250

500

126

Returns: 4
250

500

187

Returns: 4
250

500

188

Returns: 5
250

500

208

Returns: 5
250

500

209

Returns: 6
250

500

218

Returns: 6
250

500

219

Returns: 7
250

500

225

Returns: 7
250

500

226

Returns: 8
250

500

227

Returns: 8
250

500

228

Returns: 8
250

500

229

Returns: 8
250

500

230

Returns: 8
250

500

231

Returns: 9
250

500

232

Returns: 9
250

500

233

Returns: 9
250

500

234

Returns: 10
250

500

235

Returns: 10
250

500

236

Returns: 11
250

500

237

Returns: 11
250

500

238

Returns: 12
250

500

239

Returns: 13
250

500

240

Returns: 13
250

500

241

Returns: 15
250

500

242

Returns: 16
250

500

243

Returns: 18
250

500

244

Returns: 20
250

500

245

Returns: 23
250

500

246

Returns: 28
250

500

247

Returns: 37
250

500

248

Returns: 53
250

500

249

Returns: 101
250

500

250

Returns: -1
499

500

498

Returns: 2
30

500

15

Returns: 33
30

496

15

Returns: 33
30

495

15

Returns: 32
31

495

15

Returns: 30
1

500

1

Returns: -1
200

450

200

Returns: -1
2

500

1

Returns: 499
3

500

2

Returns: 498
499

500

499

Returns: 3
1

1

2

Returns: 1
1

1

3

Returns: 1
1

2

2

Returns: -1
1

2

3

Returns: -1
1

3

1

Returns: -1
1

3

2

Returns: -1
1

3

3

Returns: -1
2

1

1

Returns: 1
2

1

2

Returns: 1
2

1

3

Returns: 1
2

2

1

Returns: 1
2

2

2

Returns: 1
2

2

3

Returns: 1
2

3

1

Returns: 2
2

3

2

Returns: 3
2

3

3

Returns: -1
3

1

1

Returns: 1
3

1

2

Returns: 1
3

1

3

Returns: 1
3

2

1

Returns: 1
3

2

2

Returns: 1
3

2

3

Returns: 1
3

3

1

Returns: 1
3

3

2

Returns: 1
3

3

3

Returns: 1
212

237

173

Returns: 2
396

125

358

Returns: 1
365

435

368

Returns: 3
88

251

44

Returns: 5
13

240

369

Returns: -1
71

296

40

Returns: 9
403

98

102

Returns: 1
153

493

318

Returns: -1
281

302

257

Returns: 2
366

442

287

Returns: 2
120

445

190

Returns: -1
7

151

7

Returns: -1
6

109

2

Returns: 27
11

8

9

Returns: 1
6

93

10

Returns: -1
13

288

6

Returns: 41
9

427

1

Returns: 54
14

282

6

Returns: 35
7

230

1

Returns: 39
12

173

10

Returns: 80
12

32

5

Returns: 4
14

189

9

Returns: 36
14

432

3

Returns: 39
11

411

5

Returns: 68
15

500

10

Returns: 98
12

486

10

Returns: 236
10

476

8

Returns: 233
14

453

3

Returns: 41
13

105

2

Returns: 10
7

435

5

Returns: 215
8

381

1

Returns: 55
8

271

9

Returns: -1
10

425

9

Returns: 412
10

409

9

Returns: 396
9

288

4

Returns: 57
6

380

5

Returns: 373
13

319

1

Returns: 27
8

101

8

Returns: -1
12

44

6

Returns: 7
8

278

5

Returns: 91
10

331

8

Returns: 160
13

121

10

Returns: 36
7

300

3

Returns: 75
8

178

7

Returns: 168
7

264

3

Returns: 66
6

148

8

Returns: -1
14

471

9

Returns: 92
7

10

8

Returns: 4
10

195

10

Returns: -1
10

311

7

Returns: 101
12

178

9

Returns: 56
12

179

6

Returns: 29
13

151

3

Returns: 15
11

229

4

Returns: 33
6

471

8

Returns: -1
13

81

10

Returns: 23
15

339

10

Returns: 66
14

276

1

Returns: 22
10

198

4

Returns: 33
4

6

7

Returns: -1
8

10

6

Returns: 2
4

5

5

Returns: 3
5

8

5

Returns: 4
6

8

4

Returns: 2
6

8

6

Returns: 3
100

160

101

Returns: 5
300

301

484

Returns: 6
300

301

485

Returns: -1
3

500

2

Returns: 498
3

499

2

Returns: 497
2500

5000

2500

Returns: -1
2500

5000

2499

Returns: 961
3000

5000

3001

Returns: -1
3000

5000

3000

Returns: -1
3000

5000

2999

Returns: 153
3000

5000

2998

Returns: 79
5000

5000

5000

Returns: 1
5000

4999

5000

Returns: 1
5000

4999

4999

Returns: 1
4999

5000

5000

Returns: 3
3819

5000

5000

Returns: -1
3820

5000

5000

Returns: 7
5000

100

5000

Returns: 1
449

4844

448

Returns: 4123
78

4934

77

Returns: 4812
1956

4418

1955

Returns: 1259
755

3976

753

Returns: 1383
366

3561

1

Returns: 10
250

2669

1

Returns: 11
202

4990

2

Returns: 25
149

2600

1

Returns: 18
1661

4327

1107

Returns: 6
1092

2892

950

Returns: 11
1570

3499

1245

Returns: 6
1082

4733

883

Returns: 18
1047

3580

1024

Returns: 86
1148

2275

716

Returns: 4
744

1408

533

Returns: 4
1368

4927

1140

Returns: 15
716

4108

447

Returns: 14
1276

4785

1115

Returns: 20
915

4799

811

Returns: 35
749

1895

577

Returns: 7
1284

2603

1152

Returns: 8
1956

4679

1648

Returns: 8
2335

4365

2035

Returns: 5
2318

4674

2304

Returns: 71
2162

4917

1878

Returns: 8
2575

4876

1861

Returns: 4
2021

3976

1294

Returns: 4
804

3198

692

Returns: 20
2500

5000

1

Returns: 3
2500

5000

1250

Returns: 3
2500

5000

1251

Returns: 4
2500

5000

1875

Returns: 4
2500

5000

1876

Returns: 5
2500

5000

2083

Returns: 5
2500

5000

2084

Returns: 6
2500

5000

2187

Returns: 6
2500

5000

2188

Returns: 7
2500

5000

2250

Returns: 7
2500

5000

2251

Returns: 8
2500

5000

2300

Returns: 8
2500

5000

2301

Returns: 9
2500

5000

2333

Returns: 9
2500

5000

2334

Returns: 10
2500

5000

2495

Returns: 197
1

5000

1

Returns: -1
2

5000

1

Returns: 4999
3

5000

1

Returns: 2500
747

4150

30

Returns: 6
697

4753

19

Returns: 7
747

4328

26

Returns: 6
1000

5000

999

Returns: 3388
2000

4000

1800

Returns: 7
100

5000

97

Returns: 1617
2500

5000

2420

Returns: 16
342

3242

324

Returns: 153
3000

4000

2000

Returns: 2
1600

5000

1599

Returns: 2417
50

5000

1

Returns: 103
499

1233

128

Returns: 3
6

16

5

Returns: 9
3911

4357

2281

Returns: 2
500

5000

333

Returns: 28
900

5000

300

Returns: 8
100

5000

99

Returns: 4843
1000

5000

990

Returns: 343
2000

4000

1999

Returns: 770
2

5000

2

Returns: -1
101

200

100

Returns: 41
8

12

7

Returns: 3
2000

5000

1999

Returns: 1770
5000

5000

100

Returns: 1
10

22

9

Returns: 9
100

199

99

Returns: 42
100

5000

1

Returns: 51
2400

4801

2399

Returns: 924
8

100

7

Returns: 90
3000

5000

100

Returns: 2
24

34

23

Returns: 3

Statistics

Problem Statement for "Barracks"

Problem Statement

Definition

Constraints

Examples