Codeforces Round#235(Div.2)C Team構造法

2166 ワード

タイトルリンク:http://codeforces.com/contest/401/problem/C
2つの整数n,mを入力します.nは0の個数を表し、mは1の個数を表す.0と1のみを含む一連の数字を出力し、0は隣接せず、3つの1は連続できないことが要求されます.解がない場合は-1を出力.
問題解決の考え方:
まず无解の状态を判断して、この数字がこのような时:11011.....011 このときの0の個数が最も少ない、すなわち2*n+2=mであり、簡略化:2*n+2>=m
この数字がこのような場合:0101010....010の場合の0の個数が最も多く、すなわちm=n-1であり、簡略化:m>=n-1である.
いくつかの状態を特に判断する必要があります.
1、11011011のように... このときm==n*2+2
2、類似110……1101この時m==n*2+1
3、n>m
4、n#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<string> #include<stack> #include<queue> #include<vector> #include<algorithm> #include<iostream> #define maxn 3000000 using namespace std; #ifdef __int64 typedef __int64 LL; #else typedef long long LL; #endif int n,m; int main() { while(~scanf("%d%d",&n,&m)) { if(m<n-1||m>2*n+2)// printf("-1
"); else { if(m==n*2+2)// { for(int i=1;i<=n;i++) { printf("110"); } printf("11
"); } else if(m==n*2+1)// { for(int i=1;i<=n;i++) { printf("110"); } printf("1
"); } else if(n>m)// { while(n>m) { printf("010"); n-=2; m--; } for(int i=1;i<=n;i++) printf("10"); printf("
"); } else// { while(m>n) { printf("110"); m-=2; n--; } for(int i=1;i<=n;i++) printf("10"); printf("
"); } } } return 0; }