Spoj 3693 – Maximum Sum

Problem Link Solution :- Maximum Sum C++ /****************************************************************** *** Problewm : Spoj 3693. Maximum Sum *** *** 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 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 (100010) #define inf 1000000000 //infinity value #define eps 1e-9 #define mod 10007 ////=====================================//// struct knw { int maxi,position; }sum[mx*4],base; int a[mx]; void update(int node,int s,int e,int i,int value) { if(i>e||i<s) return; if(s==e) { sum[node].maxi=value; sum[node].position=i; return; } int n=node<<1; int mid=(s+e)>>1; update(n,s,mid,i,value); update(n+1,mid+1,e,i,value); if(sum[n].maxi>sum[n+1].maxi) {...

Spoj 61 – Brackets

Problem Link Solution :- Brackets C++ /****************************************************************** *** Problewm : Spoj 61. Brackets *** *** 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("Test %d:n",++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 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 (30010) #define Max 1000000 //infinity value #define eps 1e-9 #define mod 10007 ////=====================================//// int sum[mx*4],a[mx*4]; void update(int node,int s,int e,int i,int value) { if(i>e||i<s) return; if(s==e) { sum[node]=value; a[node]=value; return; } int n=node<<1; int mid=(s+e)>>1; update(n,s,mid,i,value); update(n+1,mid+1,e,i,value); sum[node]=sum[n]+sum[n+1]; a[node]=a[n]; a[node]=min(sum[n]+a[n+1],a[node]); } int main() { int n,no=0; while(sii(n)==1)...

Spoj 3267 – D-query

Problem Link Solution :- D-query C++ /****************************************************************** *** Problewm : Spoj 3267. D-query *** *** 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 <bits/stdc++.h> using namespace std; #define for0(i,n) for(int i=0;i<n;i++) #define for1(i,n) for(int i=1;i<=n;i++) #define rfor0(i,n) for(int i=n;i>=0;i--) #define rfor1(i,n) for(int i=n;i>=1;i--) #define forse(i,a,b) for(int i=a;i<=b;i++) #define ll long long #define pi 2*acos(0.0) #define all(v) v.begin(),v.end() #define si(t) scanf("%d",&t) #define sl(t) scanf("%lld",&t) #define sf(t) scanf("%f",&t) #define sdb(t) scanf("%lf",&t) #define schar(c) scanf("%c",&c) #define sstring(s) scanf("%s",s) #define ssi(a,b) scanf("%d%d",&a,&b) #define ssl(a,b) scanf("%lld%lld",&a,&b) #define P(a) printf("%dn",a) #define PL(a) printf("%lldn",a) #define PF(a) printf("%fn",a) #define PDB(a) printf("%lfn",a) #define PN(a) printf("%d ",a) #define PLN(a) printf("%lld ",a) #define PFN(a) printf("%f ",a) #define PDBN(a) printf("%lf ",a) #define CP(a) cout<<a<<endl #define CPN(a) cout<<a<<" " #define Case(no) printf("Case %d: ",++no) #define nl puts("") #define db(x) cout << #x << " -> " << (x) << endl; #define db_sarr(i,a) cout<<#a<<"["<<i<<"] -> "<<a[i]<<" "<<endl; #define db_arr(a,start,end) for(ll i=start;i<=end;i++) cout<<#a<<"["<<i<<"] -> "<<a[i]<<" "<<endl; #define db_mat(mat,row,col) for(ll i=0;i<row;i++) {for(ll j=0;j<col;j++) cout<<mat[i][j]<<" ";cerr<<endl;} #define ff first #define se second #define pb push_back #define ppb pop_back #define mkp(a,b) make_pair(a,b) #define ST(v) sort(all(v)) #define sz(x) (int)x.size() #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()) typedef vector<int> vi; typedef vector<ll> vl;...

Spoj 13753 – Amazing Prime Sequence

Problem Link Solution :- Amazing Prime Sequence C++ /****************************************************************** *** Problem No : Spoj 13753 *** *** Problem Name : Amazing Prime Sequence *** *** Type : Number theory , prime *** *** Author : Shipu Ahamed (Psycho Timekiller) *** *** E-mail : shipuahamed01@gmail.com *** *** University : BUBT,Dept. of CSE *** *** Team : BUBT_Psycho *** *** Facebook : http://www.facebook.com/DeesheharaShipu *** ******************************************************************/ #include <bits/stdc++.h> using namespace std; #define ll long long #define pi 2*acos(0.0) #define all(v) v.begin(),v.end() //For Define #define for0(i,n) for(__typeof(n) i=0;i<(n);i++) #define for1(i,n) for(__typeof(n) i=1;i<=(n);i++) #define rfor0(i,n) for(__typeof(n) i=(n);i>=0;i--) #define rfor1(i,n) for(__typeof(n) i=(n);i>=1;i--) #define For(i,a,b) for(__typeof(b) i=a;i<=b;i++) //input #define si(t) scanf("%d",&t) #define sl(t) scanf("%lld",&t) #define sf(t) scanf("%f",&t) #define sdb(t) scanf("%lf",&t) #define schar(c) scanf("%c",&c) #define sstring(s) scanf("%s",s) #define ssi(a,b) scanf("%d%d",&a,&b) #define ssl(a,b) scanf("%lld%lld",&a,&b) //Output #define P(a) printf("%dn",a) #define PL(a) printf("%lldn",a) #define PF(a) printf("%fn",a) #define PDB(a) printf("%lfn",a) #define PN(a) printf("%d ",a) #define PLN(a) printf("%lld ",a) #define PFN(a) printf("%f ",a) #define PDBN(a) printf("%lf ",a) #define CP(a) cout<<a<<endl #define CPN(a) cout<<a<<" " //Test Case & New line #define Case(no) printf("Case %d: ",++no) #define nl puts("") //Debug #define db(x) cout << #x << " -> " << (x) << endl; #define db_sarr(i,a) cout<<#a<<"["<<i<<"] -> "<<a[i]<<" "<<endl; #define db_arr(a,start,end) for(ll i=start;i<=end;i++) cout<<#a<<"["<<i<<"] -> "<<a[i]<<" "<<endl; #define db_mat(mat,row,col) for(ll i=0;i<row;i++) {for(ll j=0;j<col;j++) cout<<mat[i][j]<<" ";cerr<<endl;} #define db_st(a,b,start,end) for(ll i=start;i<=end;i++) cout<<#a<<"["<<i<<"]."<<#b<<" -> "<<a[i].b<<" "<<endl; #define ff first #define se second #define pb push_back #define ppb pop_back #define mkp(a,b) make_pair(a,b) #define ST(v) sort(all(v)) #define sz(x) (int)x.size() #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...

