답안 #19941

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
19941 2016-02-25T07:40:58 Z yukariko 동전 (kriii4_E) C++
0 / 100
0 ms 1720 KB
#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;
}
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -