C++ প্রোগ্রামটি খুঁজে বের করতে যে আমরা কতগুলি ঘাঁটি উপস্থাপন করতে পারি তা M-এর চেয়ে বড় নয়

ধরুন আমাদের একটি সাংখ্যিক স্ট্রিং S আছে, এবং আরেকটি সংখ্যা M আছে। ধরা যাক d-কে S-এর সর্বশ্রেষ্ঠ অঙ্ক। আমাদের খুঁজে বের করতে হবে M-এর চেয়ে বড় নয় এমন অনেকগুলি পূর্ণসংখ্যা খুঁজে বের করতে হবে যা d+1-এর চেয়ে কম নয় এমন একটি পূর্ণসংখ্যা n চয়ন করে খুঁজে পাওয়া যেতে পারে। একটি বেস-এন সংখ্যা হিসাবে S?

সুতরাং, যদি ইনপুটটি S ="999" এর মত হয়; M =1500, তাহলে আউটপুট হবে 3, কারণ S হিসাবে বেস 10 সংখ্যা, আমরা 999 পাই, বেস 11 সংখ্যা হিসাবে, আমরা 1197 পাই, বেস 12 সংখ্যা হিসাবে, আমরা 1413 পাব। এই তিনটি মান শুধুমাত্র আমরা যা করতে পারি। প্রাপ্ত করুন এবং 1500 এর বেশি নয়।

পদক্ষেপ

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

if size of S is same as 1, then:
   if numeric value of S <= M, then:
      return 1
   Otherwise
      return 0
d := 0
for each character c in S, do
   d := maximum of d and (c - ASCII of '0')
left := d
right := M + 1
while right - left > 1, do:
   mid := (left + right) / 2
   v := 0
   for each character c in S, do
      if v > M / mid, then:
         v := M + 1
      Otherwise
         v := v * mid + (c - ASCII of '0')
   if v <= M, then:
      left := mid
   Otherwise
      right := mid
return left - d

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <bits/stdc++.h>
using namespace std;

int solve(string S, int M){
   if (S.size() == 1){
      if (stoi(S) <= M)
         return 1;
      else
         return 0;
   }
   int d = 0;
   for (char c : S)
      d = max(d, int(c - '0'));
   long left = d;
   long right = M + 1;
   while (right - left > 1){
      long mid = (left + right) / 2;
      long v = 0;
      for (char c : S){
         if (v > M / mid)
            v = M + 1;
         else
            v = v * mid + (c - '0');
      }
      if (v <= M)
         left = mid;
      else
         right = mid;
   }
   return left - d;
}
int main(){
   string S = "999";
   int M = 1500;
   cout << solve(S, M) << endl;
}

ইনপুট

"999", 1500