蓝桥杯官网练习系统题解(非VIP)

#include<cstdio>
int main()
{
    int a,b;//-10000 <= A, B <= 10000
    scanf("%d%d",&a,&b);//scanf(),printf()的int型输入输出
    printf("%d\n",a+b);
    return 0;
}

#include<cstdio>
int main()
{
    long long n,sum;//n<=1000000000,int不够，需用long long 
    scanf("%I64d",&n);//scanf(),printf()的long long型输入输出,还有一种情况是"%lld"
    printf("%I64d\n",n*(n+1)/2);//等差数列求和 
    return 0;
}

#include<cstdio>
const double PI=3.1415926535897932;
int main()
{
    double r;//虽说输入是一个整数，但后面都是要转换成实数的
    scanf("%lf",&r);//scanf(),printf()的double型输入输出
    printf("%.7lf\n",PI*r*r);
    return 0;
}

/*
    (1 1) * (Fn-1) = ( Fn )//矩阵相乘，将就着看吧
    (1 0)   (Fn-2)   (Fn-1)

    (1 1) * (1 1) * (Fn-2) = ( Fn )
    (1 0)   (1 0)   (Fn-3)   (Fn-1)

    F1=1,F0=0...

    (1 1) * ... * (1 1) * (1) = ( Fn )//共n-1个(1 1)
    (1 0)         (1 0)   (0)   (Fn-1)         (1 0)
*/ 
#include<cstdio>
const int Mod=10007;
int Z[2][2];
void Matrix_Multiply(int X[][2],int Y[][2]){
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            Z[i][j]=0;
            for(int k=0;k<2;k++)
                Z[i][j]+=X[i][k]*Y[k][j];
        }
    }
}
void Matrix_Copy(int *C){
    for(int i=0;i<2*2;i++)
        C[i]=Z[i/2][i%2]%Mod;
}
int Fast(int n){//快速求幂
    int B[2][2]={1,0,0,1,},A[2][2]={1,1,1,0};//B为单位矩阵
    while(n){
        if(n&1){
            Matrix_Multiply(B,A);
            Matrix_Copy(&B[0][0]);
        }
        n>>=1;
        Matrix_Multiply(A,A);
        Matrix_Copy(&A[0][0]);
    }
    return B[0][0];//B[0][0]*f1+B[0][1]*f0 (f1=1,f0=0)
}
int main()
{
    int n;
    scanf("%d",&n);
    n=(n-1)%20016+1;//实验发现循环节为20016，其实在使用快速幂的情况下这个优化快不了多少
    printf("%d\n",Fast(n-1));
    return 0;
}

#include<cstdio>
bool Is(int y){
    if(y%4)return false;
    if(y%100)return true;
    if(y%400)return false;
    return true;
}
int main()
{
    int y;
    scanf("%d",&y);
    printf("%s\n",Is(y)?"yes":"no");
    return 0;
}

#include<cstdio>
#define MAXN 5
int ans[MAXN];
void Print_ans(int k){
    for(int i=0;i<k;i++)printf("%d",ans[i]);printf("\n");
}
void Set_01(int k){
    if(k==MAXN){
        Print_ans(k);
        return;
    }
    for(int i=0;i<2;i++){
        ans[k]=i;
        Set_01(k+1);
    }
}
int main()
{
    Set_01(0);
    return 0;
}

#include<cstdio>
int main()
{
    char ans[26][26];
    for(int i=0;i<26;i++){//这样把最大图案存好就不会错了，黑黑 
        ans[i][i]=‘A‘;
        for(int j=i+1;j<26;j++)
            ans[i][j]=ans[j][i]=‘A‘+j-i;
    }
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            printf("%c",ans[i][j]);
        printf("\n");
    }
    return 0;
}

int main()
{
    int minid,maxid,sum,n,a[10010];
    minid=maxid=sum=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        if(a[i]>a[maxid])maxid=i;
        if(a[i]<a[minid])minid=i;
        sum+=a[i];
    }
    printf("%d\n%d\n%d\n",a[maxid],a[minid],sum);
    return 0;
}

#include<cstdio>
int a[10010];
int main()
{
    int n,c;
    scanf("%d",&n);
    for(int i=1;i<=n+1;i++){
        scanf("%d",&c);
        if(a[c]==0)a[c]=i;
    }
    printf("%d\n",a[c]>n?-1:a[c]);//这里a[c]>n表示c只在最后输入查询值时出现过 
    return 0;
}

#include<cstdio>
int main()
{
    int n,f[35][35];
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        f[i][0]=f[i][i]=1;
        for(int j=1;j<i;j++)
            f[i][j]=f[i-1][j-1]+f[i-1][j];
        for(int j=0;j<i;j++)printf("%d ",f[i][j]);printf("%d\n",f[i][i]);
    }
    return 0;
}

