codeforces Round #259(div2) D問題解決レポート_html/css_WEB-ITnose

D. リトルポニーとハーモニーチェスト

テストごとの制限時間

4 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

トワイライト姫は、ハーモニーの要素からチェストを調査するためにセレスティアとルナの古城に行きました。

正の整数のシーケンス bi は、シーケンスの 2 つの要素ごとに最大公約数が 1 に等しい場合に限り、ハーモニーとなります。古代の本、チェストのキーは次の式を最小化するハーモニー シーケンス bi です:

あなたにはシーケンス AI が与えられています。トワイライト姫が鍵を見つけるのを手伝ってください。

入力

最初の行には整数 n が含まれています( 1?≤?n?≤?100) ?シーケンスaとbの要素の数。次の行には、n integersa1,?a2,?...,?an (1?≤?ai?≤?30) が含まれています。

Output

Output the key ?上記の合計を最小化するシーケンス bi 。最適なシーケンスが複数ある場合は、そのいずれかを出力できます。

サンプル テスト

入力

51 1 1 1 1

出力

1 1 1 1 1 

入力

51 6 4 2 8

出力

1 5 3 1 8 

題目大意:

出N個数ai、求出另一順序列bi、要求sum |ai-bi|、最小、およびすべてのbi都相互。

这里题眼给了几个很眼的条件，ai 制限在了 1 〜 30 間，故に可及的制限 1 この数，那么|ai-bi| 最大就是29了，意味bi はすべての双分解を要求し、すべての双分解で得られるパラメータの数がすべて異なるように変更できます。

は、これらの数値を使用して現在のフェーズの状態を示します。たとえば、 s = 3 = 11 は、現在の状態を表します。

很快我们就は状態遷移手順を書き出すことができます:

f[i][s] = min(f[i-1][s^c[k]] + abs(a[i ] - k))。 この中の c[k] は数字 k が使用したものを示します。