বৃহস্পতিবার, ৩১ মে, ২০১৮

UVA 10534 - Wavio Sequence

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
main()
{
    long n;
    while(cin>>n)
    {
        long i,ar[10006]= {0};
        vector<long>vec;
        long lis[10006],x=0,low=0,lds[10006];
        for(i=0; i<n; i++)
        {
            cin>>ar[i];
        }
        lis[0]=1,x=1;
        vec.push_back(ar[0]);
        for(i=1;i<n;i++)
        {
            if(ar[i]>vec.back())
            {
                vec.push_back(ar[i]);
                lis[i]=++x;
            }
            else
            {
                low=lower_bound(vec.begin(),vec.end(),ar[i])-vec.begin();
                vec[low]=ar[i];
                lis[i]=low+1;
            }
        }
        vec.clear();
        lds[n-1]=1;
        x=1;
        vec.push_back(ar[n-1]);
        for(i=n-2;i>=0;i--)
        {
            if(ar[i]>vec.back())
            {
                vec.push_back(ar[i]);
                lds[i]=++x;
            }
            else
            {
                low=lower_bound(vec.begin(),vec.end(),ar[i])-vec.begin();
                vec[low]=ar[i];
                lds[i]=low+1;
            }
        }
        long mn,mx=0;
        for(i=0;i<n;i++)
        {
           // cout<<lis[i]<<" "<<lds[i]<<endl;
            mn=min(lis[i],lds[i]);
            mx=max(mx,mn);
        }
        //cout<<mx<<endl;
        cout<<2*mx-1<<endl;
    }
}

এই সময়ে কোন মন্তব্য নেই:

Maximum Subarray Sum solution and their range

ম্যাক্সিমাম সাবঅ্যারে  সাম বের করার কোডঃ

Input
10
4   -5   4   -3   4   4   -4   4   -5
Output:
maximum sum=9 between 3 to 8 position

Input:
4
-2  -3 -5
Output:
Maximum sum is negative or zero

Input:
3
-1  6
Output:
maximum sum=6 between 2 to 2 position


///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
main()
{
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        long n,i,mx=0,j,ar[20005]={0},fst=1,scnd=-1,p=1,sum=0;
        cin>>n;
        for(i=1;i<n;i++)
        {
            cin>>ar[i];
        }
        for(i=1;i<n;i++)
        {
            sum+=ar[i];
            if(sum<0)
            {
                sum=0;
                p=i+1;
            }
            else if(sum>mx)
            {
                mx=sum;
                fst=p;
                scnd=i;
            }
            else if(sum==mx&&i-p>scnd-fst)
            {
                mx=sum;
                fst=p;
                scnd=i;
            }
        }
        if(mx<=0)
        {
            printf("Maximum sum is negative or zero\n");
        }
        else
        {
            printf("Maximum sum is =%ld is between stops %ld and %ld\n",mx,fst,scnd);
        }
    }
}

এই সময়ে কোন মন্তব্য নেই:

UVA 507 - Jill Rides Again

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
main()
{
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        long n,i,mx=0,j,ar[20005]={0},fst=1,scnd=-1,p=1,sum=0;
        cin>>n;
        for(i=1;i<n;i++)
        {
            cin>>ar[i];
        }
        for(i=1;i<n;i++)
        {
            sum+=ar[i];
            if(sum<0)
            {
                sum=0;
                p=i+1;
            }
            else if(sum>mx)
            {
                mx=sum;
                fst=p;
                scnd=i;
            }
            else if(sum==mx&&i-p>scnd-fst)
            {
                mx=sum;
                fst=p;
                scnd=i;
            }
        }
        if(mx<=0)
        {
            printf("Route %ld has no nice parts\n",cs++);
        }
        else
        {
            printf("The nicest part of route %ld is between stops %ld and %ld\n",cs++,fst,scnd+1);
        }
    }
}

এই সময়ে কোন মন্তব্য নেই:

বুধবার, ৩০ মে, ২০১৮

UVA 10341 - Solve It

#include<bits/stdc++.h>
using namespace std;
long p,q,r,s,t,u;
#define EPS 1e-7
double f(double x)
{
    return  p*exp(-x) + q*sin(x) + r*cos(x) + s*tan(x) + t*x*x + u;
}
double binary__search()
{
    double low=0.0,high=1.0;
    while(high>(low+EPS))
    {
        //cout<<low<<" "<<high<<endl;
        double mid=(low+high)/2.0;
        if(f(low)*f(mid)<=0)
        {
            high=mid;
        }
        else
            low=mid;
    }
    return (low+high)/2;
}
main()
{
    while(cin>>p>>q>>r>>s>>t>>u)
    {
        if(f(0)*f(1)>0)
        {
            printf("No solution\n");
        }
        else
        {
            printf("%.4f\n",binary__search());
        }
    }
}

এই সময়ে কোন মন্তব্য নেই:

মঙ্গলবার, ২৯ মে, ২০১৮