#include<cstdio>
int main()
{
    printf("153\n370\n371\n407\n");
    return 0;
}

#include<cstdio>
int main()
{
    for(int i=1;i<10;i++)
        for(int j=0;j<10;j++)
            printf("%d%d%d%d\n",i,j,j,i);
    return 0;
}

#include<cstdio>
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<10;i++)
        for(int j=0;j<10;j++){
            int k=n-i*2-j*2;
            if(k>=0 && k<10)
            printf("%d%d%d%d%d\n",i,j,k,j,i);}
    if(n%2==0){
        n/=2;
        for(int i=1;i<10;i++)
            for(int j=0;j<10;j++){
                int k=n-i-j;
                if(k>=0 && k<10)
                printf("%d%d%d%d%d%d\n",i,j,k,k,j,i);}
    }
    return 0;
}

#include<cstdio>
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n/2&&i<10;i++)
        for(int j=0;j<=n/2-i&&j<10;j++){
            int k=n-i*2-j*2;
            if(k<10)
            printf("%d%d%d%d%d\n",i,j,k,j,i);}
    if(n%2==0){
        n/=2;
        for(int i=1;i<=n&&i<10;i++)
            for(int j=0;j<=n-i&&j<10;j++){
                int k=n-i-j;
                if(k<10)
                printf("%d%d%d%d%d%d\n",i,j,k,k,j,i);}
    }
    return 0;
}

#include<cstdio>
int main()
{
    int n;
    scanf("%d",&n);
    printf("%X\n",n);//注意X
    return 0;
}

#include<cstdio>
int main()
{
    long long n;
    scanf("%I64X",&n);
    printf("%I64d\n",n);
    return 0;
}

#include<cstdio>
#include<cstring>
int getnu(char c){
    if(c>=‘0‘ && c<=‘9‘)return c-‘0‘;
    return c-‘A‘+10;
}
void putans(char *s){
    int ans=0;
    for(int i=0;i<3;i++)
        ans=ans*16+getnu(s[i]);
    printf("%04o",ans);
}
int main()
{
    int n;
    char a[100010];
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%s",a);
        int len=strlen(a);
        int flen=(len-1)%3+1;
        int ans=0;
        for(int i=0;i<flen;i++)
            ans=ans*16+getnu(a[i]);
        printf("%o",ans);
        for(int j=flen;j<len;j+=3)putans(a+j);
        printf("\n");
    }
    return 0;
}

#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
    int a[210],n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    sort(a,a+n);
    for(int i=0;i<n-1;i++)printf("%d ",a[i]);printf("%d\n",a[n-1]);
    return 0;
}

#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 1010
struct Element{

    int v,id;
}e[MAXN];
bool Cmp(Element x,Element y){
    return x.v>y.v;
}
bool Recmp(Element x,Element y){
    return x.id<y.id;
}
int main()
{
    int n,m,l,r,k;//n,m最大为1000，sort()最坏情况为O(nlogn)
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&e[i].v);
        e[i].id=i;
    }
    scanf("%d",&m);
    for(int i=0;i<m;i++){//O(m*n*logn)<=10^7 
        scanf("%d%d%d",&l,&r,&k);
        sort(e+l,e+r+1,Cmp);//按大到小排序 
        printf("%d\n",e[l+k-1]);
        sort(e+l,e+r+1,Recmp);//按原数组下标从小到大排序 
    }
    return 0;
}

#include<cstdio>
//1-n中取三个数
int main()
{
    long long n,ans;
    scanf("%I64d",&n);
    if(n<3)ans=n;
    else{
        if(n&1)ans=n*(n-1)*(n-2);
        else{
            if(n%6==0)ans=(n-1)*(n-2)*(n-3);
            else ans=n*(n-1)*(n-3);
        }
    }
    printf("%I64d\n",ans);
    return 0;
}

