在YYHS有一种奇异的汉诺塔，在汉诺塔中存放的圆盘式上大下小的，且在同一塔上的相邻两个圆盘大小之和，恰为一个质数，现有N根汉诺塔，问最多能将大小从1开始连续的圆盘放入这N个汉诺塔中。注意放入的顺序必须是从1~N。

输入格式

输出格式

样例输入1

2

样例输出1

7样例解释：43  72  61  5

各个测试点1s

 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=2005; 4 int map[maxn][maxn]; 5 int match[maxn]; 6 bool prime[maxn]; 7 bool vis[maxn]; 8 int n;int ggg; 9 inline bool ok(int x)10 {11     for(int i=2;i<=sqrt(x+0.5);i++)12     if(x%i==0)return false;13     return true;14 }15 inline void gg()16 {17     scanf("%d",&n);18     for(int i=2;i<=2000;i++)19     if(ok(i))prime[i]=true;20     return ;21 }22 bool dfs(int x)23 {24     for(int i=x+1;i<=ggg;i++)25     {26         if(prime[x+i]==true&&vis[i]==false)27         {28             vis[i]=true;29             if(match[i]==-1||dfs(match[i]))30             {31                 match[i]=x;32                 return true;33             }34         }35     }36     return false;37 }38 inline int hungary(int x)39 {40     int count=0;ggg=x;41     memset(match,-1,sizeof(match));42     for(int i=1;i<=x;i++)43     {44         memset(vis,false,sizeof(vis));45         if(dfs(i))count++;46     }47     return count;48 }49 int main()50 {51      gg();52     int left=1,right=2000;53     while(left<=right)54     {55         int mid=(left+right)>>1;56         if(mid-hungary(mid)<=n)left=mid+1;57         else right=mid-1;58     }59     printf("%d",right);60     return 0;61 }