noj 1046第K回文数
6346 ワード
K回文数時間制限(通常/Java):1000 MS/3000 MS実行メモリ制限:65536 KByte総提出:828テスト合格:226試合記述回文数は、左から右へ読むのと右から読むのと同じ正の整数である.例えば11111211505はいずれも返信数である.1から10000000までのすべての回文数を小さい頃からソートした後、k番目の回文数はいくらですか?
入力
第1の動作は整数Nであり、問い合わせの回数を表す.以下のN行は行ごとに1つの整数kであり、k番目の回文数が何であるかを尋ねることを示す.
しゅつりょく
共N行を出力し,入力データの順にk番目の回文数を順次出力する.
サンプル入力2 5 10
サンプル出力5 11
テーマソースNUAA
タイトルリンク:http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1046解題構想:シミュレーション組合せ回文数、数字は最大8桁あるため、最大4桁の数字を列挙するだけで回文数を組み合わせることができ、つまり最大4層の循環がある.コードは次のとおりです.
入力
第1の動作は整数Nであり、問い合わせの回数を表す.以下のN行は行ごとに1つの整数kであり、k番目の回文数が何であるかを尋ねることを示す.
しゅつりょく
共N行を出力し,入力データの順にk番目の回文数を順次出力する.
サンプル入力2 5 10
サンプル出力5 11
テーマソースNUAA
タイトルリンク:http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1046解題構想:シミュレーション組合せ回文数、数字は最大8桁あるため、最大4桁の数字を列挙するだけで回文数を組み合わせることができ、つまり最大4層の循環がある.コードは次のとおりです.
#include
#include
int const maxn=100000000;
int ans[20000];
int main(void)
{
int n=1;
for(int i=1;i<=9;i++)
ans[n++]=i;
for(int i=11;i<=99;i+=11)
ans[n++]=i;
for(int i=1;i<=9;i++)
{
for(int j=0;j<=9;j++)
ans[n++]=i*100+j*10+i;
}
for(int i=1;i<=9;i++)
{
for(int j=0;j<=9;j++)
ans[n++]=i*1000+j*100+j*10+i;
}
for(int i=1;i<=9;i++)
{
for(int j=0;j<=9;j++)
for(int k=0;k<=9;k++)
ans[n++]=i*10000+j*1000+k*100+j*10+i;
}
for(int i=1;i<=9;i++)
{
for(int j=0;j<=9;j++)
for(int k=0;k<=9;k++)
ans[n++]=i*100000+j*10000+k*1000+k*100+j*10+i;
}
for(int i=1;i<=9;i++)
{
for(int j=0;j<=9;j++)
for(int k=0;k<=9;k++)
for(int l=0;l<=9;l++)
ans[n++]=i*1000000+j*100000+k*10000+l*1000+k*100+j*10+i;
}
for(int i=1;i<=9;i++)
{
for(int j=0;j<=9;j++)
for(int k=0;k<=9;k++)
for(int l=0;l<=9;l++)
ans[n++]=i*10000000+j*1000000+k*100000+l*10000+l*1000+k*100+j*10+i;
}
int t,m;
scanf("%d",&t);
while(t--)
{
scanf("%d",&m);
printf("%d
",ans[m] );
}
}