এক আনমু কেমনে (Minimum Steps to One)

ডাইনামিক প্রোগ্রামিং এর বেসিক খুব সুন্দর একটা প্রবলেম নিয়ে আলোচনা করবো । এই প্রবলেমের টিউটোরিয়ালটা কোডশেফের ডাইনামিক প্রোগ্রামিং টিউটোরিয়াল সেকশন থেকে নেয়া । এই টিউটোরিয়াল পড়ার আগে রিকারশন, ডিপি উপর ধারনা থাকতে হবে । রিকারশন বা ডিপি নিয়ে যদি কারও কোন প্রবলেম থাকে তোহ  ফাহিমভাইয়ের ব্লগ এবং শাফায়েতভাইয়ের ব্লগ অতুলনীয় সেখান থেকে দেখে নিতে পারো/পারেন । প্রবলেম স্টেটমেন্ট একটি পজেটিব ইন্টিজার দেয়া থাকবে এবং কিছু শর্ত দেয়া থাকবে বের করতে হবে মিনিমাম কতগুলো স্টেপে সংখ্যাটিকে ওয়ান(এক) করা যাই । শর্তগুলো হল :     ১. এক বিয়োগ করতে পারি (n=n-1) ।     ২. যদি সংখ্যাটি ২ দ্বারা বিভাজ্য হয় তবে ২ দ্বারা ভাগ করা যাবে ।            ( if n % 2 == 0 , then n = n / 2  )     ৩. যদি সংখ্যাটি ৩ দ্বারা বিভাজ্য হয় তবে ৩ দ্বারা ভাগ করা যাবে ।           ( if n % 3 == 0 , then n = n /3  )  উদাহরণ :     1.)  For n = 1 ,  output: 0                         2.) For n = 4 ,  output: 2  ( 4  /2 = 2  /2 = 1 )                      3.) For n = 7 ,  output: 3  (7  -1 = 6   /3 = 2   /2 = 1) সল্ভিং ট্রিক্স   স্টেপগুলো বাছাই করার জন্য অনেকে গ্রিডি চিন্তা করে, তারা চিন্তা করে যে n কে তাড়াতাড়ি কিভাবে ছোট করা যাই এবং ছোট করতে করতে এক সময় ওয়ান(এক)  নিয়ে আসে । যদি তুমি ভাল করে দেখ তবে দেখবে গ্রিডি স্টেটেজিটা আসলে কাজ করতে নাহ । তোহ লোভী চিন্তা করলে এখানে চলবে নাহ। একটা উদাহরণ দেখা যাক : ধর দেয়া আছে n = 10 , Greedy --> 10 /2 = 5 -1 = 4 /2 =...

Uva 1062 – Containers

