UVa 12973 - Drinking Game

Source

Regional WarmUp（20151024）
(Competitive Programming Network - Eleventh Activity - 2015, Premio Fase II México & Centroamérica The ACM-ICPC in ESCOM-IPN 2015)
UVa 12973

問題概要

$N$ 個の正整数 $G_1,G_2,\ldots,G_N$ が与えられる．
$1$ 回の操作では，これらの整数の中から $1$ つ選び，$1$ だけ増やすか，$1$ だけ減らすことができる．
ただし，$0$ 以下にしては行けない．
最終的に，全ての整数が互いに素，つまり，${\rm GCD}(G_i,G_j) = 1, \quad 1 \leq i < j \leq N$ を満たすようにしたい．
最小の操作回数で達成できる状態を $1$ つを求める問題．

テストケースの数 $T$ に対する制約はない
$1 \leq N \leq 100$
$1 \leq G_k \leq 20$

解法

まず，$G_k$ を $1$ にしてしまえば，他のものと互いに素になることは保証される．
よって，$40$ 以上に増やす必要はなく，そうするぐらいなら $1$ にしてしまえば良い．
また，$G_i \lt; G_j$ なら最終状態でも $G_i \leq G_j$ であるべき．
なので，まずは，$G_i$ をソートして，$G_i \leq G_{i+1}$ を常に満たすと仮定しておく．
（状態を復元しないといけないので，何がどこにあったかは覚えておく）
そうすると最終状態というのは，$2$ 以上 $40$ 以下の互いに素な整数をいくつか選び，残りを $1$ で補うパターン数ぐらいしかない．
実際に，それを列挙してみると，数十万パターンであり，それらを全部試すことが可能．
よくよく考えると，$38$，$39$ も使う必要なく，それを使うぐらいなら $14$，$13$ を使えば良い．

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります．

Current time: 2024年04月19日07時31分57秒
Last modified: 2015年11月02日15時20分40秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20151024_1
トップページに戻る

Logged in as: unknown user (not login)