読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Codeforces #235 Div2. C. Team

Codeforces

CF235に参加。Div2回なので気軽だね。
ABCDは順調に解けたけどEが解けなかった。
http://codeforces.com/contest/401/problem/C

問題

0をN個、1をM個使った文字列のうち、以下の条件を満たすものを作れ。

  • 0は2個以上連続しない。
  • 1は3個以上連続しない。

解法

0は2個以上連続しないので、0の合間に1を挟む形になる。
また、挟む1は2個が上限。
よって、M<N-1の場合やM>2(N+1)の場合は条件を満たす文字列が作れない。

それ以外の場合は、M==N-1なら0と1を交互に配置し、それ以外ならN個の0を挟むN+1個の場所に1を配置していけばよい。

void solve() {
	int f,i,j,k,l,x,y;
	ll N,M;
	cin>>N>>M;
	if(M<N-1) return _P("-1\n");
	if(M>2*(N+1)) return _P("-1\n");
	
	if(M==N-1) {
		FOR(i,N) {
			_P("0");
			if(i<N-1) _P("1");
		}
		return _P("\n");
	}
	
	FOR(i,N+1) {
		if(i) _P("0");
		FOR(j,M/(N+1)+(i<(M%(N+1)))) _P("1");
	}
	_P("\n");
	
}

まとめ

まだこのあたりは簡単。

広告を非表示にする