Problem Link Solution :- Containers C++ /****************************************************************** *** Problewm : Uva 1062 - Containers *** *** Author : Shipu Ahamed (Psycho Timekiller) *** *** E-mail : shipuahamed01@gmail.com *** *** University : BUBT,Dept. of CSE *** *** Team : BUBT_Psycho *** *** My Blog : http://shipuahamed.blogspot.com *** *** Facebook : http://www.facebook.com/DeesheharaShipu *** ******************************************************************/ #include <list> #include <set> #include <map> #include <ctime> #include <stack> #include <queue> #include <cmath> #include <deque> #include <limits> #include <string> #include <cctype> #include <cstdio> #include <vector> #include <bitset> #include <numeric> #include <cassert> #include <sstream> #include <fstream> #include <cstdlib> #include <cstring> #include <utility> #include <complex> #include <iomanip> #include <iostream> #include <iterator> #include <algorithm> using namespace std; #define sc scanf #define pf printf #define ll long long #define pi 2*acos(0.0) #define ull unsigned long long #define all(v) v.begin(),v.end() #define sii(t) scanf("%d",&t) #define sll(t) scanf("%lld",&t) #define ssii(a,b) scanf("%d%d",&a,&b) #define ssll(a,b) scanf("%lld%lld",&a,&b) #define Case(no) printf("Case %d: ",++no) #define nl puts("") #define P(a) printf("%dn",a) #define PL(a) printf("%lldn",a) #define PN(a) printf("%d ",a) #define PLN(a) printf("%lld ",a) #define CP(a) cout<<a<<endl; #define CPN(a) cout<<a; #define ff first #define se second #define pb push_back #define ST(v) sort(all(v)) #define gcd(a,b) __gcd(a,b) #define lcm(a,b) (a*(b/gcd(a,b))) #define max3(a,b,c) max(a,max(b,c)) #define min3(a,b,c) min(a,min(b,c)) #define maxall(v) *max_element(all(v)) #define minall(v) *min_element(all(v)) #define cover(a,d) memset(a,d,sizeof(a)) #define popcount(i) __builtin_popcount(i) //count one #define input freopen("in.txt","r",stdin) #define output freopen("out.txt","w",stdout) #define un(v) ST(v), (v).earse(unique(all(v)),v.end()) #define common(a,b) ST(a), ST(b), a.erase(set_intersection(all(a),all(b),a.begin()),a.end()) #define uncommon(a,b) ST(a), ST(b), a.erase(set_symmetric_difference(all(a),all(b),a.begin()),a.end()) ////============ CONSTANT ===============//// #define mx (1000010) #define Max 1000000 //infinity value #define eps 1e-9 #define mod 10007 ////=====================================//// int main() { string s; int no=0; while(cin>>s) { if(s=="end") break; int len=s.size(); int a[10010]; for(int i=0;i<len;i++) { a[i]=s[i]-64; } int dp[10010]; for(int i=0;i<len;i++) { dp[i]=1;...

Uva 11790 – Murcia’s Skyline

Problem Link Solution :- Murcia's Skyline C++ /****************************************************************** *** Problem : Murcia's Skyline *** *** Author : Shipu Ahamed (Psycho Timekiller) *** *** E-mail : shipuahamed01@gmail.com *** *** University : BUBT,Dept. of CSE *** *** Team : BUBT_Psycho *** *** My Blog : http://shipuahamed.blogspot.com *** *** Facebook : http://www.facebook.com/DeesheharaShipu *** ******************************************************************/ #include <list> #include <set> #include <map> #include <ctime> #include <stack> #include <queue> #include <cmath> #include <deque> #include <limits> #include <string> #include <cctype> #include <cstdio> #include <vector> #include <bitset> #include <numeric> #include <cassert> #include <sstream> #include <fstream> #include <cstdlib> #include <cstring> #include <utility> #include <complex> #include <iomanip> #include <iostream> #include <iterator> #include <algorithm> using namespace std; #define sc scanf #define pf printf #define ll long long #define pi 2*acos(0.0) #define ull unsigned long long #define all(v) v.begin(),v.end() #define sii(t) scanf("%d",&t) #define sll(t) scanf("%lld",&t) #define ssii(a,b) scanf("%d%d",&a,&b) #define ssll(a,b) scanf("%lld%lld",&a,&b) #define Case(no) printf("Case %d. ",++no) #define nl puts("") #define P(a) printf("%dn",a) #define PL(a) printf("%lldn",a) #define PN(a) printf("%d ",a) #define PLN(a) printf("%lld ",a) #define CP(a) cout<<a<<endl; #define CPN(a) cout<<a<<" "; #define ff first #define se second #define pb push_back #define ST(v) sort(all(v)) #define gcd(a,b) __gcd(a,b) #define lcm(a,b) (a*(b/gcd(a,b))) #define max3(a,b,c) max(a,max(b,c)) #define min3(a,b,c) min(a,min(b,c)) #define maxall(v) *max_element(all(v)) #define minall(v) *min_element(all(v)) #define cover(a,d) memset(a,d,sizeof(a)) #define popcount(i) __builtin_popcount(i) //count one #define parity(i) __builtin_parity(i) //evenparity 0 and odd parity 1 #define input freopen("in.txt","r",stdin) #define output freopen("out.txt","w",stdout) #define un(v) ST(v), (v).earse(unique(all(v)),v.end()) #define common(a,b) ST(a), ST(b), a.erase(set_intersection(all(a),all(b),a.begin()),a.end()) #define uncommon(a,b) ST(a), ST(b), a.erase(set_symmetric_difference(all(a),all(b),a.begin()),a.end()) ////============ CONSTANT ===============//// #define mx (10010) #define inf 1<<30 //infinity value #define eps 1e-9 #define mod 10007 ////=====================================//// struct house { int h[mx],w[mx]; }; int lis(house a,int n) { int dp[mx]; for(int i=0;i<n;i++) { dp[i]=a.w[i];...

