题目来源：

题目如下（链接有可能无法访问）：

A Broken Calculator

---

Time limit : 2sec / Stack limit : 256MB / Memory limit : 256MB

Problem

Dave's calculator is broken. His calculator halts when put more than K kinds of number.

Dave wants to input an integer A, but if he put this number correctly the calculator might halt. Instead, he inputs the closest integer that won't halts the calculator.

Output the difference between Dave's input and the integer A.

---

Input

The input will be given in the following format from the Standard Input.

A K

• On the first line, you will be given the integer A(1≦A≦1015), the integer Dave wants to input, followed by a space andK(1≦K≦10), the kinds of number his calculator can recognize.

Acheivements and Points

• When you pass every test case where 1≦A≦100,000, you will be awarded 30 points.
• In addition, if you pass all the rest test cases you will be awarded 70 more points.

Output

Output the minimum difference between Dave's input and the integer A in one line. Make sure to insert a line break at the end of the output.

---

Input Example 1

1234 2

Output Examle 1

12

In this case Dave can only use up to 2 kinds of numbers.

He will input the closest integer 1222, so the difference is 12.

---

Input Example 2

800000 1

Output Example 2

22223

Dave can use only 1 number, so 777777 is the closest integer.

---

Inout Example 3

7328495 10

Output Example 3

0

In this case Dave's calculator is not broken at all.

He can input the given integer A as is.

---

Input Example 4

262004 2

Output Example 4

218

The closest integer is 262222.

 

解题思路：

设A的数字长度为L，首先寻找K个数，对剩余的L-K数分别计算最大值和最小值，在计算的时候要考虑借位和进位的情况。

具体算法（java版，直接AC）

1 import java.math.BigInteger;  2 import java.util.Arrays;  3 import java.util.Scanner;  4   5 public class Main{  6       7     public int[]available;  8     public String target;  9     public int limited; 10      11     public Main(String target,int limited){ 12         this.available=new int[10]; 13         this.target=target; 14         this.limited=limited; 15     } 16     private int getIntByIndex(int index){ 17         return this.target.charAt(index)-'0'; 18     } 19      20     private BigInteger substract(String str1,String str2){ 21         BigInteger a=new BigInteger(str1); 22         BigInteger b=new BigInteger(str2); 23         if(a.compareTo(b)>0){ 24             return a.subtract(b); 25         }else{ 26             return b.subtract(a); 27         } 28     } 29     private String convertTo(int[]array){ 30         StringBuffer buffer=new StringBuffer(); 31         for(int i=0;i
        
         0){ 58             System.out.println(diff2.toString()); 59         }else{ 60             System.out.println(diff1.toString()); 61         } 62     } 63      64     private int getValue(int[] avail,boolean less){ 65         if(less){ 66             for(int i=0;i<=9;i++){ 67                 if(avail[i]>0) 68                     return i; 69             } 70         }else{ 71             for(int i=9;i>=0;i--){ 72                 if(avail[i]>0) 73                     return i; 74             } 75         } 76         return -1; 77     } 78      79     public int[] calculateMax(int[] avail,int index){ 80         int[]result=new int[this.target.length()]; 81         int nextValue=Integer.MIN_VALUE; 82         for(int i=0;i
         
          0&&i>this.getIntByIndex(index)){ 87                 nextValue=i; 88                 break; 89             } 90         } 91         if(nextValue==Integer.MIN_VALUE){ 92             nextValue=this.getIntByIndex(index-1)+1; 93             for(int j=index-1;j>=0;j--){ 94                 if(result[j]==nextValue-1){ 95                     result[j]=nextValue; 96                 } 97             } 98             result[index-1]=nextValue; 99             avail[nextValue-1]=0;100             int min=Integer.MAX_VALUE;101             if(avail[nextValue]==0){102                 avail[nextValue]=1;103                 min=this.getValue(avail, true);104             }105             for(int j=index;j
          
           =0;i--){126             if(avail[i]>0&&i
           
            =0;j--){140                     if(result[j]==nextValue+1){141                         result[j]=nextValue;142                     }143                 }144                 result[index-1]=nextValue;145                 avail[nextValue+1]=0;146                 int max=Integer.MIN_VALUE;147                 if(avail[nextValue]==0){148                     avail[nextValue]=1;149                     max=this.getValue(avail, false);150                 }151                 for(int j=index;j