There are n bushes in a row conveniently labelled 1 to n in IOI Kingdom, each of them can either contain a ninja (or not). Also, potato knows that there are k ninjas in these n bushes.
Potato wants to invade IOI kingdom and get some gold. He may call upon some royal potato guards one by one to check out the bushes. Potato can command a royal potato guard to count the number of ninjas in a range starting from bush 1, then the next guard, until he can decide the positions of the ninjas.
Potato wants to minimize the number of royal potato guards he needs to call upon to guarantee that he can find the ninjas. However, potato realizes this is a non-trivial problem! He asks you for help in order to reduce the number of royal guards he needs to command.
void Potate(int n, int k) will be called. n, k indicates the number of bushes and ninjas respectively. This function should find the position of all ninjas.
You may use the following functions:
- int Guard(int x): returns the number of ninjas in bushes 1 to x inclusive.
- void Ninja(int x): indicates that there is a ninja at bush x. You have to call this function exactly once for each ninja.
Subtask 1 (16 points): 1 ≤ k ≤ n ≤ 30
Subtask 2 (22 points): 1 ≤ k ≤ n ≤ 90
Subtask 3 (42 points): 1 ≤ k ≤ n ≤ 400
Subtask 4 (20 points): 1 ≤ k ≤ 50000, n ≤ 1000000000, 1 ≤ k ≤ n