TopCoder Statistics - Problem Statement

Problem Statement

Fox Ciel needs an avatar. In her operating system she has n avatars to choose from. They are numbered from 1 to n.

Whenever her operating system displays a set of avatars, it does so in the following way:

The avatars will be shown in a grid, in a fixed-width window.
The window will always have the room for exactly width columns of avatars.
The number of rows will be the smallest necessary. (If there are X avatars to be displayed, there will be ceil(X/width) rows.)
The avatars are shown ordered by their number, in row major order. That is, in order to look at all the avatars in numerical order, you look at the first row from left to right, then the second row from left to right, and so on.
Note that in the last row some of the rightmost columns may be empty.

The window currently contains all n avatars. Fox Ciel has already decided that she wants the avatar number x. She now needs to delete all the other ones. In a single step, she can select a sub-rectangle of the current window and delete all avatars it contains. (She is allowed to select any rectangle, including one that contains some of the empty cells in the last row of the window.) After each step the remaining avatars are reformatted using the above procedure.

Return the smallest number of steps in which she can achieve her goal.

Definition

Class:: FoxAndAvatar
Method:: minimalSteps
Parameters:: int, int, int
Returns:: int
Method signature:: int minimalSteps(int n, int width, int x)
(be sure your method is public)

Constraints

n will be between 1 and 3,000, inclusive.
width will be between 1 and n, inclusive.
x will be between 1 and n, inclusive.

Examples

3

2

3

Returns: 1

At the beginning these 3 avatars are arranged like this: 12 3 We need only one operation: select avatars #1 and #2 and delete them.
5

2

3

Returns: 2

At the beginning the window looks like: 12 34 5 On optimal solution is as follows. First we delete avatars #2 and #4. The window now looks like: 13 5 And then we delete #1 and #5.
13

3

8

Returns: 3
54

6

28

Returns: 4
1

1

1

Returns: 0
47

6

23

Returns: 3
6

2

4

Returns: 2
8

4

7

Returns: 2
36

4

14

Returns: 4
9

3

8

Returns: 2
7

4

3

Returns: 2
6

3

2

Returns: 3
6

2

3

Returns: 2
13

4

6

Returns: 2
2000

412

1626

Returns: 3
2000

440

1577

Returns: 2
2000

661

1162

Returns: 3
2000

656

1161

Returns: 3
1

1

1

Returns: 0
2

1

2

Returns: 1
3

1

2

Returns: 2
100

100

100

Returns: 1
100

100

99

Returns: 2
100

100

1

Returns: 1
199

100

100

Returns: 1
200

100

100

Returns: 2
1

1

1

Returns: 0
2

1

1

Returns: 1
2

1

2

Returns: 1
2

2

1

Returns: 1
2

2

2

Returns: 1
3

1

1

Returns: 1
3

1

2

Returns: 2
3

1

3

Returns: 1
3

2

1

Returns: 2
3

2

2

Returns: 1
3

2

3

Returns: 1
3

3

1

Returns: 1
3

3

2

Returns: 2
3

3

3

Returns: 1
4

1

1

Returns: 1
4

1

2

Returns: 2
4

1

3

Returns: 2
4

1

4

Returns: 1
4

2

1

Returns: 2
4

2

2

Returns: 2
4

2

3

Returns: 2
4

2

4

Returns: 2
4

3

1

Returns: 2
4

3

2

Returns: 2
4

3

3

Returns: 1
4

3

4

Returns: 1
4

4

1

Returns: 1
4

4

2

Returns: 2
4

4

3

Returns: 2
4

4

4

Returns: 1
5

1

1

Returns: 1
5

1

2

Returns: 2
5

1

3

Returns: 2
5

1

4

Returns: 2
5

1

5

Returns: 1
5

2

1

Returns: 2
5

2

2

Returns: 2
5

2

3

Returns: 2
5

2

4

Returns: 2
5

2

5

Returns: 1
5

3

1

Returns: 2
5

3

2

Returns: 2
5

3

3

Returns: 1
5

3

4

Returns: 2
5

3

5

Returns: 2
5

4

1

Returns: 2
5

4

2

Returns: 2
5

4

3

Returns: 2
5

4

4

Returns: 1
5

4

5

Returns: 1
5

