CF 453B(Little Pony and Harmony Chest-數列最小加減1更改方案,滿足任意2數互質-位運算dp+最壞情況分析+記憶化搜索)

B. Little Pony and Harmony Chest time limit per test 4 seconds memory limit per test 256 megabytes input standard input output standard output

Princess Twilight went to Celestia and Luna's old castle to research the chest from the Elements of Harmony.

A sequence of pZ喎?/kf/ware/vc/" target="_blank" class="keylink">vc2l0aXZlIGludGVnZXJzIDxlbT5iPC9lbT48ZW0+aTwvZW0+IGlzCiBoYXJtb255IGlmIGFuZCBvbmx5IGlmIGZvciBldmVyeSB0d28gZWxlbWVudHMgb2YgdGhlIHNlcXVlbmNlIHRoZWlyIGdyZWF0ZXN0IGNvbW1vbiBkaXZpc29yIGVxdWFscyAxLiBBY2NvcmRpbmcgdG8gYW4gYW5jaWVudCBib29rLCB0aGUga2V5IG9mIHRoZSBjaGVzdCBpcyBhIGhhcm1vbnkgc2VxdWVuY2UgPGVtPmI8L2VtPjxlbT5pPC9lbT4gd2hpY2gKIG1pbmltaXplcyB0aGUgZm9sbG93aW5nIGV4cHJlc3Npb246PC9wPgo8Y2VudGVyIGNsYXNzPQ=="tex-equation">

You are given sequence ai, help Princess Twilight to find the key.

Input

The first line contains an integer n (1?≤?n?≤?100) — the number of elements of the sequences a and b. The next line contains n integersa1,?a2,?...,?an (1?≤?ai?≤?30).

Output

Output the key — sequence bi that minimizes the sum described above. If there are multiple optimal sequences, you can output any of them.

Sample test(s) input

5
1 1 1 1 1

output

1 1 1 1 1 

input

5
1 6 4 2 8

output

1 5 3 1 8 

假想把數列改成1，1，1... 1 滿足題意

因此我們對於數列中任意1個數，只要尋找比改成1更優的策略

由於ai≤30，bi≤30+29=59,因此涉及的質數≤59

故可用記憶化搜索+位運算Dp求解

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Lson (x<<1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define MAXN (100+10)
#define MAXAi (30)
#define MAXBi (59)
long long mul(long long a,long long b){return (a*b)%F;}
long long add(long long a,long long b){return (a+b)%F;}
long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;}
typedef long long ll;
int n,a[MAXN],prime[16] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
int dp[1<<16][MAXN],divv[MAXN];
int dfs(int mask,int siz)
{
	if (siz==n+1) return 0;
	int &ret=dp[mask][siz];
	if (ret!=-1) return ret;ret=INF;
	For(i,2*a[siz]-1)
	{
		if (mask&divv[i]) continue;
		ret=min(ret,dfs(mask|divv[i],siz+1)+abs(i-a[siz]));
	}
	return ret;
}
int ans[MAXN];
void find(int mask,int siz)
{
	if (siz==n+1) return ;
	int ret=dp[mask][siz];
	For(i,2*a[siz]-1)
	{
		if (mask&divv[i]) continue;
		if (ret==dfs(mask|divv[i],siz+1)+abs(i-a[siz])) 
		{
			ans[siz]=i;
			find(mask|divv[i],siz+1);
			return;
		}
	}
}
int main()
{
//	freopen("Harmony Chest.in","r",stdin);
//	freopen(".out","w",stdout);
	scanf("%d",&n);
	For(i,n) scanf("%d",&a[i]);
	dfs(0,1);
	MEM(divv)
	memset(dp,-1,sizeof dp);
	For(i,MAXBi)
		Rep(j,16)
		{
			if (i%prime[j]==0) divv[i]|=1<