Submission #19941

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19941	2016-02-25T07:40:58 Z	yukariko	동전 (kriii4_E)	C++	0 / 100	0 ms	1720 KB

D

#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007
#define INF 987654321

typedef long long lld;

// (연속된 짝수개의 0)%2 == (연속된 홀수개의 0)%2

char trace[10];

bool isCorrect(char *s, const int& L){
	int i, odd=0, even=0, cnt=0;
	int oneCount=0;
	for(i=0; i<L; ++i){
		if(s[i] == '0'){
			cnt = 0;
			while(s[i+cnt]=='0') cnt++;
			if(cnt&1) odd += 1;
			else even += 1;
			
			i += cnt-1;
			oneCount += cnt==1;
		}
	}
	if(odd == 1 || even == 1) return false;
	if(oneCount&1) return false;
	return odd%2 == even%2;
}

lld f(int pos, const int& L){
	if(pos == L){
		return isCorrect(trace, L);
	}
	int r = 0;
	trace[pos]='0';
	r = (r + f(pos+1, L))%MOD;
	trace[pos]='1';
	r = (r + f(pos+1, L))%MOD;
	return r;
}

int main(){
	int n;
	while(~scanf("%d", &n))
		printf("%lld\n", f(0, n));
	return 0;
}

Subtask #1

0.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1720 KB	Output is correct
2	Correct	0 ms	1720 KB	Output is correct
3	Correct	0 ms	1720 KB	Output is correct
4	Correct	0 ms	1720 KB	Output is correct
5	Correct	0 ms	1720 KB	Output is correct
6	Correct	0 ms	1720 KB	Output is correct
7	Incorrect	0 ms	1720 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 95.0

#	Verdict	Execution time	Memory	Grader output
1	Halted	0 ms	0 KB	-