โปรแกรม C++ หาจำนวนฐานที่เราแทนค่าได้ไม่เกิน M

สมมุติว่าเรามีสตริงตัวเลข S และอีกจำนวนหนึ่ง M ให้ d เป็นตัวเลขที่มีค่ามากที่สุดใน S เราต้องหาจำนวนเต็มที่ต่างกันไม่เกิน M หาได้โดยเลือกจำนวนเต็ม n อย่างน้อย d+1 แล้วดู S เป็นเลขฐาน n?

ดังนั้น หากอินพุตเป็น S ="999"; M =1500 แล้วผลลัพธ์จะเป็น 3 เพราะ S เป็นเลขฐาน 10 เราได้ 999 จากเลขฐาน 11 เราได้ 1197 จากเลขฐาน 12 เราได้ 1413 ค่าทั้งสามนี้เป็นค่าเดียวที่เราทำได้ ได้รับและไม่เกิน 1,500.

ขั้นตอน

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

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

ผลลัพธ์

3