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

Автор -emli-, история, 6 лет назад, По-английски

How to solve D?

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

What a interesting problem that is.

Spoiler
»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

If you have odd number in a[i][j], transfer 1 to a[i+1][j] or a[i][j+1], whichever is eligible

Just do this for each i <= n & j <= m, where n and m are dimensions of the matrix

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    stefdasca How your idea will work to this test?

    3 3

    2 3 2

    2 2 2

    2 2 3

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      That 1 from (1,2) will go to (2,2), (3,2) and (3,3), where it will be added to a[3][3] which is 3, therefore making all matrix full with even elements

      The thing is that if sum of elements in a matrix is even, we can make it have just even elements by doing this strategy, because eventually, all 1's resulting from odd numbers will end up in some other square, situated in a bigger line and bigger column

      If sum of elements is odd, we can do the same strategy too, but we will have exactly one odd element, because odd sum can't be formed by only even elements

      I was at today's ABC, and i got AC on first try, using this idea

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

why adding all the non-zero numbers and put it to any one cell (let's say, the bottom right (h,w)) doesn't work? with this any odd number will paired with another odd number and make it even, and even+even still even, so the number of even number will be all cell (because we make all 0 except cell (h,w)) plus -1 if cell (h,w) is odd

give counter example pls, i cant find any..

EDIT: misread the problem, changed above algo to move one coin from all cell with odd number of coins to any one cell (mine to (h,w)) is accepted

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

    You can move only one coin in a single operation. Moving two or more coins from the same cell is forbidden.