vsanjayvyas

SPOJ – ABA12C – Buying Apples!

#include<stdio.h>
typedef long long ll;
ll min(ll a,ll b)
{
 if(a<=b)
 return a;
 else return b;
}
int main()
{
 ll t,n,k;
 scanf("%lld",&t);
 ll dp[102];
 ll ar[102];
 while(t--)
 {
 scanf("%lld%lld",&n,&k);
 for(ll i=1;i<=k;i++)
 scanf("%lld",&ar[i]);
 for(ll i=1;i<=k;i++)
 dp[i]=-1;
 dp[0]=0;
 for(ll i=1;i<=k;i++)
 {
 for(ll j=1;j<=k;j++)
 {
 if(i>=j)
 {
 if(dp[i]==-1 && dp[i-j]!=-1 && ar[j]!=-1)
 dp[i]=ar[j]+dp[i-j];
 else if(dp[i-j]!=-1 && ar[j]!=-1)
 dp[i]=min(dp[i],ar[j]+dp[i-j]);
 
 }
 }
 }
 if(dp[k]!=-1)
 printf("%lld\n",dp[k]);
 else
 printf("-1\n");
}
return 0;
}
vsanjayvyas

SPOJ – ABA12C – Buying Apples!

#include<stdio.h>
#define INF 1000000000000
typedef long long ll;
ll min(ll a,ll b)
{
 if(a>=b)
 return b;
 else
 return a;
}
ll dp[103][103];
int main()
{
 ll t,n,k;
 ll p[103];
 scanf("%lld",&t);
 while(t--)
 {
 scanf("%lld%lld",&n,&k);
 for(ll i=1;i<=k;i++)
 scanf("%lld",&p[i]);
 for(ll i=0;i<=k;i++)
 dp[i][0]=INF;
 for(ll i=1;i<=k;i++)
 {
 for(ll j=1;j<=k;j++)
 dp[i][j]=INF;
 }
 for(ll i=0;i<=k;i++)
 dp[0][i]=0;
 dp[0][0]=0;
 for(ll i=1;i<=k;i++)
 {
 for(ll j=1;j<=k;j++)
 {
 dp[i][j]=-1;
 if(j>i || p[j]==-1)
 dp[i][j]=dp[i][j-1];
 else
 {
 if(dp[i-j][j]!=INF)
 dp[i][j]=min(dp[i][j-1],p[j]+dp[i-j][j]);
 }
 
 }
 }
 if(dp[k][k]!=-1)
 printf("%lld\n",dp[k][k]);
 else
 printf("-1\n");
 }
 return 0;
}
vsanjayvyas

SPOJ -PIGBANK – Piggy-Bank

#include<stdio.h>
typedef long long ll;
ll min(ll a,ll b)
{
 if(a<=b)
 return a;
 else return b;
}
int main()
{
 ll t,a,b;
 ll v[505],w[505];
 scanf("%lld",&t);
 ll dp[10002];
 while(t--)
 {
 scanf("%lld%lld",&a,&b);
 ll n;
 ll k=b-a;
 scanf("%lld",&n);
 for(ll i=1;i<=n;i++)
 scanf("%lld%lld",&v[i],&w[i]);
 for(ll i=1;i<=k;i++)
 dp[i]=-1;
 for(ll i=1;i<=k;i++)
 {
 for(ll j=1;j<=n;j++)
 {
 if(i>=w[j])
 {
 if(dp[i]==-1 && dp[i-w[j]]!=-1)
 dp[i]=v[j]+dp[i-w[j]];
 else if(dp[i-w[j]]!=-1)
 dp[i]=min(dp[i],v[j]+dp[i-w[j]]);
 }
 }
 }
 if(dp[k]==-1)
 printf("This is impossible.\n");
 else 
 printf("The minimum amount of money in the piggy-bank is %lld.\n",dp[k]);
 }
 return 0;
}
vsanjayvyas

SPOJ – RPLC – Coke madness

#include<stdio.h>
typedef long long ll;
ll ar[1000002];
int main()
{
 ll t,n,i,f=1;
 scanf("%lld",&t);
 while(t--)
 {
 scanf("%lld",&n);
 for(i=0;i<n;i++)
 scanf("%lld",&ar[i]);
 ll ans=0;
 ll sum=0;
 for(i=0;i<n;i++)
 {
 sum=sum+ar[i];
 if(sum<=0)
 {
 ans=ans+((-1)*sum)+1;
 sum=1;
 }
 }
 if(ans==0)
 ans++;
 printf("Scenario #%lld: %lld\n",f++,ans);
 }
 return 0;
}
vsanjayvyas

SPOJ – RPLB – Blueberries