5

1

Returns: 1
5

5

2

Returns: 2
5

5

3

Returns: 2
5

5

4

Returns: 2
5

5

5

Returns: 1
1718

1255

1080

Returns: 2
2303

4

893

Returns: 3
3

1

1

Returns: 1
59

36

1

Returns: 2
2434

3

151

Returns: 3
165

89

31

Returns: 3
5

2

5

Returns: 1
1066

893

23

Returns: 3
1

1

1

Returns: 0
8

4

3

Returns: 2
33

2

24

Returns: 3
774

1

774

Returns: 1
542

1

542

Returns: 1
192

192

127

Returns: 2
1029

63

1029

Returns: 2
2661

293

1875

Returns: 3
75

14

64

Returns: 3
4

4

3

Returns: 2
666

271

19

Returns: 3
70

37

1

Returns: 2
1

1

1

Returns: 0
43

5

36

Returns: 3
800

3

1

Returns: 2
960

3

587

Returns: 3
9

4

7

Returns: 2
7

4

1

Returns: 2
24

21

1

Returns: 2
1478

856

649

Returns: 2
9

3

5

Returns: 3
60

3

1

Returns: 2
9

2

4

Returns: 3
1164

490

572

Returns: 2
5

5

4

Returns: 2
2792

3

1

Returns: 2
25

21

17

Returns: 2
7

5

1

Returns: 2
817

169

1

Returns: 2
14

13

13

Returns: 1
84

12

61

Returns: 3
1037

919

956

Returns: 2
283

113

170

Returns: 3
708

42

519

Returns: 3
754

141

395

Returns: 3
97

4

58

Returns: 4
813

63

91

Returns: 3
17

16

8

Returns: 2
79

48

44

Returns: 2
135

1

47

Returns: 2
1266

1226

1

Returns: 2
780

1

1

Returns: 1
2934

573

1885

Returns: 3
481

317

1

Returns: 2
31

24

5

Returns: 2
83

5

66

Returns: 3
1823

1

253

Returns: 2
3

1

3

Returns: 1
1811

485

843

Returns: 3
7

7

7

Returns: 1
1448

3

1

Returns: 2
7

7

2

Returns: 2
1213

405

1213

Returns: 2
2508

4

2107

Returns: 3
887

291

329

Returns: 3
28

4

8

Returns: 3
359

275

312

Returns: 2
22

1

22

Returns: 1
9

5

3

Returns: 2
27

11

18

Returns: 2
759

4

316

Returns: 3
506

3

506

Returns: 2
1839

815

944

Returns: 2
963

573

685

Returns: 2
521

266

449

Returns: 2
118

5

4

Returns: 3
4

3

4

Returns: 1
853

191

325

Returns: 3
44

42

24

Returns: 2
5

5

5

Returns: 1
28

16

14

Returns: 2
349

1

55

Returns: 2
2

1

1

Returns: 1
4

3

1

Returns: 2
45

15

14

Returns: 2
1

1

1

Returns: 0
342

200

175

Returns: 2
45

2

44

Returns: 2
672

85

672

Returns: 2
156

140

45

Returns: 2
9

2

6

Returns: 3
2683

233

56

Returns: 3
7

7

2

Returns: 2
8

4

2

Returns: 3
400

278

272

Returns: 2
1042

2

624

Returns: 3
369

368

283

Returns: 2
77

28

17

Returns: 3
316

54

316

Returns: 2
1

1

1

Returns: 0
345

168

302

Returns: 2
853

809

766

Returns: 2
2971

496

1207

Returns: 3
2958

2643

735

Returns: 2
2919

732

2292

Returns: 2
2938

685

1728

Returns: 3
2913

1736

2549

Returns: 2
2961

2139

1782

Returns: 2
2930

1147

2136

Returns: 2
2927

1508

1604

Returns: 2
2952

2424

1936

Returns: 2
2996

2582

864

Returns: 2
2949

1747

1264

Returns: 2
2907

2559

189

Returns: 2
2963

2205

1101

Returns: 2
2934

301

1431

Returns: 3
2906

2365

2413

Returns: 2
2914

613

1277

Returns: 3
2984

440

93

Returns: 3
2935

2667

2021

Returns: 2
2903

2464

1664

