একটি প্রোগ্রাম অ্যারে প্রিন্ট করেছিল কিন্তু স্পেস দিয়ে নি। প্রিন্ট করা স্ট্রিং s এবং मैক্সিমাম ভ্যালু k দেওয়া আছে (অ্যারে এলিমেন্ট ১ থেকে k)। স্ট্রিং থেকে আসল অ্যারে কতভাবে রিস্টোর করা যায় তা বের করুন (মডুলো ১০^৯+৭)।
উদাহরণ: s="1318", k=2000 -> ৮টি উপায়: [1318], [131,8], [13,18], [1,318], [1,3,18], [1,31,8], [13,1,8], [1,3,1,8]।
সমাধানের ধাপসমূহ
- DP+memoization: help(idx, num) = idx পজিশন থেকে num বিল্ড করা থাকলে বাকি পার্টের উপায়।
- যদি num >=1 && num <= k && s[idx]!='0': ret += help(idx, 0) (নতুন নম্বর শুরু)।
- যদি num*10 + digit <= k: ret += help(idx+1, new_num)।
- বটম-আপ DPও সম্ভব: ans[i] = স্ট্রিং-এর প্রথম i ক্যারেক্টর থেকে বানানো উপায়।
C++ কোড উদাহরণ
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int m = 1e9 + 7;
class Solution {
public:
unordered_map<int, unordered_map<lli, int>> dp;
lli add(lli a, lli b) { return ((a % m) + (b % m)) % m; }
int help(int idx, string& s, lli num, int k) {
if (idx >= s.size()) return 1;
if (dp.count(idx) && dp[idx].count(num)) return dp[idx][num];
int ret = 0;
if (num >= 1 && num <= k && s[idx] != '0')
ret = add(help(idx, s, 0, k), ret);
if (num * 10 + (s[idx] - '0') <= k)
ret = add(help(idx+1, s, num*10 + (s[idx]-'0'), k), ret);
return dp[idx][num] = ret;
}
int numberOfArrays(string s, int k) {
int n = s.size();
vector<lli> ans(n+1); ans[0] = 1;
s = " " + s;
string ks = to_string(k);
for (lli i = 1; i <= n; i++) {
lli cnt = 1; string temp = "";
for (lli j = i; j >= 1 && cnt <= 10; j--, cnt++) {
temp = s[j] + temp;
if (s[j] == '0') continue;
if (temp.size() > ks.size()) break;
lli val = stol(temp);
if (val >= 1 && val <= k)
ans[i] = add(ans[i], ans[j-1]);
}
}
return ans[n];
}
};
int main() {
Solution ob;
cout << ob.numberOfArrays("1318", 2000);
return 0;
}
ইনপুট
"1318", 2000
আউটপুট
8
