FoxAndAvatar
SRM 594 · 2013-06-25 · by cgy4ever
SRM 594 · 2013-06-25 · by cgy4ever · Dynamic Programming, Greedy
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 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.
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.
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
0)
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.
1)
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.
2)
13 3 8 Returns: 3
3)
54 6 28 Returns: 4
4)
1 1 1 Returns: 0
Submissions are judged against all 315 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FoxAndAvatar with a public method int minimalSteps(int n, int width, int x) · 315 test cases · 2 s / 256 MB per case