PAT1010

  1 /*二叉搜索来找进制数*/
  2 #include<iostream>
  3 #include<string>
  4 #include<vector>
  5 #include<iterator>
  6 using namespace std;
  7 
  8 
  9 
 10 /*转换成十进制，注意不能用POW求幂，因为POW返回为double*/
 11 long long turntodec(vector<int> v, long long radix)
 12 {
 13     long long sum = 0;
 14     long long m = 1;
 15     vector<int>::reverse_iterator riter = v.rbegin();
 16     for(; riter != v.rend(); ++riter)
 17     {
 18         sum += *riter * m;
 19         m *= radix;
 20     }
 21     return sum;
 22 }
 23 
 24 long long turntodec_c(vector<int> v, long long radix, long long limit)
 25 {
 26     long long sum = 0;
 27     long long m = 1;
 28     vector<int>::reverse_iterator riter = v.rbegin();
 29     for(; riter != v.rend(); ++riter)
 30     {
 31         sum += *riter * m;    
 32         m *= radix;
 33         if(sum > limit || sum < 0)
 34             return -1;
 35         /*sum<0 及其容易忽略的中间结果的判定条件*/
 36     }
 37     return sum;
 38 }
 39 
 40 /*不递归的二分搜索效率高*/
 41 long long binarysearch(vector<int> v, long long least, long long most, long long sum_other)
 42 {
 43     while(least <= most)
 44     {    
 45         long long mid = (least + most)/2;
 46         long long sum = turntodec_c(v, mid, sum_other);
 47         if(sum == sum_other)
 48             return mid;
 49         else if(sum == -1 )
 50             most = mid - 1;
 51         else 
 52             least = mid + 1;
 53     }
 54     return -1;
 55 }
 56 
 57 int main()
 58 {
 59     string n1, n2;
 60     int tag;
 61     long long radix;
 62     while(cin>>n1>>n2>>tag>>radix)
 63     {
 64         vector<int> v_n1, v_n2;
 65         long long n1_max_num = -1, n2_max_num = -1;
 66         for(int i=0; i < n1.size(); ++i)
 67             if(n1[i] >= 'a' && n1[i] <= 'z')
 68             {
 69                 v_n1.push_back(n1[i] - 'a' + 10);
 70                 if(tag == 2)
 71                     if(n1[i] - 'a' + 10 > n1_max_num)
 72                         n1_max_num = n1[i] - 'a' + 10;
 73             }
 74             else
 75             {
 76                 v_n1.push_back(n1[i] - '0');
 77                 if(tag == 2)
 78                     if(n1[i] - '0' > n1_max_num)
 79                         n1_max_num = n1[i] - '0';
 80             }
 81         for(int i=0; i < n2.size(); ++i)
 82             if(n2[i] >= 'a' && n2[i] <= 'z')
 83             {
 84                 v_n2.push_back(n2[i] - 'a' + 10);
 85                 if(tag == 1)
 86                     if(n2[i] - 'a' + 10 > n2_max_num)
 87                         n2_max_num = n2[i] - 'a' + 10;
 88             }
 89             else
 90             {
 91                 v_n2.push_back(n2[i] - '0');
 92                 if(tag == 1)
 93                     if(n2[i] - '0' > n2_max_num)
 94                         n2_max_num = n2[i] - '0';
 95             }
 96         if(tag == 1)
 97         {
 98             long long sum1 = turntodec(v_n1, radix);
 99             long long leastradix = n2_max_num + 1;
100             long long mostradix = (sum1 + 1 > leastradix + 1 ) ? sum1 + 1 : leastradix + 1;
101             long long result = binarysearch(v_n2, leastradix, mostradix, sum1);
102             if(result == -1)
103                 cout<<"Impossible"<<endl;
104             else
105                 cout<<result<<endl;
106         }
107         else if(tag == 2)
108         {
109             long long sum2 = turntodec(v_n2, radix);
110             long long leastradix = n1_max_num + 1;
111             long long mostradix = (sum2 + 1 > leastradix +1 ) ? sum2 + 1 : leastradix + 1;
112             long long result = binarysearch(v_n1, leastradix, mostradix, sum2);
113             if(result == -1)
114                 cout<<"Impossible"<<endl;
115             else
116                 cout<<result<<endl;            
117         }
118     }
119     return 0;
120 }