Uva 10130 – SuperSale

Problem Link Solution :- SuperSale C++ /*------------------------------------------------*/ //Problem Name : SuperSale //Uva Problem No : 10130 //Type : DP,knapsack //Author : Shipu Ahamed //University : BUBT //E-mail : shipuahamed01@gmail.com /*-----------------------------------------------*/ #include<algorithm> #include<iostream> #include<iterator> #include<cassert> #include<sstream> #include<fstream> #include<cstdlib> #include<cstring> #include<utility> #include<complex> #include<string> #include<cctype> #include<cstdio> #include<vector> #include<bitset> #include<stack> #include<queue> #include<cmath> #include<deque> #include<list> #include<set> #include<map> #define sc scanf #define pf printf #define ll long long #define pi 2*acos(0.0) #define ff first #define se second #define inf (1<<30) //infinity value #define pb push_back #define mod 1000000007 #define ST(v) sort(v.begin(),v.end()) #define cover(a,d) memset(a,d,sizeof(a)) #define input freopen("in.txt","r",stdin) #define output freopen("out.txt","w",stdout) #define maxall(v) *max_element(v.begin(),v.end()) #define minall(v) *min_element(v.begin(),v.end()) #define un(v) ST(v), v.erase(unique(v.begin(),v.end()),v.end()) using namespace std; int profit[1010][1010],value[1010],weight[1010]; int main() { int knapsack_weight,n,t; cin>>t; while(t--) { cin>>n; for(int i=1;i<=n;i++) { cin>>value[i]>>weight[i]; } int a,sum=0; cin>>a; cover(profit,0); for(int i=0;i<a;i++) { cin>>knapsack_weight; for(int i=1;i<=n;i++) { for(int w=1;w<=knapsack_weight;w++) { if(weight[i]>w) { profit[i][w] = profit[i-1][w]; } else { if(profit[i-1][w]>profit[i-1][w-weight[i]]+value[i]) { profit[i][w] = profit[i-1][w]; } else { profit[i][w] = profit[i-1][w-weight[i]]+value[i]; } } } } sum+=profit[n][knapsack_weight]; } pf("%dn",sum); } return 0; } 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697 /*------------------------------------------------*///Problem Name   : SuperSale//Uva Problem No : 10130//Type           : DP,knapsack//Author         : Shipu Ahamed//University     : BUBT//E-mail         : shipuahamed01@gmail.com/*-----------------------------------------------*/ #include<algorithm>#include<iostream>#include<iterator>#include<cassert>#include<sstream>#include<fstream>#include<cstdlib>#include<cstring>#include<utility>#include<complex>#include<string>#include<cctype>#include<cstdio>#include<vector>#include<bitset>#include<stack>#include<queue>#include<cmath>#include<deque>#include<list>#include<set>#include<map> #define sc scanf#define pf printf#define ll long long#define pi 2*acos(0.0) #define ff first#define se second#define inf (1<<30)                                              //infinity value#define pb push_back#define mod  1000000007#define ST(v) sort(v.begin(),v.end())#define cover(a,d) memset(a,d,sizeof(a))#define input freopen("in.txt","r",stdin)#define output freopen("out.txt","w",stdout)#define maxall(v) *max_element(v.begin(),v.end())#define minall(v) *min_element(v.begin(),v.end())#define un(v) ST(v), v.erase(unique(v.begin(),v.end()),v.end()) using namespace std;int profit[1010][1010],value[1010],weight[1010];int main(){      int knapsack_weight,n,t;     cin>>t;     while(t--)     {         cin>>n;         for(int i=1;i<=n;i++)         {             cin>>value[i]>>weight[i];         }         int a,sum=0;         cin>>a;         cover(profit,0);         for(int i=0;i<a;i++)         {             cin>>knapsack_weight;             for(int i=1;i<=n;i++)             {                for(int w=1;w<=knapsack_weight;w++)                {                    if(weight[i]>w)                    {                        profit[i][w] = profit[i-1][w];                        }                    else                    {                        if(profit[i-1][w]>profit[i-1][w-weight[i]]+value[i])                        {                            profit[i][w] = profit[i-1][w];                            }                         else                         {                            profit[i][w] = profit[i-1][w-weight[i]]+value[i];                            }                    }                 }              }              sum+=profit[n][knapsack_weight];         }         pf("%dn",sum);     }    return 0;}...

