1 <= A < 10^15
1 <= S <= 135
আমরা যদি A পর্যন্ত সকল সংখ্যা generate করি এবং sum এর সমান কিনা তা check করি তাহলেই আমরা আমাদের answer পেয়ে যাব।
1 <= S <= 135
আমরা যদি A পর্যন্ত সকল সংখ্যা generate করি এবং sum এর সমান কিনা তা check করি তাহলেই আমরা আমাদের answer পেয়ে যাব।
000
001
.
.
188
189
.
.
244
245
.
.
257
258
আমাদের কে প্রথমে জানতে হবে ডিজিট সংখ্যা কয়টি। এখানে আমরা ৩ ডিজিট এর সংখ্যা ধরেছি A।
আমরা ৩ ডিজিট এর সকল সংখ্যা generate করতে পারব। কিন্তু A এর উপরের সংখ্যা generate করে আমাদের কোন লাভ হবে না। তাই A পর্যন্ত limit দিয়ে ৩ ডিজিট এর সংখ্যা generate করব।
আমরা আগেই n ডিজিট এর সকল সংখ্যা কিভাবে generate করা যায় তা দেখেছি এখানে।
এখন আমরা দেখবো A পর্যন্ত limit কিভাবে সেট করা যায়।
আমরা একটা recursive function লেখতে পারি। যার প্যারামিটার হবে 3ta current_digit_no ,sum_left , limit ।
আমরা এভাবে চিন্তা করতে পারি A = 2(0 তম ডিজিট ) 5 (1 তম ডিজিট) 6 (2 তম ডিজিট) 8 (3 তম ডিজিট)।
function er limit parameter আমাদের বলবে আমরা যে ডিজিট এ আসছি তার limit পর্যন্ত নিতে পারব না সব সংখ্যা নিতে পারব।
০ তম ডিজিট এর জন্য আমরা highest ২ পর্যন্ত generate করতে পারব, আমরা যদি ০ তম ডিজিট এ ২ নিয়ে আগাই তাহলে ১ তম ডিজিট এ ৫ পর্যন্ত genetare করতে পারব, আবার আমরা যদি ০ তম ডিজিট এ ০/১ নিয়ে আগাই তাহলে ১ তম ডিজিট এ ০-৯ পর্যন্ত সব গুল ডিজিট নিয়ে আগাইতে পারব। পরের ডিজিট এর জন্য same কাজ হবে।
আমরা limit এর ২টা value ঠিক করব।
যখন limit == 0 তখন প্রতিবার ০ - ৯ এর মধে সবগুলো সংখ্যা নিয়ে একবার আগাবো যদি sum_left - সংখ্যা >= ০ হয় সাথে sum_left থেকে সংখ্যা টা বিয়োগ করে দিব আর limit 0 পাথাব।
আর যখন limit == 1 তখন ঐ ডিজিট এর highest_limit বের করব। প্রতিবার ০ ঠেকে highest_limit এর মধে সবগুলো সংখ্যা নিয়ে একবার আগাবো যদি sum_left - সংখ্যা >= ০ হয় সাথে sum_left থেকে সংখ্যা টা বিয়োগ করে দিব। সংখ্যাটা highest_limit এর চে ছোট হলে limit = 0 পাঠাব আর highest_limit এর সমান হলে limit = 1 পাঠাব।
BaseCase:
যদি current_digit_no যদি n হয়ে যায় আর sum_left ০ হয়ে যায় তার মানে আমরা এমন একটা n ডিজিট বিশিষ্ট সংখ্যা পায়ে গেছি যার ডিজিট গুলোর যোগ ফল sum এর সমান। তাই আমরা ১ return করব।
যদি current_digit_no যদি n হয়ে যায় আর sum_left ০ না হয় তার মানে আমরা যে সংখ্যা generate করেছি যার ডিজিট গুলোর যোগ ফল sum এর সমান না। তাই আমরা ০ return করব।
dynamic programming:
function টার recursive tree আঁকলে দেখবো যে এখানে overlapping subproblem পাওয়া যাবে। তাই যদি আমরা memorization করতে পারি।
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<bits/stdc++.h> | |
| using namespace std; | |
| string s; | |
| int n; | |
| int dp[10][95][3]; // digit number max = 10 (0<=A<=10^10) | |
| /// as there can be at most 10 digit the max sum can be 9*10 = 90 so if input sum > 90 then answer will be 0 | |
| string int_to_string(int a){ | |
| stringstream ss; | |
| ss << a; | |
| string str = ss.str(); | |
| return str; | |
| } | |
| long long f(int current_digit_no,int sum_left,int limit){ | |
| if(current_digit_no==n){ | |
| if(sum_left==0) return 1; | |
| return 0; | |
| } | |
| if(dp[current_digit_no][sum_left][limit]!=-1) return dp[current_digit_no][sum_left][limit]; | |
| long long total = 0; | |
| if(limit==0){ | |
| for(int i=0;i<10;i++){ | |
| if((sum_left-i)>=0) total += f(current_digit_no+1,sum_left-i,0); | |
| } | |
| } | |
| else{ | |
| int highest_limit = (int) (s[current_digit_no] - '0'); | |
| for(int i=0;i<=highest_limit;i++){ | |
| if((sum_left-i)>=0){ | |
| if(i==highest_limit) total += f(current_digit_no+1,sum_left-i,1); | |
| else total += f(current_digit_no+1,sum_left-i,0); | |
| } | |
| } | |
| } | |
| return dp[current_digit_no][sum_left][limit] = total; | |
| } | |
| int main(){ | |
| int a,sum; | |
| cin>>a>>sum; | |
| s = int_to_string(a); | |
| n = s.size(); | |
| memset(dp,-1,sizeof(dp)); | |
| long long z = f(0,sum,1); | |
| cout<<z<<"\n"; | |
| } |