Spoj 14863 – Summation of Multiples

Problem Link    খুবই সুন্দর একটা প্রবলেম আর সহজও তবুও আমি সমাধানটা ব্যাখ্যা করছি কারণ কিছু ট্রিক্স অনেকে অজানা থাকতে পারে তাই লিখলাম । ১-১০০ পর্যন্ত সবাই যোগ করার সূত্রটা জানো তারপরও দেখিয়ে দিচ্ছি : 1 + 2 + 3 + … + n = (n*(n+1))/2 ধর আমি ১-১০০০ পর্যন্ত ৩ ও ৫ এর মাল্টিপলগুলার Sum কত সেটা জানতে চাই । তার মানে ৩ আর ৫ এর মাল্টিপলগুলা বের করে যোগ করে দিলেই হচ্ছে তাই তো আর এটা আমাকে For loop নাহ চালিয়ে বের করতে হবে কারণ মূল প্রবলেমে N এর মান  ১০৯ পর্যন্ত হতে পারে আর ১০৯ পর্যন্ত লুপ চললে তো হইছেই কাম । logic টা হল ৩ এর সব মাল্টিপলগুলা যোগ করে রাখব N এর নিচের সংখ্যা পর্যন্ত । তারপর একিভাবে ৫ ও ১৫ এর সব মাল্টিপলগুলা যোগ করে রাখব N এর নিচের সংখ্যা পর্যন্ত । ১৫ কেন রাখব কারণ তুমি এমন কিছু সংখ্যাও যোগ করে ফেলেছ যেগুলা কিনা ২ বার যোগ হয়েছে একবার ৫ এ আরেকবার ৩ এ So সেগুলা বাদ দেয়ার জন্য ৩*৫ = ১৫ এর মাল্টিপলগুলার Sum দরকার । Sum of all numbers <1000 divisible by 3: 3 + 6 + 9 + … + 999 = 3 * (1 + 2 + 3 + … + 333) = (3 * (333*334))/2 = 166833 Sum of all numbers <1000 divisible by 5: 5 + 10 + 15 + … + 995 = 5 * (1 + 2 + 3 + … + 199) = (5 * (199*200))/2 = 99500 Sum of all numbers <1000 divisible by 15: 15 + 30 + 45 + … + 990 = 15 * (1 + 2 + 3 + … + 66) = (15 * (66*67))/2...