Uva 10405 – Longest Common Subsequence

Problem Link Solution :- Longest Common Subsequence C++ /*-------------------------------------------------*/ //Problem Setter: Piotr Rudnicki //Uva Problem No: 10405 //Problem Name : Longest Common Subsequence(LCS) //Type : DP, LCS //Author : Shipu Ahamed //University : BUBT //E-mail : shipu@programmer.net /*------------------------------------------------*/ #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<iostream> #include<cctype> #include<map> #include<stack> #include<cstdlib> #include <queue> #include <vector> #include<algorithm> #define ll long long #define sc scanf #define pf printf #define Pi 2*acos(0.0) using namespace std; int n,m,lcs[2000][2000]; int main() { string s1,s2; while(getline(cin,s1)) { getline(cin,s2); n=s1.size(); m=s2.size(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(s1[i-1]==s2[j-1]) lcs[i][j]=lcs[i-1][j-1]+1; else lcs[i][j]=max(lcs[i-1][j],lcs[i][j-1]); } cout<<lcs[n][m]<<endl; } return 0; } 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849 /*-------------------------------------------------*///Problem Setter: Piotr Rudnicki//Uva Problem No: 10405//Problem Name  : Longest Common Subsequence(LCS)//Type          : DP, LCS//Author        : Shipu Ahamed//University    : BUBT//E-mail        : shipu@programmer.net/*------------------------------------------------*/ #include<cstdio>#include<cstring>#include<string>#include<cmath>#include<iostream>#include<cctype>#include<map>#include<stack>#include<cstdlib>#include <queue>#include <vector>#include<algorithm>#define ll long long#define sc scanf#define pf printf#define Pi 2*acos(0.0)using namespace std;int n,m,lcs[2000][2000];int main(){    string s1,s2;     while(getline(cin,s1))    {        getline(cin,s2);        n=s1.size();        m=s2.size();        for(int i=1;i<=n;i++)            for(int j=1;j<=m;j++)            {                if(s1[i-1]==s2[j-1])                lcs[i][j]=lcs[i-1][j-1]+1;                else                lcs[i][j]=max(lcs[i-1][j],lcs[i][j-1]);            }        cout<<lcs[n][m]<<endl;    }return 0;}...

LightOJ 1033 – Generating Palindromes