#include<cstdio>
#include<cmath>
using namespace std;
const int Mod=1000000007; 
int main()
{
    int k,l,dp[110][110]={0},ans=0;
    scanf("%d%d",&k,&l);
    if(l<2)ans=k*l;//我觉得这里的k不应该减一，但是题目中这里的k需要减掉1才能过掉第一组数据（好坑） 
    else{
        dp[0][1]=0;
        for(int i=1;i<k;i++)dp[i][1]=1;
        for(int j=2;j<=l;j++){
            for(int i=0;i<k;i++){
                for(int h=0;h<k;h++){
                    if(abs(h-i)!=1)dp[i][j]=(dp[i][j]+dp[h][j-1])%Mod;//abs()=1时表示是相邻的数字 
                }
            }
        }
        for(int i=0;i<k;i++){
            ans=(ans+dp[i][l])%Mod;
        }
    }
    printf("%d\n",ans);
    return 0;
}

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 100010
int Head[MAXN],Head0[MAXN],n,V[MAXN],D[MAXN],Son[MAXN],GSon[MAXN],mk=0;
bool f[MAXN];
struct EdgeNode{
    int to,next;
}Edges[MAXN],Edges0[MAXN<<1];
void DFS(int s){//递归 
    int k=Head[s];
    D[s]=V[s];
    while(k>=0){
        if(D[Edges[k].to]<0)DFS(Edges[k].to);
        Son[s]+=D[Edges[k].to];
        GSon[s]+=Son[Edges[k].to];
        k=Edges[k].next;
    }
    D[s]=max(D[s]+GSon[s],Son[s]);
}
void GtoT(int u){//生成树
    int k=Head0[u];
    while(k>=0){
        if(!f[Edges0[k].to]){
            f[Edges0[k].to]=true;
            Edges[mk].to=Edges0[k].to;
            Edges[mk].next=Head[u];
            Head[u]=mk;
            mk++;
            GtoT(Edges0[k].to); 
        }
        k=Edges0[k].next;
    }
}
void Swap(int &a,int &b){
    int c=a;
    a=b;
    b=c;
}
int main()
{
    int u,v;
    scanf("%d",&n);
    memset(Head,-1,sizeof(Head));
    memset(Head0,-1,sizeof(Head0));
    memset(D,-1,sizeof(D));
    memset(Son,0,sizeof(Son));
    memset(GSon,0,sizeof(GSon));
    for(int i=1;i<=n;i++)scanf("%d",&V[i]);
    for(int i=0;i<2*n-2;i++){//生成图，双向 
        scanf("%d%d",&u,&v);
        Edges0[i].to=v;
        Edges0[i].next=Head0[u];
        Head0[u]=i++;
        Swap(u,v);
        Edges0[i].to=v;
        Edges0[i].next=Head0[u];
        Head0[u]=i;
    }
    memset(f,false,sizeof(f));
    f[1]=true;//图中任选一点，这里选结点1 
    GtoT(1); 
    DFS(1);
    printf("%d\n",D[1]);
    return 0;
}

