FoxAndAvatar | Topcoder Archive

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
```

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.