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
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;
}