#include<cstdio>
#include<cstring>
#define MAXN 20010
#define MAXM 200010
#define INF 200000
int Head[MAXN],n,m,Dist[MAXN];
struct EdgeNode{
    int to,w,next;
}Edges[MAXM];
void SPFA(int s){//题目说不存在负环，所以没实现判断负环存在功能 
    int Que[MAXN],Iq=0;
    bool Visit[MAXN];
    for(int i=0;i<=n;i++)Dist[i]=INF;
    memset(Visit,false,sizeof(Visit));
    Dist[s]=0;
    Visit[s]=true;
    Que[Iq++]=s;
    int Id=0;
    while(Id!=Iq){
        int top=Que[Id];
        Visit[top]=false;
        int k=Head[top];
        while(k>=0){
            if(Dist[Edges[k].to]>Edges[k].w+Dist[top]){
                Dist[Edges[k].to]=Edges[k].w+Dist[top];
                if(!Visit[Edges[k].to]){
                    Que[Iq++]=Edges[k].to;
                    Visit[Edges[k].to]=true;
                }
            }
            k=Edges[k].next;
        }
        Id++;
    }
}
int main()
{
    int u,v,l;
    scanf("%d%d",&n,&m);
    memset(Head,-1,sizeof(Head));
    for(int i=0;i<m;i++){//链式前向星建图 
        scanf("%d%d%d",&u,&v,&l);
        Edges[i].to=v;
        Edges[i].w=l;
        Edges[i].next=Head[u];
        Head[u]=i;
    }
    SPFA(1);
    for(int i=2;i<=n;i++)printf("%d\n",Dist[i]);
    return 0;
}

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXM=100010;
const int MAXN=10010;
int f[MAXN];
int find(int x){
    if(f[x]==x)return x;
    return find(f[x]);
}
void Merge(int x,int y){
    f[y]=x;
}
struct Edge{
    int a,b,v;
}e[MAXM];
bool cmp(Edge a,Edge b){
    return a.v<b.v;
}
int main()
{
    int ans=0,k=1,N,P,C[MAXN];
    scanf("%d%d",&N,&P);
    for(int i=1;i<=N;i++){
        scanf("%d",&C[i]);
        if(C[i]<C[k])k=i;//选择过夜牧场 
    }
    ans+=C[k];
    for(int i=0;i<P;i++){
        scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].v);
        e[i].v<<=1;//边权重构
        e[i].v+=C[e[i].a]+C[e[i].b];
    }
    sort(e,e+P,cmp);
    k=0;
    for(int i=1;i<=N;i++)f[i]=i;
    for(int i=0;i<P;i++){//Kruskal 
        int x=find(e[i].a);//并查集 
        int y=find(e[i].b);
        if(x!=y){
            k++;
            ans+=e[i].v;
            Merge(x,y);
        }
        if(k==N-1)break;
    }
    printf("%d\n",ans);
    return 0;
}

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
long long ans=0,ls,lans,rans,lin,rin;
struct Node{
    Node *ch[2];
    int v;
    int r;
    int s;
    int sv;
    Node(int v,int c):v(v){
        ch[0]=ch[1]=NULL;r=rand();s=sv=c;
    }
    int cmp(int x){
        if(x==v)return -1;
        return x<v?0:1;
    }
    void maintain(){
        s=sv;
        if(ch[0]!=NULL)s+=ch[0]->s;
        if(ch[1]!=NULL)s+=ch[1]->s;
    }
};
void rotate(Node* &o,int d){
    Node* k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;o->maintain();k->maintain();o=k;
}
void insert(Node* &o,int x,int c){
    if(o==NULL)o=new Node(x,c);
    else{
        int d=o->cmp(x);
        if(d==-1){
            rin=o->sv;
            if(o->ch[0]!=NULL)lin+=o->ch[0]->s;
            o->s+=c;o->sv+=c;
        }else{
            if(d==1){
                lin+=o->sv;
                if(o->ch[0]!=NULL)lin+=o->ch[0]->s;
            }
            insert(o->ch[d],x,c);
            if(o->ch[d]->r > o->r) rotate(o,d^1);
        }
    }
    o->maintain();
}
int Rank(Node* o,int x){
    if(o==NULL)return 0;
    if(o->v>x)return Rank(o->ch[0],x);
    int t=0;
    if(o->ch[0]!=NULL)t+=o->ch[0]->s;
    if(o->v==x)return t;
    return t + (o->sv) + Rank(o->ch[1],x);
}
int TRank(Node* o,int x){
    if(o==NULL)return 0;
    if(o->v<x)return TRank(o->ch[1],x);
    int t=0;
    if(o->ch[1]!=NULL)t+=o->ch[1]->s;
    if(o->v==x)return t;
    return t + (o->sv) + TRank(o->ch[0],x);
}
void Merge(Node* &a,Node* &b){
    if(b->ch[1]!=NULL)Merge(a,b->ch[1]);
    lin=rin=0;
    insert(a,b->v,b->sv);
    lans+=lin*b->sv;
    rans+=(ls-lin-rin)*b->sv;
    if(b->ch[0]!=NULL)Merge(a,b->ch[0]);
}
void Count(Node* &a,Node* &b){
    lans+=(long long)Rank(a,b->v)*(b->sv);
    rans+=(long long)TRank(a,b->v)*(b->sv);
    if(b->ch[0]!=NULL)Count(a,b->ch[0]);
    if(b->ch[1]!=NULL)Count(a,b->ch[1]);
}
Node* Merge_count(Node* &a,Node* &b){
    lans=rans=0;
    ls=a->s;
//  Count(a,b);
    Merge(a,b);
    ans+=min(lans,rans);
    return a;
}
Node* Init(){
    int x;
    scanf("%d",&x);
    if(x!=0){
        Node* o=new Node(x,1);
        return o;
    }
    Node* a=Init();
    Node* b=Init();
    if(a->s >= b->s)return Merge_count(a,b);
    return Merge_count(b,a);
}
int main()
{
    int n;
    scanf("%d",&n);
    Init();
    printf("%I64d\n",ans);
    return 0;
}

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 100001
int s=1,n,Seg[MAXN<<2],BIT[MAXN];
void Seg_RefUp(int i,int c){//线段树更新O(logn)
    Seg[i]=c;
    while(i>1){
        i>>=1;
        int e=Seg[i];
        Seg[i]=max(Seg[i<<1],Seg[i<<1|1]);
        if(e==Seg[i])return;
    }
}
void BIT_RefUp(int k,int c){//树状数组更新O(logn)
        while(k<=n){
            BIT[k]+=c;
            k+=k&-k;
        }
}
void BuildSegAndBIT(){//建线段树和树状数组(时间复杂度和空间复杂度实际上都是O(n))
    memset(Seg,0,sizeof(Seg));
    memset(BIT,0,sizeof(BIT));
    while(s<n)
        s<<=1;
    s--;
    int c;
    for(int i=1;i<=n;i++){
        scanf("%d",&c);
        Seg_RefUp(s+i,c);
        BIT_RefUp(i,c);
    }
}
int BIT_Query(int a,int b){//树状数组查询O(logn)
    int ans=0;
    while(b>0){
        ans+=BIT[b];
        b-=b&-b;
    }
    a--;
    while(a>0){

        ans-=BIT[a];
        a-=a&-a;
    }
    return ans;
}
int Seg_Query(int a,int b,int k,int l,int r){//线段数查询O(logn)
    if(a<=l && b>=r)return Seg[k];
    if(a>r || b<l)return 0;
    return max(Seg_Query(a,b,k<<1,l,(l+r)>>1),Seg_Query(a,b,(k<<1)+1,((l+r)>>1)+1,r));
}
int main()
{
    int m,p,x,y;
    scanf("%d%d",&n,&m);
    BuildSegAndBIT();
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&p,&x,&y);
        if(p==1){
            BIT_RefUp(x,y-Seg[s+x]);
            Seg_RefUp(s+x,y);
        }
        if(p==2)
            printf("%d\n",BIT_Query(x,y));
        if(p==3)
            printf("%d\n",Seg_Query(x,y,1,1,s+1));
    }
    return 0;
}

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN=25010;
const int MAXE=150010;
int head[MAXN],size,HEAD[MAXN],SIZE;

