ZIO 2013：人形

Question

あなたのお店では、いくつかの種類の人形が販売されています。各人形は、提示価格を持っており、 人形の2つのタイプは同じ価格を持っていません。異なるタイプの人形ができるだけ価格が異なるように、 各人形の実際の販売価格を修正したいと思います。原因 いくつかの政府の規制に、あなただけの提案価格がpであれば、あなたは範囲{P-K、P内の任意の販売価格 を選ぶことができ、±K-内の他の単語の固定 帯域内希望価格を変更することができます - K + 1 ,. 。 。 、p + K-1、p + K}である。もちろん、販売価格は必ず でなければなりません。たとえば、あなたが 価格に150、210、50を調整することができ、提案価格は130と人形の4種類、210、70 および90、あなたはその後、20の帯域内の価格を変更することが許可されているがあるとし と人形の任意の2種類の価格 の最小差が50になるように、100は、それぞれ、あなたはこれが最大の分離であることを確認することができます（第2人形のために、あなたは200と230との間の任意 価格を選んだ可能性が）そのあなたは 与えられた制約を達成することができます。以下の例それぞれで

、あなたは価格の順序とあなたはあなたが変更することが許可されている場合は、 シーケンス内のすべてのペア間で達成できる最大の分離を決定する必要があり Kの値を与えています各価格は±Kまでです。

（a）は、K = 13配列：144、152、214、72、256、3、39、117、238、280
（b）は、K = 10配列：10、48 = 20配列、57、32、61、74、33、45、99、81、19、24、101
（C）K：10、19、154、67、83、39、54、110、 124、99、139、170

だから基本的に、私はちょうどをコーディングすることなく、最大の分離の値を見つける必要があります。私はアルゴリズムを考案しようとしましたが、悲惨に失敗しましたので、基本的に各値を一定の値だけ増減することにより、それを強制的に強制的に開始しましたが、ここで適用されるブルートフォースは、Kの値によって、任意のK < 6）には簡単でした。

誰かがそれを計算するための関数や漸化式を定義することはできますか？ソリューションはオンライン上にありますが、解答は整数としてのみ提供され、ソリューションに到達する方法は説明しません。私はプログラミングの初心者ですので、C++の擬似コード/少し使って説明してください。ありがとうございました。

出典：http://www.iarcs.org.in/inoi/2013/zio2013/zio2013-qpaper.pdf ソリューション：http://www.iarcs.org.in/inoi/2013/zio2013/zio2013-solutions.pdf

Answer 1

ここでは、O（nlogn）アルゴリズムです。 K = 10

1. 並べ替え、10、48、57、32、61、74、33、45、99、81、19、24、101：私は第二の例を使用する例示する

   リスト（10、19、24、32、33、45、48、57、61、74、81、99、101）

2. 使用二分の試行値について

X最小分離を見つけますxの条件を満たすように、最終値をできるだけ小さく配置します（負ではない、元の値のK以内、少なくともxは前の値より大きい）。

x = 10から始めましょう。 次のように我々は移動する：

1. 10-> 0（負行くことができないので、これは最小許容される）
2. 19-> 10（前回値のK = 10内で行くことができません）
3. 24> 20
4. 32> 30
5. 33-> 40
6. 45-> 50
7. 48不可能となります。 38と58の間の値しか割り当てることはできませんが、これらの値は前の50から10以上離れていません。

x = 10は分離が高すぎると判断し、低く移動する必要があります。 （値のみに移動することができます

1. 10-> 0
2. 19 - > 9： あなたは、x = 9は、x = 8を試行し、それが不可能である見つける、X = 7を試してみて、それが可能であるかもしれません9-> 29）
3. 24> 17
4. 32> 25
5. 33-> 33
6. 45-> 41
7. 48-> 49
8. 57-> 56
我々は、x = 8であることを見出した
9. 61-> 64
10. 74-> 72
11. 81-> 80
12. 99-> 89
13. 101-> 97

だから可能な場合、x = 9は不可能であり、従ってx = 8は可能な最大分離である。