Блог пользователя Rock2000

Автор Rock2000, 4 года назад, По-английски

I was solving this problem. I solved it with my intuition and the solution I thought was also given in the editorial. But I couldn't find proof of this solution anywhere. Can anyone please give me proof for the solution of this problem. Thanks in advance.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Consider any sequence of less then $$$n + \left[\frac{n}{2}\right]$$$ moves. Then there will be more then $$$\left\lceil\frac{n}{2}\right\rceil$$$ cells that are used no more than 1 time (Dirichlet principle). This means that there will be a pair of consecutive cells that are used no more than 1 time. Now consider a tank in the cell which is being bombed later. If this tank moves to the other cell, it wont be hit for the second time.