struct Edge{
    int to,next,w;
}edge[MAXE],EDGE[50010];
void edge_Add(int u,int v,int l){
    edge[size].to=v;
    edge[size].w=l;
    edge[size].next=head[u];
    head[u]=size++;
}
void EDGE_Add(int u,int v){
    EDGE[SIZE].to=v;
    EDGE[SIZE].next=HEAD[u];
    HEAD[u]=SIZE++;
}
int par[MAXN],rank[MAXN];
int find(int x){
    if(x==par[x])return x;
    return par[x]=find(par[x]);
}
void merge(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)return;
    if(rank[x] < rank[y])par[x]=y;
    else{
        par[y]=x;
        if(rank[x]==rank[y])rank[y]++;
    }
}
bool isvis[MAXN];
void DFS_isvis(int s){
    isvis[s]=true;
    for(int k=head[s];k>=0;k=edge[k].next)if(!isvis[edge[k].to])DFS_isvis(edge[k].to);
}
int indegree[MAXN],dist[MAXN];
bool p[MAXN];
void Dijkstra(int s){
    queue<int> degree0;
    priority_queue<pair<int,int> > heap;
    dist[s]=0;
    heap.push(make_pair(0,s));
    while(!heap.empty() || !degree0.empty()){
        if(heap.empty()){
            int u=degree0.front();
            degree0.pop();
            for(int k=HEAD[u];k>=0;k=EDGE[k].next){
                int v=EDGE[k].to;
                heap.push(make_pair(-dist[v],v));
            }
        }else{
            int u=heap.top().second;
            heap.pop();
            if(p[u])continue;
            p[u]=true;
            for(int k=head[u];k>=0;k=edge[k].next){
                int v=edge[k].to;
                if(!p[v] && dist[v]>dist[u]+edge[k].w){
                    dist[v]=dist[u]+edge[k].w;
                    if(find(u)==find(v))heap.push(make_pair(-dist[v],v));
                }
                if(find(u)!=find(v)){
                    indegree[find(v)]--;
                    if(indegree[find(v)]==0)degree0.push(find(v));
                }
            }
        }
    }
}
int main()
{
    int n,r,p,s,a,b,c,d=0,U[50010],V[50010];
    scanf("%d%d%d%d",&n,&r,&p,&s);
    for(int i=1;i<=n;i++){
        par[i]=i;
        rank[i]=0;
        head[i]=HEAD[i]=-1;
    }
    for(int i=0;i<r;i++){
        scanf("%d%d%d",&a,&b,&c);
        edge_Add(a,b,c);
        edge_Add(b,a,c);
        merge(a,b);
    }
    for(int i=0;i<p;i++){
        scanf("%d%d%d",&a,&b,&c);
        U[d]=a;
        V[d++]=b;
        edge_Add(a,b,c);
    }
    DFS_isvis(s);
    for(int i=0;i<p;i++)if(isvis[U[i]]){
        indegree[find(V[i])]++;
        EDGE_Add(find(V[i]),V[i]);
    }
    for(int i=1;i<=n;i++)dist[i]=2000000000;
    Dijkstra(s);
    for(int i=1;i<=n;i++)if(isvis[i])printf("%d\n",dist[i]);else puts("NO PATH");
    return 0;
}

#include<cstdio>
int gcd(int x,int y){//求x,y两者的最大公约数
    int z;
    while(y){
        z=x%y;
        x=y;
        y=z;
    }
    return x;
}
int main()
{
    int a,b,c,ans;
    scanf("%d%d%d",&a,&b,&c);
    ans=a*b/gcd(a,b);//a,b,c<30
    ans=ans*c/gcd(ans,c);
    printf("%d\n",ans); 
    return 0;
}