Returns: 2
2958

2929

2941

Returns: 2
3000

1252

1439

Returns: 2
2937

497

878

Returns: 3
2915

2649

2338

Returns: 2
2942

863

548

Returns: 3
2994

1695

471

Returns: 3
2930

2761

1441

Returns: 2
2984

1725

1273

Returns: 2
2927

1511

608

Returns: 3
2930

2155

1011

Returns: 2
2984

2469

998

Returns: 2
2932

19

208

Returns: 4
2924

52

1124

Returns: 4
2804

22

1304

Returns: 4
2285

22

1846

Returns: 4
952

9

402

Returns: 4
2616

30

445

Returns: 4
2202

27

533

Returns: 4
1452

27

585

Returns: 4
1148

27

256

Returns: 4
801

12

368

Returns: 4
2722

9

1563

Returns: 4
1685

4

1402

Returns: 4
462

6

416

Returns: 4
1888

53

340

Returns: 4
1950

9

663

Returns: 4
407

10

176

Returns: 4
1278

15

309

Returns: 4
1724

38

215

Returns: 4
2734

16

2472

Returns: 4
1729

21

1404

Returns: 4
1432

49

167

Returns: 4
780

15

530

Returns: 4
1526

42

286

Returns: 4
2497

68

716

Returns: 4
2736

64

522

Returns: 4
1946

43

492

Returns: 4
639

10

308

Returns: 4
1681

51

498

Returns: 4
721

38

211

Returns: 4
1195

20

108

Returns: 4
2642

20

186

Returns: 4
619

20

213

Returns: 4
1594

18

524

Returns: 4
1233

9

894

Returns: 4
2772

60

635

Returns: 4
2552

35

509

Returns: 4
1545

6

195

Returns: 4
2716

32

117

Returns: 4
794

6

742

Returns: 4
1363

45

334

Returns: 4
2503

28

623

Returns: 4
2503

67

300

Returns: 4
1356

10

954

Returns: 4
2853

108

809

Returns: 4
1138

39

331

Returns: 4
2397

39

960

Returns: 4
2031

34

828

Returns: 4
1229

23

377

Returns: 4
2620

15

1557

Returns: 4
2816

41

310

Returns: 4
2057

26

1004

Returns: 4
2320

80

674

Returns: 4
1966

44

281

Returns: 4
2892

34

590

Returns: 4
2636

34

255

Returns: 4
2160

36

653

Returns: 4
669

28

160

Returns: 4
2795

18

2094

Returns: 4
1543

12

1074

Returns: 4
2206

24

1821

Returns: 4
2456

29

190

Returns: 4
2003

42

229

Returns: 4
2674

87

564

Returns: 4
1798

20

834

Returns: 4
2074

65

606

Returns: 4
1266

36

192

Returns: 4
2986

43

1268

Returns: 4
2395

42

1030

Returns: 4
1703

40

457

Returns: 4
2907

15

417

Returns: 4
2814

12

1444

Returns: 4
2158

21

1035

Returns: 4
1937

30

140

Returns: 4
1150

4

714

Returns: 4
2963

26

2872

Returns: 4
2972

90

467

Returns: 4
2551

85

807

Returns: 4
2179

49

321

Returns: 4
2754

4

2522

Returns: 4
2435

15

1266

Returns: 4
2397

15

1806

Returns: 4
1525

14

160

Returns: 4
2596

60

387

Returns: 4
2344

39

522

Returns: 4
978

39

165

Returns: 4
2483

54

308

Returns: 4
2209

33

155

Returns: 4
2654

64

151

Returns: 4
2023

18

79

Returns: 4
861

33

239

Returns: 4
1292

34

911

Returns: 4
2792

38

562

Returns: 4
2849

60

501

Returns: 4
2868

35

585

Returns: 4
1436

65

371

Returns: 4
1653

43

480

Returns: 4
1281

18

640

Returns: 4
1500

20

253

Returns: 4
2227

6

842

Returns: 4
2035

26

228

Returns: 4
3000

7

16

Returns: 3
3000

7

16

Returns: 3
79

12

48

Returns: 2
14

8

13

Returns: 2

Statistics

Problem Statement for "FoxAndAvatar"

Problem Statement

Definition

Constraints

Examples