#include<stdio.h>
typedef int ll;
ll max(ll a,ll b)
{
 if(a>b)
 return a;
 else return b;
}
ll bb[1002];
ll dp[1002][1002];
int main()
{
 ll t,n,k,f=1;
 scanf("%lld",&t);
 while(t--)
 {
 scanf("%d%d",&n,&k);
 for(ll i=2;i<=n+1;i++)
 scanf("%d",&bb[i]);
 for(ll i=2;i<=n+1;i++)
 {
 for(ll j=0;j<=k;j++)
 {
 if(j==0)
 dp[i][j]=0;
 else
 {
 if(bb[i]<=j)
 dp[i][j]=max(bb[i]+dp[i-2][j-bb[i]],dp[i-1][j]);
 else
 dp[i][j]=dp[i-1][j];
 }
 }
 }
 printf("Scenario #%d: %d\n",f++,dp[n+1][k]);
}
 return 0;
}
vsanjayvyas

SPOJ – LKS – Large Knapsack

#include<stdio.h>
typedef int ll;
ll max(ll a,ll b)
{
 if(a>b)
 return a;
 else return b;
}
ll ts,n;
ll w[505],v[505];
ll dp[2][2000002];
int main()
{
 scanf("%d%d",&ts,&n);
 ll i;
 for(i=1;i<=n;i++)
 scanf("%d%d",&v[i],&w[i]);
 ll j;
 ll cur=1,prev=0;
 for(i=1;i<=n;i++)
 {
 for(j=0;j<=ts;j++)
 {
 if(j==0)
 dp[cur][j]=0;
 else
 {
 if(w[i]<=j)
 dp[cur][j]=max(v[i]+dp[prev][j-w[i]],dp[prev][j]);
 else
 dp[cur][j]=dp[prev][j];
 }
 }
 cur=1-cur;
 prev=1-prev;
 }
 printf("%d\n",dp[n&1][ts]);
}
vsanjayvyas

SPOJ – KNAPSACK – The Knapsack Problem

  1. #include<stdio.h>
    #include<iostream>
    #include<string>
    #define sci(x) scanf(“%d”,&x)
    #define scll(x) scanf(“%lld”,&x)
    #define pfi(x) printf(“%d”,x)
    #define pfll(x) printf(“%lld”,x)
    #define ch(x) scanf(“%c”,&x)
    using namespace std;
    typedef long long ll;
    /*float stof(const string& str, size_t *idx = 0);
    double stod(const string& str, size_t *idx = 0);
    long double stold(const string& str, size_t *idx = 0);
    int stoi(const string& str, size_t *idx = 0, int base = 10);
    long stol(const string& str, size_t *idx = 0, int base = 10);
    unsigned long stoul(const string& str, size_t *idx = 0, int base = 10);
    long long stoll(const string& str, size_t *idx = 0, int base = 10);
    unsigned long long stoull(const string& str, size_t *idx = 0, int base = 10); */
    ll max(ll a,ll b)
    {
    if(a>b)
    return a;
    else
    return b;
    }
    ll n;
    ll dp[2002][2002];
    ll s[2003];
    ll v[2003];
    ll ks(ll idx,ll rs)
    {
    if(idx==n || rs==0)
    return 0;
    if(dp[idx][rs]!=-1)
    return dp[idx][rs];
    if(s[idx]<=rs)
    return dp[idx][rs]=max(v[idx]+ks(idx+1,rs-s[idx]),ks(idx+1,rs));
    if(s[idx]>rs)
    return dp[idx][rs]=ks(idx+1,rs);
    }
    int main()
    {
    ll si;
    scll(si);
    scll(n);
    ll i,j;
    for(i=0;i<=2000;i++)
    {
    for(j=0;j<=2000;j++)
    dp[i][j]=-1;
    }
    for(i=0;i<n;i++)
    {
    scll(s[i]);scll(v[i]);
    }
    ll k=ks(0,si);
    pfll(k);
    return 0;
    }

     

vsanjayvyas

SPOJ – WACHOVIA – Wachovia Bank

  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<string>
  4. #define sci(x) scanf(“%d”,&x)
  5. #define scll(x) scanf(“%lld”,&x)
  6. #define pfi(x) printf(“%d”,x)
  7. #define pfll(x) printf(“%lld”,x)
  8. #define ch(x) scanf(“%c”,&x)
  9. using namespace std;
  10. typedef long long ll;
  11. /*float stof(const string& str, size_t *idx = 0);
  12. double stod(const string& str, size_t *idx = 0);
  13. long double stold(const string& str, size_t *idx = 0);
  14. int stoi(const string& str, size_t *idx = 0, int base = 10);
  15. long stol(const string& str, size_t *idx = 0, int base = 10);
  16. unsigned long stoul(const string& str, size_t *idx = 0, int base = 10);
  17. long long stoll(const string& str, size_t *idx = 0, int base = 10);
  18. unsigned long long stoull(const string& str, size_t *idx = 0, int base = 10); */
  19. ll max(ll a,ll b)
  20. {
  21. if(a>b)
  22. return a;
  23. else
  24. return b;
  25. }
  26. ll n;
  27. ll dp[52][1002];
  28. ll s[2003];
  29. ll v[2003];
  30. ll ks(ll idx,ll rs)
  31. {
  32. if(idx==n || rs==0)
  33. return 0;
  34. if(dp[idx][rs]!=-1)
  35. return dp[idx][rs];
  36. if(s[idx]<=rs)
  37. return dp[idx][rs]=max(v[idx]+ks(idx+1,rs-s[idx]),ks(idx+1,rs));
  38. if(s[idx]>rs)
  39. return dp[idx][rs]=ks(idx+1,rs);
  40. }
  41. int main()
  42. {
  43. ll si;ll t;
  44. scll(t);
  45. while(t–)
  46. {
  47. scll(si);
  48. scll(n);
  49. ll i,j;
  51. for(i=0;i<=50;i++)
  52. {
  53. for(j=0;j<=1000;j++)
  54. dp[i][j]=-1;
  55. }
  56. for(i=0;i<n;i++)
  57. {
  58. scll(s[i]);scll(v[i]);
  59. }
  60. ll k=ks(0,si);
  61. printf(“Hey stupid robber, you can get %lld.\n“,k);
  62. }
  63. return 0;
  64. }
