hdu1058 Humble Number
제목: 인자가 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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.