TopCoder SRM 594 - 950: FoxAndAvatar

Problem Statement

给你一个宽度为w，无限高的方格。
将1到n从方格第一行第一格从左到右，从上到下依次填入。
现在每次删除一个矩形内的数字(矩形可以包括没有数字的方格)，
将剩下的数字按照原来的方式从小到大填入。
问最小几步操作，可以使数字只剩下x？

数据范围：(n<=3000, x,w<=n).

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)

Limits

Time limit (s) 2.000
Memory limit (MB) 64

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.

Test cases

input
- n 3
- width 2
- x 3
output
Returns 1
note
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.
input
- n 5
- width 2
- x 3
output
Returns 2
note
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.
input
- n 13
- width 3
- x 8
output
Returns 3
input
- n 54
- width 6
- x 28
output
Returns 4
input
- n 1
- width 1
- x 1
output
Returns 0

back to the menu

SRM 594 1 950 FoxAndAvatar

Problem Statement

Definition

Limits

Constraints

Test cases