#include<cstdio>
#define MAX 125
int main()
{
    char g[MAX][MAX],a=‘$‘,b=‘.‘;
    int n,center=63;
    for(int i=0;i<MAX;i++)for(int j=0;j<MAX;j++)g[i][j]=b;
    scanf("%d",&n);n++;
    for(int k=1;k<=n;k++){
        int s=center-k*2,e=center+k*2;
        for(int i=s+2;i<=e-2;i++)g[i][s]=g[i][e]=g[s][i]=g[e][i]=a;
        s++;e--;
        int ss=s+1,ee=e-1;
        g[s][ss]=g[s][ee]=g[ss][s]=g[ss][e]=g[ee][s]=g[ee][e]=g[e][ss]=g[e][ee]=g[ss][ss]=g[ss][ee]=g[ee][ss]=g[ee][ee]=a;
    }
    n<<=1;
    for(int i=center-n;i<=center+n;i++){
        for(int j=center-n;j<=center+n;j++)printf("%c",g[i][j]);printf("\n");
    }
    return 0;
}

#include<iostream>
#include<cstring>
using namespace std;
bool v[10];
int n,ans,nu[10],e;
int getnu(int a,int b){
    int num=0;
    for(int i=0;i<b;i++)num=num*10+nu[a+i];
    return num;
}
void findnu(int k){
    if(k==9){
        for(int a=1;a<=e;a++){
            int d=(9-a)/2;
            for(int b=1;b<=d;b++){
                int c=9-a-b;
                int fm=getnu(0,b);
                int fz=getnu(b,c);
                if(fz%fm==0){
                    int df=getnu(b+c,a);
                    if(df+fz/fm==n)ans++;
                }
            }
        }
        return;
    }
    for(int i=1;i<10;i++)if(!v[i]){
        v[i]=true;
        nu[k]=i;
        findnu(k+1);
        v[i]=false;
    }
}
int main()
{
    cin>>n;
    int m=n;
    while(m){
        e++;
        m/=10;
    }
    memset(v,false,sizeof(v));
    findnu(0);
    cout<<ans<<endl;
    return 0;
}

#include<cstdio>
#include<sstream>
#include<string>
#include<iostream>
using namespace std;
int f[100010];
int main()
{
    int n,max=0,min=100010,c;
    string s;
    scanf("%d",&n);
    getline(cin,s);
    for(int i=0;i<n;i++){
        getline(cin,s);
        istringstream ss(s);
        while(ss>>c){
            f[c]++;
            if(c<min)min=c;
            if(c>max)max=c;
        }
    }
    for(int i=min;i<max;i++){
        if(f[i]==0)n=i;
        if(f[i]==2)c=i;
    }
    printf("%d %d\n",n,c);
    return 0;
}

#include<cstdio>
#include<cstring>
int main()
{
    int ans=0;
    char a[1010],b[1010];
    scanf("%s%s",&a,&b);
    for(int i=0;i<strlen(a)-1;i++)if(a[i]!=b[i]){
        ans++;
        if(b[i+1]==‘o‘)b[i+1]=‘*‘;else b[i+1]=‘o‘;
    }
    printf("%d\n",ans);
    return 0;
}

#include<cstdio>
#define MAXN 50010
int main()
{
    int n,ans=0,a[MAXN],max,min;
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    ans+=n;
    for(int i=0;i<n;i++){
        max=min=a[i];
        for(int j=i+1;j<n;j++){
            if(a[j]>max)max=a[j];
            if(a[j]<min)min=a[j];
            if(j-i==max-min)ans++;
        }
    }
    printf("%d\n",ans);
    return 0;
}

#include<cstdio>
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    printf("%d\n",a*b-a-b);
    return 0;
}

#include<cstdio>
#include<cstring>
#define MAXN 100010//题目没说n的范围，随便取了一个大一点的 
int Head[MAXN],Head0[MAXN],n,mk=0,ans=0;
bool f[MAXN];
struct Edge{
    int next,to,w;
}Edges[MAXN],Edges0[MAXN<<2];
int DFS(int s){//其实这个DFS可以在GtoT中实现的 
    int k=Head[s],max=0;
    while(k>=0){
        int c=Edges[k].w+DFS(Edges[k].to);
        if(c+max>ans)ans=c+max;
        if(c>max)max=c;
        k=Edges[k].next;
    }
    return max;
}
void GtoT(int s){
    int k=Head0[s];
    while(k>=0){
        if(!f[Edges0[k].to]){
            f[Edges0[k].to]=true;
            Edges[mk].to=Edges0[k].to;
            Edges[mk].w=Edges0[k].w;
            Edges[mk].next=Head[s];
            Head[s]=mk++;
            GtoT(Edges0[k].to); 
        }
        k=Edges0[k].next;
    }
}
void Sweap(int &a,int &b){
    int c=a;
    a=b;
    b=c;
}
int main()
{
    int u,v,d;
    memset(Head,-1,sizeof(Head));
    memset(Head0,-1,sizeof(Head0));
    scanf("%d",&n);
    for(int i=0;i<n*2-2;){
        scanf("%d%d%d",&u,&v,&d);
        Edges0[i].to=v;
        Edges0[i].w=d;
        Edges0[i].next=Head0[u];
        Head0[u]=i++;
        Sweap(u,v);
        Edges0[i].to=v;
        Edges0[i].w=d;
        Edges0[i].next=Head0[u];
        Head0[u]=i++;
    }
    memset(f,false,sizeof(f));
    f[1]=true;
    GtoT(1);
    DFS(1);
    printf("%d\n",(21+ans)*ans/2);
    return 0;
}

