hdu1058 Humble Number

2031 단어
데이터 슈퍼 BT의 한 문제, WA는 왜 틀렸는지 모르겠다. 다른 사람의 AC 코드를 보고 211과 같은 출력에 대해th, 221은 st를 사용해야 한다는 것을 알게 되었다.그걸 눈물이라고 해요%> <%
제목: 인자가 2, 3, 5, 7에 불과한 순서대로 출력됩니다.
이 문제는 이 장에서 문제를 받자마자 DP동태방정식을 생각하고 한참을 멍하니 있었더니 아무리 생각해도 DP가 아니라고 느꼈다.시작할 때 1-200000000에서 순서대로 선별법을 써야 한다고 생각했는데 어쩔 수 없이 무한 시간 초과였다.최적화를 해 보았지만 여전히 안 된다.
나중에 인자가 4개밖에 없는데 모든 수치를 계산하지 않고sort를 해보자.써 봤어.결과적으로 문장 머리에 나타난 비극이 나타났지만, 여전히 나 AC~\(≥;≤)/~에 의해
자세히 생각해 보면 DP도 차이가 많지 않다. DP 그룹에 저장된 것은 엄격하게 증가하는 수이다.헤헤아싸 화이팅!!!
코드:
#include<iostream>
#include<algorithm>
using namespace std;
int num2[31];
int num3[20];
int num5[14];
int num7[12];
int num[6000];
int len=0;
int Calculate()
{
	int i,j,k,w;
	num2[0]=1;
	//31,20,14,12        
	for(i=1;i<31;i++)
		num2[i]=num2[i-1]*2;
	num3[0]=1;
	for(i=1;i<20;i++)
		num3[i]=num3[i-1]*3;
	num5[0]=1;
	for(i=1;i<14;i++)
		num5[i]=num5[i-1]*5;
	num7[0]=1;
	for(i=1;i<12;i++)
		num7[i]=num7[i-1]*7;
	int x,y,z;
	for(i=0;i<31;i++)
	{
		for(j=0;j<20;j++)
		{
			if(2000000000/num2[i]<num3[j]) break;
			x=num2[i]*num3[j];
			for(k=0;k<14;k++)
			{
				if(2000000000/x<num5[k]) break;
				y=x*num5[k];
				for(w=0;w<12;w++)
				{
					if(2000000000/y<num7[w]) break;
					z=y*num7[w];
					num[len++]=z;
				}
			}
		}
	}
	return 0;
}
int main()
{
	int n;
	Calculate();
	sort(num,num+len);
	while(cin>>n&&n)
	{
		if(n%10==1&&n%100!=11) cout<<"The "<<n<<"st humble number is "<<num[n-1]<<"."<<endl;
		else if(n%10==2&&n%100!=12) cout<<"The "<<n<<"nd humble number is "<<num[n-1]<<"."<<endl;
		else if(n%10==3&&n%100!=13) cout<<"The "<<n<<"rd humble number is "<<num[n-1]<<"."<<endl;
		else cout<<"The "<<n<<"th humble number is "<<num[n-1]<<"."<<endl;
	}
	return 0;
}

좋은 웹페이지 즐겨찾기