freaks_geeks's blog

By freaks_geeks, history, 3 weeks ago, In English

I tried this problem (1366/A) a lot and still, I'm doing wrong something in it. Are there some hints for this problem?

I don't get what should I give priority for sticks or shovel. The only condition when I'm facing an error is - when a < b < 2*a where a is number of limiting item.

I tried using binary search to find the midpoint of weightage or something like that but still no solution. Maybe I'm implementing incorrect logic. Is there anything I'm missing? I've tried this problem for a whole day now! Any help/hint would be greatly appreciated.


Problem — CodeforcesShovels and Swords

Binary Search — Python PoolBinary Search

  • Vote: I like it
  • 0
  • Vote: I do not like it

3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by freaks_geeks (previous revision, new revision, compare).

3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Assume that the number of shovels and the number of swords made are non-negative integers $$$x$$$ and $$$y$$$, respectively. The problem can be modeled as the following integer programming problem.

$$$\max z = x+y$$$

subject to

$$$2x + y \le a$$$

$$$x + 2y \le b$$$

where $$$x,y \ge 0$$$

It can be shown the solution is $$$\min(\lfloor\frac{a+b}{3}\rfloor,a,b)$$$

Complexity: $$$O(1)$$$