Given an N x M matrix having only positive integer values, we have to nullify the matrix
i.e make all entries 0.
We are given two operations
1) multiply each element of any one column at a time by 2.
2) Subtract 1 from all elements of any one row at a time
Find the minimum number of operations required to nullify the matrix.
LCMに関連することを考えましたが、解決策に到達できませんでした
最初に 1 行を解決してみましょう。これをすべての行に拡張できます。ランダムな例を見てみましょう:
6 11 5 13
目標は、すべての要素を 1 にすることです。まず、5 (最小要素) を 1 にします。このためには、4 を引く必要があります (つまり、1 を 4 回引く)。結果の配列は次のとおりです。
2 7 1 9
ここで、1 を 2 で乗算し、すべての行要素を 1 で減算します。
1 6 1 8
次に、2 つの 1 を 2 で乗算し、すべての行要素を 1 で減算します。
1 5 1 7
このように続けると、 に到達し1 1 1 1ます。ここで 1 を引いて を取得します0 0 0 0。
次に、他の行に移動して、上記と同じことを行います。上記で無効化した行はすべてゼロであるため、他の行を操作するときに 2 を乗算しても、既に無効化された行は変更されません。
操作の最小数を見つける問題は、選択する行シーケンスにも依存します。最初に（他の行の中で）最大が最小の行を選択することだと思います。これを確認する必要があります。