vsanjayvyas

SPOJ – PARTY – Party Schedule

  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<string>
  4. #define sci(x) scanf(“%d”,&x)
  5. #define scll(x) scanf(“%lld”,&x)
  6. #define pfi(x) printf(“%d”,x)
  7. #define pfll(x) printf(“%lld”,x)
  8. #define ch(x) scanf(“%c”,&x)
  9. using namespace std;
  10. typedef long long ll;
  11. /*float stof(const string& str, size_t *idx = 0);
  12. double stod(const string& str, size_t *idx = 0);
  13. long double stold(const string& str, size_t *idx = 0);
  14. int stoi(const string& str, size_t *idx = 0, int base = 10);
  15. long stol(const string& str, size_t *idx = 0, int base = 10);
  16. unsigned long stoul(const string& str, size_t *idx = 0, int base = 10);
  17. long long stoll(const string& str, size_t *idx = 0, int base = 10);
  18. unsigned long long stoull(const string& str, size_t *idx = 0, int base = 10); */
  19. ll max(ll a,ll b)
  20. {
  21. if(a>b)
  22. return a;
  23. else
  24. return b;
  25. }
  26. ll n;
  27. ll dp[101][502];
  28. ll s[2003];
  29. ll v[2003];
  30. ll ks(ll idx,ll rs)
  31. {
  32. if(idx==n || rs==0)
  33. return 0;
  34. if(dp[idx][rs]!=-1)
  35. return dp[idx][rs];
  36. if(s[idx]<=rs)
  37. return dp[idx][rs]=max(v[idx]+ks(idx+1,rs-s[idx]),ks(idx+1,rs));
  38. if(s[idx]>rs)
  39. return dp[idx][rs]=ks(idx+1,rs);
  40. }
  42. int main()
  43. {
  44. ll si;
  45. while(scanf(“%lld%lld”,&si,&n) && (si!=0 || n!=0))
  46. {
  47. ll i,j;
  49. for(i=0;i<=100;i++)
  50. {
  51. for(j=0;j<=500;j++)
  52. dp[i][j]=-1;
  53. }
  54. for(i=0;i<n;i++)
  55. {
  56. scll(s[i]);scll(v[i]);
  57. }
  58. ll k=ks(0,si);
  59. ll low=0,high=si,mid;
  60. while(low<high)
  61. {
  62. mid=(low+high)/2;
  63. if(ks(0,mid)<k)
  64. low=mid+1;
  65. else
  66. high=mid;
  67. }
  68. printf(“%lld %lld\n“,high,k);
  69. }
  70. return 0;
  71. }
vsanjayvyas

SPOJ – ABSYS- Anti-Blot System

#include<stdio.h>
#include<iostream>
#include<string>
using namespace std;
typedef long long ll;
/*float stof(const string& str, size_t *idx = 0);
double stod(const string& str, size_t *idx = 0);
long double stold(const string& str, size_t *idx = 0);
int stoi(const string& str, size_t *idx = 0, int base = 10);
long stol(const string& str, size_t *idx = 0, int base = 10);
unsigned long stoul(const string& str, size_t *idx = 0, int base = 10);
long long stoll(const string& str, size_t *idx = 0, int base = 10);
unsigned long long stoull(const string& str, size_t *idx = 0, int base = 10); */
int main()
{
 string a,b,c;
 char a1,b1;
 ll t;
 cin >>t;
 while(t--)
 {
 cin >>a>>a1>>b>>b1>>c;
 ll k,i;
 for(i=0;i<a.size();i++)
 {
 if(a[i]=='m')
 {
 k=0;
 break;
 }
 
 }
 for(i=0;i<b.size();i++)
 {
 if(b[i]=='m')
 {
 k=1;
 break;
 }
 
 }
 for(i=0;i<c.size();i++)
 {
 if(c[i]=='m')
 {
 k=2;
 break;
 }
 
 }
 if(k==0)
 cout << stoll(c)-stoll(b)<< " + "<<b<< " = "<< c << endl;
 else if(k==1)
 cout << a<< " + "<<stoll(c)-stoll(a)<< " = "<<c<< endl;
 else cout << a<< " + "<<b<< " = "<<stoll(a)+stoll(b)<< endl;
 }
 return 0;
}