UVA 1213 - Sum of Different Primes

///...................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("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pf(a) printf("%d",a)
#define pf2(a,b) printf("%d %d",a,b)
#define pf3(a,b,c) printf("%d %d %d",a,b,c)
#define sfl(a) scanf("%lld",&a)
#define sfl2(a,b) scanf("%lld %lld",&a,&b)
#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pfl(a) printf("%lld",a)
#define pfl2(a,b) printf("%lld %lld",a,b)
#define pfl3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#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++)
#define tz 100000
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//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
int vis[1500];
vector<int>vec;
void sieve()
{
    int i,j;
    for(i=2;i<=1129;i++)
    {
        if(vis[i]==0)
        {
            vec.push_back(i);
            for(j=2*i;j<=1129;j+=i)
            {
                vis[j]=1;
            }
        }
    }
}
int ways[1130][16];
void precalc()
{
    for(int n=0;n<=1120;n++)
    {
        for(int k=0;k<=14;k++)
        {
            ways[n][k]=0;
        }
    }
    ways[0][0]=1;
    for(int i=0;i<vec.size();i++)
    {
        for(int n=1120;n>=vec[i];n--)
        {
            for(int k=1;k<=14;k++)
            {
                ways[n][k]+=(ways[n-vec[i]][k-1]);
            }
        }
    }
}
main()
{
    sieve();
    //cout<<vec.size()<<endl;
    precalc();
    int n,k;
    while(cin>>n>>k)
    {
        if(n==0&&k==0)
            break;
        cout<<ways[n][k]<<endl;
    }
}

UVA 1246 - Find Terrorists

///...................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("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pf(a) printf("%d",a)
#define pf2(a,b) printf("%d %d",a,b)
#define pf3(a,b,c) printf("%d %d %d",a,b,c)
#define sfl(a) scanf("%lld",&a)
#define sfl2(a,b) scanf("%lld %lld",&a,&b)
#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pfl(a) printf("%lld",a)
#define pfl2(a,b) printf("%lld %lld",a,b)
#define pfl3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#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++)
#define tz 100000
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//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
int vis[1003];
int divisor[10005];
vector<int>vec;
void sieve()
{
    int i,j,k;
    vis[1]=1;
    vis[0]=1;
    int sz=1003;
    for(i=2; i<=1003; i++)
    {
        if(vis[i]==0)
        {
            for(j=2*i;j<=sz;j+=i)
            {
                //cout<<j<<endl;
                vis[j]=1;
            }
        }
    }
    divisor[0]=0;
    for(i=1;i<=10005;i++)
    {
        int nm=i,cnt=0;
        for(j=1;j<=sqrt(nm);j++)
        {
            if(nm%j==0)
            {
                cnt++;
                if((nm/j)!=j)
                    cnt++;
            }
        }
        divisor[i]=cnt;
    }
}
main()
{
   // timesave;
    int ts;
    sieve();
    cin>>ts;
    while(ts--)
    {
        int l,h,i,flag=0,chk=0;
        cin>>l>>h;
        for(i=l;i<=h;i++)
        {
            //cout<<i<<" "<<vis[divisor[i]]<<endl;
            if(vis[divisor[i]]==0)
            {
                if(flag==1)
                {
                    printf(" ");
                }
                cout<<i;
                chk=flag=1;
            }
        }
        if(chk==0)
            cout<<-1;
        cout<<endl;
    }
}

UVA 11086 - Composite Prime

///...................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("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pf(a) printf("%d",a)
#define pf2(a,b) printf("%d %d",a,b)
#define pf3(a,b,c) printf("%d %d %d",a,b,c)
#define sfl(a) scanf("%lld",&a)
#define sfl2(a,b) scanf("%lld %lld",&a,&b)
#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pfl(a) printf("%lld",a)
#define pfl2(a,b) printf("%lld %lld",a,b)
#define pfl3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#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++)
#define tz 100000
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//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
int vis[1000100];
vector<int>vec;
void sieve()
{
    int i,j,k;
    vis[1]=1;
    int sz=1000000;
    for(i=2; i<=1000000; i++)
    {
        if(vis[i]==0)
        {
            vec.push_back(i);
            //for(k=sz/i,j=i*k;k>=i;k--,j-=i)
            for(j=2*i;j<=sz;j+=i)
            {
                //cout<<j<<endl;
                vis[j]=1;
            }
        }
    }
}
int chk(int number)
{
    int i,j;
    for(i=0;i<vec.size()&&vec[i]*vec[i]<=number;i++)
    {
        if(number%vec[i] == 0)
        {
            j = number/vec[i];
            if(vis[j]==0)
                return 1;
        }
    }
    return 0;
}
main()
{
    timesave;
    int n;
    sieve();
    while(cin>>n)
    {
        int i,a,cnt=0;
        for(i=0; i<n; i++)
        {
            cin>>a;
            if(chk(a))
             cnt++;
        }
        cout<<cnt<<endl;
    }
}

UVA 990 - Diving for Gold

///...................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("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pf(a) printf("%d",a)
#define pf2(a,b) printf("%d %d",a,b)
#define pf3(a,b,c) printf("%d %d %d",a,b,c)
#define sfl(a) scanf("%lld",&a)
#define sfl2(a,b) scanf("%lld %lld",&a,&b)
#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pfl(a) printf("%lld",a)
#define pfl2(a,b) printf("%lld %lld",a,b)
#define pfl3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#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++)
#define tz 100000
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//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
int t,w,ar[31],br[31],dp[31],mx,n,path[31];
void update()
{
    int i,sum=0;
    for(i=0; i<n; i++)
    {
        if(dp[i])
        {
            sum+=br[i];
        }
    }
    if(sum>mx)
    {
        mx=sum;
        for(i=0; i<n; i++)
        {
            path[i]=dp[i];
        }
    }
}
void call(int i,int baki)
{
    if(i==n)
    {
        update();
        return;
    }
    dp[i]=0;
    call(i+1,baki);
    dp[i]=1;
    if(baki>=3*w*ar[i])
    {
        call(i+1,baki-3*w*ar[i]);
    }
}
int flag=1;
void print()
{
    int i,cnt;
    if(!flag)
        cout<<endl;
    else
        flag=0;
    cout<<mx<<endl;
    cnt=0;
    for(i=0;i<n;i++)
        if(path[i])
            cnt++;
    cout<<cnt<<endl;
    for(i=0;i<n;i++)
    {
        if(path[i])
        {
            cout<<ar[i]<<" "<<br[i]<<endl;
        }
    }
}
main()
{
    flag=1;
    while(cin>>t>>w)
    {
        int i1;
        cin>>n;
        for(i1=0; i1<n; i1++)
        {
            cin>>ar[i1]>>br[i1];
        }
        call(0,t);
        print();
    }
}