#include<cstdio>
#define MAXN 1000010
bool flag[MAXN];
int m,n,a[MAXN],s[MAXN],size=0;//a[i]存储幸运数i的位置(幸运数列中的) 
int fa(int k){
    if(flag[k])return a[k];
    return fa(k-1);
}
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i+=2){
        s[++size]=i;//s[]存储幸运数列 
        flag[i]=true;//f[i]存储i是否为幸运数 
        a[i]=size;
    }
    for(int i=2;i<=size;i++){
        int Mod=s[i],d=s[i]-1;
        if(Mod>size)break;
        for(int p=1,j=Mod;j<=size;j+=Mod,p++){
            flag[s[j]]=false;
            for(int k=1;k<Mod&&k+j<=size;k++){
                s[++d]=s[j+k];
                a[s[j+k]]-=p;
            }
        }
        size=d;
    }
    printf("%d\n",fa(n-1)-fa(m));
    return 0;
}

#include<cstdio>
#include<sstream>
#include<string>
#include<iostream>
using namespace std;
#define MAXN 110
#define MAXM 710
struct Node{
    int left,right,left_s,right_s,v,id,ak;
    char a[10];
}Nodes[MAXN];
char map[MAXN][MAXN],a=‘.‘,b=‘-‘,c=‘|‘,d=‘\0‘;
void BinaryTree_set(int rt,int k){
    if(Nodes[k].v>Nodes[rt].v){
        Nodes[rt].right_s++;
        if(Nodes[rt].right!=-1)BinaryTree_set(Nodes[rt].right,k);
        else Nodes[rt].right=k;
    }
    else{
        Nodes[rt].left_s++;
        if(Nodes[rt].left!=-1)BinaryTree_set(Nodes[rt].left,k);
        else Nodes[rt].left=k;
    }
}
void Id_set(int rid,int k){
    Nodes[k].id=rid+Nodes[k].right_s+1;
    if(Nodes[k].right!=-1)Id_set(rid,Nodes[k].right);
    if(Nodes[k].left!=-1)Id_set(Nodes[k].id,Nodes[k].left);
}
void Map_set(int k,int index){
    for(int i=0;i<Nodes[k].ak;i++)map[Nodes[k].id][index+i]=Nodes[k].a[Nodes[k].ak-1-i];
    index+=Nodes[k].ak;
    if(Nodes[k].left!=-1 || Nodes[k].right!=-1){
        map[Nodes[k].id][index++]=b;
        int max,min;
        max=min=Nodes[k].id;
        if(Nodes[k].left!=-1){
            max=Nodes[Nodes[k].left].id;
            map[Nodes[Nodes[k].left].id][index+1]=b;
            Map_set(Nodes[k].left,index+2);
        }
        if(Nodes[k].right!=-1){
            min=Nodes[Nodes[k].right].id;
            map[Nodes[Nodes[k].right].id][index+1]=b;
            Map_set(Nodes[k].right,index+2);
        }
        for(int i=min;i<=max;i++)map[i][index]=c;
        map[Nodes[k].id][index+1]=d;
    }
    else{
        map[Nodes[k].id][index]=d;
        return;
    }
}
int main()
{
    int n=0,e,A[MAXN];
    string s;
    getline(cin,s);
    istringstream ss(s);
    while(ss>>e)A[n++]=e;
    for(int i=0;i<n;i++){
        e=A[i];
        Nodes[i].left=Nodes[i].right=-1;
        Nodes[i].left_s=Nodes[i].right_s=0;
        Nodes[i].ak=0;
        Nodes[i].v=e;
        while(e){
            Nodes[i].a[Nodes[i].ak++]=e%10+‘0‘;
            e/=10;
        }
    }
    for(int i=1;i<n;i++)BinaryTree_set(0,i);
    Id_set(0,0);
    for(int i=1;i<=n;i++)for(int j=0;j<MAXM;j++)map[i][j]=a;
    Map_set(0,0);
    for(int i=1;i<=n;i++)printf("%s\n",map[i]);
    return 0;
}

