i just used a simple recursion to solve B:

def solve(r, ub):
	if x/r > ub:
		return ub
	return c/r + solve(r+f, x/r-c/r)

print solve(2, x/2)

here, r is the current rate of generation of cookies and ub is the upper bound of what the function can return (returning anything above that is useless because answer can be reduced by not buying more farms).

I solved it using the same idea , no need for ternary search

my approach was to find the solution in the form of at most 3 connected rectangles X × Y, X₁ × 1, 1 × Y₁ such that X·Y + X₁ + Y₁ = R·C - M ,

where X₁ ≤ X, Y₁ ≤ Y and (X, X₁, Y, Y₁) ≠ 1.

Example:

4 4 3

X = 3; Y = 3; X1 = 2; Y1 = 2

BB**
AAA*
AAAC
AAAC

If R = 1 or C = 1, it's clear that we can just make the last M cells contain mines.

Next, there's a special case of M = RC - 1; if M < RC - 1, the field we click on mustn't neighbor mines.

You can always get +1 free space (without mines) by cutting off concave corners (a mine neighboring 3 free spaces). By doing so, you get a rectangle a × b from f connected free cells, eventually — that means you can get any number of free cells from f to ab.

The smallest f (that you could get a given a × b rectangle from) is clearly achieved by making a path 2 cells thick along 2 sides of the field and next to a corner, and it's f = 2a + 2b - 4, so it suffices to find some a, b such that 2(a + b - 2) ≤ RC - M ≤ ab, cut off that space next to a corner (a - 1 and b - 1 cells not neighboring any others, along a vertical and a horizontal side) and then remove mines from as many cells from that a × b rectangle as necessary. Example:

R C M
4 5 9

for example x = 3, y = 4

....*
....*
..***
*****

and remove 1 more mine

....*
....*
...**
*****

My solution:

1) R = 1 or C = 1 or M = R·C - 1 as Xellos described.

2) Try to fill the rectangle (r - 2) × (c - 2) ([0..r - 3] × [0..c - 3]) line by line (fill the the row 0 and all cells [0..c - 3] then the row 1 and etc.).

3) If you have no remained mines, then you are done.

4) If the number of remained mines is odd then we try to steal the mine at (r - 3, c - 3) and now the number of remained mines is even.

5) Now we consider all the rows and columns which have 2 free cells. And fill them by putting 2 mines into those rows and columns.

If at the end we have remained mines or we couldn't steal mine at step 4 when we need it, then it's Impossible.

My solution:

1. R = 1 or C = 1 or M = R C — 1 as Xellos described.
2. M = 0
3. (R = 2 or C = 2) and M % 2 == 1 and M != R C — 1 -> Impossible
4. Let's count free cells, not mines. So, we need RC — M cells. Let's click in a corner. Now we have 4 revealed cells. Then recursively try open new cells while count of revealed is less than needed. Less words, more code:

void dfs(i, j, current_field, revealed)
     if revealed == M - RC
           answer <- current_field
     temp <- count of closed adjacent cells
     if temp == 0 or revealed + temp > M - RC
           return
     current_field <- current_field with revealed adjacent cells
     for dx : -1..1
           for dy : -1..1
                  dfs(i + dx, j + dy, current_field, revealed + temp)

When I was coding it, I thought that it's bruteforce and works very slow. But execution time of 134 large tests was about 1 second.

But I can't prove the fact that if solution exists, we can find it, clicking in a corner

My approach. Place bombs to the cells at the shorter side of the remaining rectangle. The only corner case is if number of remaining bombs equal to the (shorter_side_size — 1). In this case we have to place (shorter_side_size — 2) bombs for this side and leave 1 bomb to next iteration.

Example:
5 rows 7 columns 28 bombs
Step 1. Place 5 bomb to 1 column. (remaining rectangle after this step 5x6)
Step 2. Place 5 bomb to 2 column. (remaining rectangle after this step 5x5)
Step 3. Place 5 bomb to 3 column. (remaining rectangle after this step 4x5)
Step 4. Place 5 bomb to 1 row. (remaining rectangle after this step 4x4)
Step 5. Place 4 bomb to 4 column. (remaining rectangle after this step 3x4)
Step 6. Place 4 bomb to 2 row. (remaining rectangle after this step 3x3)
Done.

If Naomy gives 4 but says that he gives any block with mass > 10, Ken will think that he must play the smallest possible block because he loses anyway. Then he will give 2 and Naomi will win since 4 > 2 .

Basically, Naomi can make Ken play the blocks in the order that's the most advantageous for her.

She could pick her lightest i blocks, make each of them just a little bit lighter than each of Ken's heaviest i blocks, and thus make him play these blocks (scoring i points). Then, she could pick her N - i heaviest blocks, play them from lightest to heaviest, which will make Ken play his N - i lightest blocks also from lightest to heaviest, making Naomi score N - i points. (Of course, this strategy doesn't have to be possible for some i, but it can be shown that if it isn't, then the answer isn't N - i.)

Sorted blocks:

['0.186', '0.300', '0.389', '0.557', '0.832', '0.899', '0.907', '0.959', '0.992']

['0.215', '0.271', '0.341', '0.458', '0.520', '0.521', '0.700', '0.728', '0.916']

Firstly, take Naomi's blocks which are less than Ken's ones. In our case — 0.186. Naomi know that she won't win this point, but she does not say the real value, because she wants to destroy the heaviest possible Ken's block — 0.916. For example, she can say 0.915, but the value does not matter in this problem. Ken get 1 point, but lose the biggest block.

Secondly, take the next Naomi's block — 0.300. Note there is Ken's block that are less that Naomi's one — 0.215. Naomi says the value which is heavier that all of Ken's values — 0.729 (again, exact value does not matter). Ken see that he won't win this point, so he wants to lose the smallest block — 0.215. 0.215 < 0.300 — this point goes to Naomi. The next pair will be 0.389 > 0.271 and so on. The last pair will be 0.992 > 0.728. 8 pairs — 8 points.

because ternary search in B was superfluous

I thought i could hack that code with T=230 and for each R=5 C=5 M=22 ( Should Check 2^25 permutation for each 230 testcases ).

Also we could do Memorization, But with precomputing i could trust my code will output less than 1 second.

And also precomputing helps me finding bugs in my two wrong submissions ;)