CODE[VS] 2080 특이한 질수 갈비뼈

제목 설명Description
농민 존의 암소는 항상 가장 좋은 갈비뼈를 만들어 낸다.너는 농민 존과 미국 농업부가 갈비뼈 하나하나에 표시한 숫자를 통해 그것들을 알아볼 수 있다.농민 존은 그가 구매자에게 판매한 것이 진정한 질수 갈비뼈라고 확신했다. 오른쪽부터 갈비뼈를 잘라서 매번 남은 갈비뼈의 숫자가 하나의 질수를 구성했다. 예를 들어 7, 3, 1 모든 갈비뼈의 숫자 7331이 질수이다.세 개의 갈비뼈 733은 질수이다.두 갈비뼈 73은 질수이다.물론 마지막 갈비뼈 7도 질수다.7331은 길이 4의 특수질수라고 불린다.주어진 갈비뼈의 수 N(1<=N<=8)에 대해 프로그램을 써서 모든 특수한 질수를 구한다.숫자 1은 하나의 질수로 간주되지 않는다.
설명 입력 Input Description
별도의 행에는 N이 포함됩니다.
출력 설명 Output Description
각 행에 하나씩 길이가 N인 특수 질량을 순서대로 내보냅니다.
샘플 Sample Input 입력
4
샘플 출력 Sample Output
2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

데이터 범위 및 프롬프트 Data Size & Hint
묘사를 보다
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
신기한 특성: 특수질수 1위는 23574종, 나머지 1위는 13794종~
그리고 이 문제는 매번 네 가지만 가능한 검색이 됐어요. 그리고 데이터 범위도 <=8도 작아요.
판단 질수는 2부터 순환한다. 아아아아!나도 셀 수가 없어. 몇 번째야. 이거 때문에 토혈이 났어!
#include
#include

int n,a1[5]={0,2,3,5,7},a2[5]={0,1,3,7,9},tot;

bool pan(int u)
{
	for(int j=2;j<=(int)sqrt(u*1.0);j++)
	  if(u%j==0) return 0;
	return 1;
}

void dfs(int u,int v)
{
	if(n==v)
	{
		printf("%d
",u);return; } for(int ii=1;ii<=4;ii++) if(pan(u*10+a2[ii])) dfs(u*10+a2[ii],v+1); return; } int main() { scanf("%d",&n); if(n==1) { for(int i=1;i<=4;i++) printf("%d
",a1[i]); return 0; } for(int i=1;i<=4;i++) dfs(a1[i],1); return 0; }

좋은 웹페이지 즐겨찾기