UVA 10036 - Divisibility

UVA Aug 31, 2020

Problem PDF

Solution:

/*
    Author   : Shipu Ahamed (Psycho Timekiller)
    Facebook : http://facebook.com/DeesheharaShipu
*/

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

#define pi 2*acos(0.0)
#define all(v) v.begin(),v.end()

//input
#define si(t) scanf("%d",&t)
#define sl(t) scanf("%lld",&t)
#define sii(a,b) scanf("%d%d",&a,&b)
#define sll(a,b) scanf("%lld%lld",&a,&b)

//Output
#define P(a) printf("%d\n",a)
#define PL(a) printf("%lld\n",a)
#define PN(a) printf("%d ",a)
#define PLN(a) printf("%lld ",a)
#define PP(a,b) printf("%d %d\n",a,b)
#define PPN(a,b) printf("%d %d ",a,b)
#define PPL(a,b) printf("%lld %lld\n",a,b)
#define PPLN(a,b) printf("%lld %lld ",a,b)

#define CP(a) cout<string toString( T Number ){stringstream st;st << Number;return st.str();}
int SOD(int n) {int sum=0;for(int i=1;i*i<=n;i++)sum+=(n%i)?0:((i*i==n)?i:i+n/i);return sum;}

//File input/output
#define input freopen("in.txt","r",stdin)
#define output freopen("out.txt","w",stdout)

//upper bound and lower bound
#define LB(a,value) (lower_bound(all(a),value)-a.begin())
#define UB(a,value) (upper_bound(all(a),value)-a.begin())

//Test Case & New line
#define Case(no) printf("Case %d: ",++no)
#define nl puts("")

int stringconvert(string s){int p; istringstream st(s); st>>p ; return p;}

ll pow(ll a,ll b, ll m) { ll res = 1; while(b) { if(b & 1) { res = ( (res % m) * (a % m) ) %m ; } a= ((a%m) * (a%m)) %m; b >>= 1; } return res; }
ll modInverse(ll a, ll m){return pow(a,m-2,m);}

////============ CONSTANT ===============////
#define inf   1<<30                                           //infinity value
#define eps   1e-9
#define mx    10010
#define mod   1000000007
////=====================================////

int a[mx],dp[mx][203],n,k;

bool solve(int i,int sum)
{
    if(i==n)
    {
        if(sum%k==0)
        {
            return 1;
        }
        else
            return 0;
    }

    if(dp[i][sum]!=-1)
        return dp[i][sum];

    return dp[i][sum]=(solve(i+1,(sum+a[i])%k)|solve(i+1,(sum-a[i])%k));
}

int main()
{
    int t;
    si(t);
    while(t--)
    {
        sii(n,k);

        cover(dp,-1);

        for(int i=0;i
https://github.com/Shipu/OnlineJudgeProblemSolutionWithCPlusPlus/tree/master/uva/10036/10036.cpp

Tags

Shipu Ahamed

CSPO® | Partly Product, Project Manager and Partly Software Engineer.

Great! You've successfully subscribed.
Great! Next, complete checkout for full access.
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.