#include<cstdio>
#define MAXN 1010
#define MAXM 2010
int E[MAXN],U[MAXM],V[MAXM],n,m,x,y,ans=-1;
void Merge(int a,int b){
    int c=E[b];
    for(int i=1;i<=n;i++)if(E[i]==c)E[i]=E[a];
}
void MinSpanTree(int t){
    for(int i=0;i<m;i++){
        if(U[i]==t || V[i]==t)continue;
        if(E[U[i]]!=E[V[i]])Merge(U[i],V[i]);
        if(E[x]==E[y])break;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)scanf("%d%d",&U[i],&V[i]);
    scanf("%d%d",&x,&y);
    for(int j=1;j<=n;j++)E[j]=j;
    MinSpanTree(0);
    if(E[x]==E[y])ans++;//判断两点是否连通 
    if(ans!=-1)for(int i=1;i<=n;i++){
        if(i==x || i==y)continue;
        for(int j=1;j<=n;j++)E[j]=j;
        MinSpanTree(i);
        if(E[x]!=E[y])ans++;//判断出去i点后，两点是否连通 
    }
    printf("%d\n",ans);
    return 0;
}

#include<cstdio>
#include<cstring>
#define MAXN 10010
#define MAXM 100010
int Du[MAXN],U[MAXM],V[MAXM];
int main()
{
    int n,m;
    long long ans=0;
    scanf("%d%d",&n,&m);
    memset(Du,0,sizeof(Du));
    for(int i=0;i<m;i++){
        scanf("%d%d",&U[i],&V[i]);
        Du[U[i]]++;
        Du[V[i]]++;
    }
    for(int i=0;i<m;i++)if(Du[U[i]]>1&&Du[V[i]]>1)ans+=(Du[U[i]]-1)*(Du[V[i]]-1)*2;//我在想，这里的Du是不是也应该定义成long long型(特例好像会溢出，但测试数据中没有) 
    printf("%I64d\n",ans);
    return 0;
}

#include<cstdio>
#include<string>
#include<sstream>
#include<iostream>
using namespace std;
#define MAXN 110
int a[MAXN],b[MAXN],n,t;
int main()
{
    string s;
    getline(cin,s);
    istringstream ss(s);
    while(ss>>t)a[n++]=t;
    for(int i=0;i<n-1;i++)b[i]=a[i+1]-a[i]-1;
    int sss=0;
    for(int i=0;i<n-1;i+=2)sss^=b[i];
    if(sss==0){
        printf("-1\n");
        return 0;
    }
    for(int i=0;i<n-1;i++){
        if(i&1){
            if(b[i]>=(sss^b[i-1])-b[i-1]){
                printf("%d %d\n",a[i],a[i]+(sss^b[i-1])-b[i-1]);
                return 0;
            }
        }
        else{
            if(b[i]>(sss^b[i])){
                printf("%d %d\n",a[i],a[i]+(b[i]-(sss^b[i])));
                return 0;
            }
        }
    }
    printf("-1\n");
    return 0;
}

/*
    当n>1时，刷油漆可以分为5个状态
    顺序为a->b->c->d
    或a->b->...->c->d(状态3)
状态1)(可由状态1,2得来)
..ac    ..ab
..db    ..dc
状态2)(可由状态2,3,4,5得来)
..bc    ..bd    ..ad    ..ac
..ad    ..ac    ..bc    ..bd
状态3)(可由状态3得来)
..ba    ..ca
..cd    ..bd
状态4)(可由状态2得来)
..ba    ..dc
..dc    ..ba
状态5)(可由状态2得来)
..ad    ..cb
..cb    ..ad

*/
#include<cstdio>
#define MAXN 1010
#define MOD 1000000007
int main()
{
    long long DP[5][MAXN],ans=2;
    int n;
    scanf("%d",&n);
    if(n>1){
        DP[0][2]=DP[2][2]=DP[3][2]=DP[4][2]=4;
        DP[1][2]=8;
        for(int i=3;i<=n;i++){
            DP[0][i]=(DP[0][i-1]*2+DP[1][i-1]*2)%MOD;
            DP[1][i]=(DP[1][i-1]*2+DP[2][i-1]*4+DP[3][i-1]*2+DP[4][i-1]*2)%MOD;
            DP[2][i]=DP[2][i-1]*2%MOD;
            DP[3][i]=DP[1][i-1];
            DP[4][i]=DP[1][i-1];
        }
        ans=0;
        for(int i=0;i<5;i++)ans+=DP[i][n];
        ans%=MOD;
    }
    printf("%I64d\n",ans);
    return 0;
}