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$ つを求める問題.

解法

まず,$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: 2017年11月19日12時16分59秒
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)

ログイン: