3

n個の数値が与えられた場合、次の操作を何度でも実行できます。数値のサブセットを選択します。いずれも0ではありません。サブセット内の数値を1ずつ減らし、サブセット内にない数値をKだけ増やします。

1つを除いてすべて0になるような操作はできますか？

入力：最初の行には、テストケースTの数が含まれています。2* T行が続き、ケースごとに2つです。テストケースの最初の行には、番号nとKが含まれています。次の行には、番号a_1...a_nが含まれています。

出力：各テストケースに対応するTラインを出力します。テストケースの場合、説明されている一連の操作がある場合は「YES」を出力し、そうでない場合は「NO」を出力します。

サンプル入力：

3
2 1
10 10
3 2
1 2 2
3 2
1 2 3

サンプル出力：

YES
YES
NO

制約：

1 <= T <= 1000
2 <= n <= 100
1 <= K <= 10
0 <= a_i <= 1000

私は私の解決策を次のアルゴリズムで受け入れました---

a[i] is value in ith cell
n[i] is number of times it is selected in subset
T is total number of times the operation is done

=> a[i] - n[i] + (T - n[i])*K = 0 for all except 1
=> a[i]= n[i] (K+1) -TK 
=> a[i] = (K+1)(n[i]-T) + T

したがって、余りは、1（ゼロになる）とK + 1で割ったときのTを除いて、すべてのa[i]で同じである必要があります。私の疑問は、この条件が必要であるということですが、それはどのように十分ですか？

4

1 に答える 1

1

ステップ1

次の要素で構成される動きを想像してみてください。

  1. a [i]> = K+1であるすべての数で構成されるサブセットAを選択します
  2. セット全体で構成されるサブセットをK回選択します

サブセットAの数値はK+1倍にデクリメントされますが、セットAの外側の数値は同じままです（Kずつ増加してから、K倍にデクリメントされます）。

すべての数値がK+1未満になるまで、この移動を繰り返します。

このステップでは、K+1を法とする剰余になるように数値を変更します。

ステップ2

ここで、すべての番号が同じであると仮定します（1を除く）。

これで、セット全体で構成されるサブセットを選択できます（奇数のものを除く）。

これにより、すべての数値が1つ減ります（奇数の数値を除く）。完全に0になるまで、この選択を繰り返します。

結論

したがって、すべての数値（1つを除く）の剰余がK + 1を法とする場合、ステップ1を使用してすべてを同じレベルに減らし、次にステップ2を使用して共通レベルを0に下げることができます。

于 2013-02-11T19:17:13.560 に答える