Problem Link Solution :- C++ /*------------------------------------------------*/<br />//Problem Setter: MD. KAMRUZZAMAN<br />//Uva Problem No: 1033<br />//Problem Name : Generating Palindromes<br />//Type : Dynamic Programming<br />//Author : Shipu Ahamed<br />//University : BUBT<br />//E-mail : shipuahamed01@gmail.com<br />/*------------------------------------------------*/<br /><br />#include&lt;algorithm&gt;<br />#include&lt;iostream&gt;<br />#include&lt;iterator&gt;<br />#include&lt;cassert&gt;<br />#include&lt;sstream&gt;<br />#include&lt;fstream&gt;<br />#include&lt;cstdlib&gt;<br />#include&lt;cstring&gt;<br />#include&lt;utility&gt;<br />#include&lt;complex&gt;<br />#include&lt;string&gt;<br />#include&lt;cctype&gt;<br />#include&lt;cstdio&gt;<br />#include&lt;vector&gt;<br />#include&lt;bitset&gt;<br />#include&lt;stack&gt;<br />#include&lt;queue&gt;<br />#include&lt;cmath&gt;<br />#include&lt;deque&gt;<br />#include&lt;list&gt;<br />#include&lt;set&gt;<br />#include&lt;map&gt;<br /><br />#define ll long long<br />#define sc scanf<br />#define pf printf<br />#define pi 2*acos(0.0)<br /><br />#define ft first<br />#define se second<br />#define in freopen("in.txt","r",stdin)<br />#define out freopen("out.txt","w",stdout)<br />#define maxall(v) *max_element(v.begin(),v.end())<br />#define minall(v) *min_element(v.begin(),v.end())<br />#define Sort(v) sort(v.begin(),v.end())<br />#define cover(a,b) memset(a,b,sizeof(a))<br />#define un(v) Sort(v), v.erase(unique(v.begin(),v.end()),v.end())<br /><br />using namespace std;<br />string s;<br />int mem[200][200];<br />int pl(int i,int j)<br />{<br /> if(mem[i][j]!=-1) return mem[i][j];<br /> if(i&gt;=j) return 0;<br /> if(s[i]==s[j])<br /> return pl(i+1,j-1);<br /> else<br /> mem[i][j]=1+ min(pl(i,j-1),pl(i+1,j));<br /><br /> return mem[i][j];<br />}<br />int main()<br />{<br /> int t,no=0;<br /> cin&gt;&gt;t;<br /> while(t--)<br /> {<br /> cover(mem,-1);<br /> cin&gt;&gt;s;<br /> int l=s.size();<br /> pf("Case %d: %dn",++no,pl(0,l-1));<br /> }<br /> return 0;<br />}<br /> 1 /*------------------------------------------------*/<br />//Problem Setter: MD. KAMRUZZAMAN<br />//Uva Problem No: 1033<br />//Problem Name  : Generating Palindromes<br />//Type          : Dynamic Programming<br />//Author        : Shipu Ahamed<br />//University    : BUBT<br />//E-mail        : shipuahamed01@gmail.com<br />/*------------------------------------------------*/<br /><br />#include&lt;algorithm&gt;<br />#include&lt;iostream&gt;<br />#include&lt;iterator&gt;<br />#include&lt;cassert&gt;<br />#include&lt;sstream&gt;<br />#include&lt;fstream&gt;<br />#include&lt;cstdlib&gt;<br />#include&lt;cstring&gt;<br />#include&lt;utility&gt;<br />#include&lt;complex&gt;<br />#include&lt;string&gt;<br />#include&lt;cctype&gt;<br />#include&lt;cstdio&gt;<br />#include&lt;vector&gt;<br />#include&lt;bitset&gt;<br />#include&lt;stack&gt;<br />#include&lt;queue&gt;<br />#include&lt;cmath&gt;<br />#include&lt;deque&gt;<br />#include&lt;list&gt;<br />#include&lt;set&gt;<br />#include&lt;map&gt;<br /><br />#define ll long long<br />#define sc scanf<br />#define pf printf<br />#define pi 2*acos(0.0)<br /><br />#define ft first<br />#define se second<br />#define in freopen("in.txt","r",stdin)<br />#define out freopen("out.txt","w",stdout)<br />#define maxall(v) *max_element(v.begin(),v.end())<br />#define minall(v) *min_element(v.begin(),v.end())<br />#define Sort(v) sort(v.begin(),v.end())<br />#define cover(a,b) memset(a,b,sizeof(a))<br />#define un(v) Sort(v), v.erase(unique(v.begin(),v.end()),v.end())<br /><br />using namespace std;<br />string s;<br />int mem[200][200];<br />int pl(int i,int j)<br />{<br...