Problem Description
We define f(m,k,n) is the value of the nth number which has m continuous digit k. For example, f(3,6,1)=666,f(3,6,2)=1666,f(3,6,3)=2666,....
Now give you m,k,n and ask you to solve f(m,k,n).
Input
Input contains multiple cases each presented on a separate line. Each line contains three integer numbers m,k,n(2<=m<=10,1<=k<=9,1<=n<=1000000000).
Output
For each test case, your program should output the value of f(m,k,n).
Sample Input
3 6 187
Sample Output
66666
亲测样例结果：发现好像不太正确，但是对于简单的结构是正确的。
操作思路是这样的：
比如3个4，串列：444，1444-3444，4440-4449，你会发现这个规律为444_或_444的分类，“_”代表0-9，这样从444可以发展为左边填一个数字_
这样，形成一个二叉树，采用广度优先搜索，将符合条件的数放入队列中，每一层符合条件的数先放在数组里，然后排序。得到如下条件：
例子的输出：
input m:
3
input k:
4
input n:
5
4440
input m:
3
input k:
6
input n:
187
66639
以下是Java代码关于这个例子的参考实现（附注释）：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class ContinousDigit {
public static String result="";
private static Queue<String> list=new LinkedList<String>();
private static ArrayList<Integer> vector=new ArrayList<Integer>();
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan=new Scanner(System.in);
int m,k,n;
System.out.println("input m:");
m=scan.nextInt();
System.out.println("input k:");
k=scan.nextInt();
System.out.println("input n:");
n=scan.nextInt();
ContinousDigit instance=new ContinousDigit();
instance.LaunchMKN(m,k,n);
System.out.println(instance.result);
}
//construct MKN Core Start String format
public void LaunchMKN(int m,int k,int n){
String oper="";
for(int i=0;i<m;i++) {
oper=oper+""+k;
}
list.add(oper);
MKN(m,k,n,1);
}
//MKN Core
public void MKN(int m,int k,int n,int found){
String load=list.remove();
String temp=load;
//start the bi-directional traversal,right first
for(int i=0;i<10;i++){
load=load+""+i;
vector.add(Integer.parseInt(load));
load=temp;
}
for(int i=0;i<10;i++){
load=i+""+load;
if(judge(load)) {
vector.add(Integer.parseInt(load));
}
load=temp;
}
int[] vec=new int[vector.size()];
for(int i=0;i<vector.size();i++) {
vec[i]=vector.get(i);
}
Arrays.sort(vec);
for(int i=0;i<vector.size();i++) {
found++;
if(found==n) {
result=vec[i]+"";
return;
}else {
list.add(vec[i]+"");
}
}
vector.clear();
vec=null;
MKN(m,k,n,found);
}
public boolean judge(String subject) {
boolean judge=true;
if(subject.charAt(0)=='0') {
judge=false;
}
return judge;
}
}
对不起，上述代码我筛选的粒度太粗了，使用下面算法：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class ContinousDigit {
public static String result="";
private static Queue<String> list=new LinkedList<String>();
private static ArrayList<Integer> vector=new ArrayList<Integer>();
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan=new Scanner(System.in);
int m,k,n;
System.out.println("input m:");
m=scan.nextInt();
System.out.println("input k:");
k=scan.nextInt();
System.out.println("input n:");
n=scan.nextInt();
ContinousDigit instance=new ContinousDigit();
instance.LaunchMKN(m,k,n);
System.out.println(instance.result);
}
//construct MKN Core Start String format
public void LaunchMKN(int m,int k,int n){
String oper="";
for(int i=0;i<m;i++) {
oper=oper+""+k;
}
list.add(oper);
MKN(m,k,n,1,m);
}
public void MKN(int m,int k,int n,int found,int layer) {
int[] source=new int[layer+1];
int[] mark=new int[layer+1];
for(int i=0;i<mark.length;i++) {
mark[i]=0;
}
//get All qualified Number in a coarse granularity
for(int i=0;i<layer+2-m;i++) {
for(int j=0;j<m;j++) {
source[i+j]=k;
mark[i+j]=1;
}
//call recursive
recursive(source,mark);
for(int t=0;t<mark.length;t++) {
mark[t]=0;
source[t]=0;
}
}
//![end] The Same Layer has been added to vector completely
//remove same
//System.out.println("size"+vector.size());
removeSame();
for(int i=0;i<vector.size();i++) {
System.out.println("A["+(i+found+1)+"]="+vector.get(i));
}
if(found+vector.size()>=n) {
//find this element and return
int finalresult=vector.get(n-found-1);
result=finalresult+"";
return;
}else {
//flush all element in vector to queue
for(int i=0;i<vector.size();i++) {
list.add(vector.get(i)+"");
}
found=found+vector.size();
System.out.println("Next Layer base:"+found);
vector.clear();
MKN(m,k,n,found,layer+1);
}
}
public void recursive(int[] source,int[] mark) {
int tag=-1;
for(int i=0;i<mark.length;i++) {
if(mark[i]==0) {
tag=i;
}
}
if(tag==-1) {
String w="";
for(int i=0;i<mark.length;i++) {
w=w+""+source[i];
}
if(judge(w)) {
//System.out.println("============");
//System.out.println(w);
vector.add(Integer.parseInt(w));
}
return;
}else {
for(int i=0;i<10;i++) {
mark[tag]=1;
source[tag]=i;
recursive(source,mark);
}
mark[tag]=0;
}
}
public boolean judge(String subject) {
boolean judge;
if(subject.charAt(0)!='0') {
judge=true;
}else {
judge=false;
}
return judge;
}
public void removeSame() {
//System.out.println(vector.size());
//space for vector element
int[] vec=new int[vector.size()];
//space for remove the Same
int[] vecS=new int[vector.size()];
//populate it
for(int i=0;i<vector.size();i++) {
vec[i]=vector.get(i);
}
//sort in space
Arrays.sort(vec);
//check same
vecS[0]=vec[0];
int tag=1;
for(int i=0;i<vec.length;i++) {
//not add to vecS if vec's element not equal to tail of vecS
if(vecS[tag-1]!=vec[i]) {
vecS[tag]=vec[i];
tag++;
}
}
vector.clear();
for(int i=0;i<tag;i++) {
vector.add(vecS[i]);
}
}
}
输出：
input m:
3
input k:
6
input n:
187
A[2]=1666
A[3]=2666
A[4]=3666
A[5]=4666
A[6]=5666
A[7]=6660
A[8]=6661
A[9]=6662
A[10]=6663
A[11]=6664
A[12]=6665
A[13]=6666
A[14]=6667
A[15]=6668
A[16]=6669
A[17]=7666
A[18]=8666
A[19]=9666
Next Layer base:19
A[20]=10666
A[21]=11666
A[22]=12666
A[23]=13666
A[24]=14666
A[25]=15666
A[26]=16660
A[27]=16661
A[28]=16662
A[29]=16663
A[30]=16664
A[31]=16665
A[32]=16666
A[33]=16667
A[34]=16668
A[35]=16669
A[36]=17666
A[37]=18666
A[38]=19666
A[39]=20666
A[40]=21666
A[41]=22666
A[42]=23666
A[43]=24666
A[44]=25666
A[45]=26660
A[46]=26661
A[47]=26662
A[48]=26663
A[49]=26664
A[50]=26665
A[51]=26666
A[52]=26667
A[53]=26668
A[54]=26669
A[55]=27666
A[56]=28666
A[57]=29666
A[58]=30666
A[59]=31666
A[60]=32666
A[61]=33666
A[62]=34666
A[63]=35666
A[64]=36660
A[65]=36661
A[66]=36662
A[67]=36663
A[68]=36664
A[69]=36665
A[70]=36666
A[71]=36667
A[72]=36668
A[73]=36669
A[74]=37666
A[75]=38666
A[76]=39666
A[77]=40666
A[78]=41666
A[79]=42666
A[80]=43666
A[81]=44666
A[82]=45666
A[83]=46660
A[84]=46661
A[85]=46662
A[86]=46663
A[87]=46664
A[88]=46665
A[89]=46666
A[90]=46667
A[91]=46668
A[92]=46669
A[93]=47666
A[94]=48666
A[95]=49666
A[96]=50666
A[97]=51666
A[98]=52666
A[99]=53666
A[100]=54666
A[101]=55666
A[102]=56660
A[103]=56661
A[104]=56662
A[105]=56663
A[106]=56664
A[107]=56665
A[108]=56666
A[109]=56667
A[110]=56668
A[111]=56669
A[112]=57666
A[113]=58666
A[114]=59666
A[115]=60666
A[116]=61666
A[117]=62666
A[118]=63666
A[119]=64666
A[120]=65666
A[121]=66600
A[122]=66601
A[123]=66602
A[124]=66603
A[125]=66604
A[126]=66605
A[127]=66606
A[128]=66607
A[129]=66608
A[130]=66609
A[131]=66610
A[132]=66611
A[133]=66612
A[134]=66613
A[135]=66614
A[136]=66615
A[137]=66616
A[138]=66617
A[139]=66618
A[140]=66619
A[141]=66620
A[142]=66621
A[143]=66622
A[144]=66623
A[145]=66624
A[146]=66625
A[147]=66626
A[148]=66627
A[149]=66628
A[150]=66629
A[151]=66630
A[152]=66631
A[153]=66632
A[154]=66633
A[155]=66634
A[156]=66635
A[157]=66636
A[158]=66637
A[159]=66638
A[160]=66639
A[161]=66640
A[162]=66641
A[163]=66642
A[164]=66643
A[165]=66644
A[166]=66645
A[167]=66646
A[168]=66647
A[169]=66648
A[170]=66649
A[171]=66650
A[172]=66651
A[173]=66652
A[174]=66653
A[175]=66654
A[176]=66655
A[177]=66656
A[178]=66657
A[179]=66658
A[180]=66659
A[181]=66660
A[182]=66661
A[183]=66662
A[184]=66663
A[185]=66664
A[186]=66665
A[187]=66666
A[188]=66667
A[189]=66668
A[190]=66669
A[191]=66670
A[192]=66671
A[193]=66672
A[194]=66673
A[195]=66674
A[196]=66675
A[197]=66676
A[198]=66677
A[199]=66678
A[200]=66679
A[201]=66680
A[202]=66681
A[203]=66682
A[204]=66683
A[205]=66684
A[206]=66685
A[207]=66686
A[208]=66687
A[209]=66688
A[210]=66689
A[211]=66690
A[212]=66691
A[213]=66692
A[214]=66693
A[215]=66694
A[216]=66695
A[217]=66696
A[218]=66697
A[219]=66698
A[220]=66699
A[221]=67666
A[222]=68666
A[223]=69666
A[224]=70666
A[225]=71666
A[226]=72666
A[227]=73666
A[228]=74666
A[229]=75666
A[230]=76660
A[231]=76661
A[232]=76662
A[233]=76663
A[234]=76664
A[235]=76665
A[236]=76666
A[237]=76667
A[238]=76668
A[239]=76669
A[240]=77666
A[241]=78666
A[242]=79666
A[243]=80666
A[244]=81666
A[245]=82666
A[246]=83666
A[247]=84666
A[248]=85666
A[249]=86660
A[250]=86661
A[251]=86662
A[252]=86663
A[253]=86664
A[254]=86665
A[255]=86666
A[256]=86667
A[257]=86668
A[258]=86669
A[259]=87666
A[260]=88666
A[261]=89666
A[262]=90666
A[263]=91666
A[264]=92666
A[265]=93666
A[266]=94666
A[267]=95666
A[268]=96660
A[269]=96661
A[270]=96662
A[271]=96663
A[272]=96664
A[273]=96665
A[274]=96666
A[275]=96667
A[276]=96668
A[277]=96669
A[278]=97666
A[279]=98666
A[280]=99666
66666