UVA 497 - Strategic Defense Initiative

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
long dp[1000],ar[1000],dir[1000];
long lisb(long u,long n)
{
    long mxx=0,v,l;
    if(dp[u]!=-1)
        return dp[u];
    for(v=u+1;v<n;v++)
    {
        if(ar[v]>ar[u])
        {
            l=lisb(v,n);
            if(l>mxx)
            {
                mxx=l;
                dir[u]=v;
            }
        }
    }
    dp[u]=mxx+1;
    return dp[u];
}
main()
{
    long ts,cs=0;
    cin>>ts;
    getchar();
    getchar();
    while(ts--)
    {
        if(cs==1)
            cout<<endl;
        cs=1;
        long k=0,i;
        string s;
        while(getline(cin,s))
        {
            if(s[0]=='\0'&&s.size()==0)
                break;
            ar[k++]=atoi(s.c_str());
        }
        memset(dp,-1,sizeof(dp));
        memset(dir,-1,sizeof(dir));
        long length,mx=0,start=0;
        for(i=0;i<k;i++)
        {
            length=lisb(i,k);
            if(length>mx)
            {
                mx=length;
                start=i;
            }
        }
        cout<<"Max hits: ";
        cout<<mx<<endl;
        cout<<ar[start]<<endl;
        while(dir[start]!=-1)
        {
            cout<<ar[dir[start]]<<endl;
            start=dir[start];
        }
    }
}

এই সময়ে কোন মন্তব্য নেই:

UVA 111 - History Grading

//...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
long ar[25],br[25],dp[25][25],n;
long lcs(long i1,long j1)
{
    if(i1==n||j1==n)
    {
        return 0;
    }
    if(dp[i1][j1]!=-1)
    {
        return dp[i1][j1];
    }
    long ans=0;
    if(ar[i1]==br[j1])
    {
        ans=1+lcs(i1+1,j1+1);
    }
    else
    {
        ans=max(lcs(i1+1,j1),lcs(i1,j1+1));
    }
    dp[i1][j1]=ans;
    return dp[i1][j1];
}
main()
{
   while(cin>>n)
   {
       long i,fst;
       for(i=0;i<n;i++)
       {
           cin>>fst;
           ar[fst-1]=i;
       }
       while(cin>>fst)
       {
           br[fst-1]=0;
           memset(dp,-1,sizeof(dp));
           for(i=1;i<n;i++)
           {
               cin>>fst;
               br[fst-1]=i;
           }
           cout<<lcs(0,0)<<endl;
       }
   }
}

এই সময়ে কোন মন্তব্য নেই:

সোমবার, ২৮ মে, ২০১৮

UVA 10465 - Homer Simpson

//...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
main()
{
    long n,m,t;
    while(cin>>n>>m>>t)
    {
        long ans=0,i,x,xx,tot,total=0,ar[100005];
        memset(ar,-1,sizeof(ar));
        for(i=0; i<=(t/n); i++)
        {
            xx=i*n;
            x=t-xx;
            if(x/m==0)
                break;
            tot=(x/m)+i;
            total=((x/m)*m)+(i*n);
            ar[total]=max(ar[total],tot);
            if(t==total)
                ans=max(ans,tot);
        }
        for(i=0; i<=(t/m); i++)
        {
            xx=i*m;
            x=t-xx;
            if(x/n==0)
                break;
            tot=(x/n)+i;
            total=((x/n)*n)+(i*m);
            ar[total]=max(ar[total],tot);
            if(t==total)
                ans=max(ans,tot);
        }
        if(ans==0)
        {
            long f=0;
            for(i=t-1;i>=0;i--)
            {
                if(ar[i]>=0)
                {
                    f=1;
                    cout<<ar[i]<<" "<<t-i<<endl;
                    break;
                }
            }
            if(f==0)
            {
                cout<<0<<" "<<t<<endl;
            }

        }
        else
            cout<<ans<<endl;
    }
}

এই সময়ে কোন মন্তব্য নেই:
এতে সদস্যতা: পোস্টগুলি (Atom)

Factory Pattern

Factory Method  is a creational design pattern that provides an interface for creating objects in a superclass but allows subclasses to alte...

  • LOJ 1348 - Aladdin and the Return Journey
    এখানে একটা গ্রাফ দেওয়া থাকবে এখন দুইটা অপারেশন দেবে অপারেসনে বলবে যে ১ দিলে i নাম্বার নোডে  V আপডেট হবে আর ০ দিলে i to j এর মধ্যে  টোটাল ...
  • Compute sum of digits in all numbers from 1 to n
    Sum of digits of a range(suppose 1-10 ans is 46,1-9 ans is 45) #include<stdio.h> #include<algorithm> #include<iostream...
  • UVA 147 - Dollars
    #include<bits/stdc++.h> using namespace std; long long coin[]= {10000,5000,2000,1000,500,200,100,50,20,10,5}; long long  dp[12][30...