HackerEarth Question paper problem solution

In this HackerEarth Question paper problem solution, A question paper contains N questions. The marks assigned to each correct answer is a. For each incorrect answer, you will lose b marks. Find the number of different marks that can be obtained in the examination.

HackerEarth Question paper problem solution.

#include<bits/stdc++.h>
#define ll int
using namespace std;
bool visited[4000006];
queue<pair<ll,ll> > q;
void solve()
{
    ll t;
    cin>>t;
    while(t--)
    {
        ll n,a,b,d,s,ans=0;
        cin>>n>>a>>b;
        while(!q.empty())
            q.pop();
        s=n*b;
        d=n*a+s;
        q.push({s,0});
        memset(visited,0,sizeof(visited));
        visited[s]=1;
        while(!q.empty())
        {
            ll temp=q.front().first;
            ll lvl=q.front().second;
            q.pop();
            if(lvl>=n)
            {
                continue;
            }
            if(temp+a<=d)
            {
                if(!visited[temp+a])
                {
                    visited[temp+a]=1;
                    q.push({temp+a,1+lvl});
                }
            }
            if(temp-b>=0)
            {
                if(!visited[temp-b])
                {
                    visited[temp-b]=1;
                    q.push({temp-b,1+lvl});
                }
            }
        }
        for(ll i=0;i<=d;i++)
            ans+=visited[i];
        cout<<ans<<"n";
    }
}
int main()
{
    ll i,j,k;
    /*for(i=10;i<=49;i++)
    {
        stringstream ss;
        ss << i;
        string s = ss.str();
        s="in"+s+".txt";
        string s1=ss.str();
        s1="out"+s1+".txt";
        freopen(s.c_str(),"r",stdin);
        freopen(s1.c_str(),"w",stdout);*/
        solve();
   // }
    return 0;
}

Second solution

#include<bits/stdc++.h>
using namespace std;
#define extra 1000001
bool vis[2000010];
int n,a,b;
int bfs(int s)
{
    for(int i=1;i<=2000001;i++)
    {
        vis[i]=0;
    }
    queue<pair<int,int> >q;
    q.push({s,0});
    vis[s+extra]=1;
    while(!q.empty())
    {
        int u=q.front().first,lev=q.front().second;q.pop();
        if(lev>=n)continue;
        if(!vis[u+a+extra])
        {
            vis[u+a+extra]=1;q.push({u+a,lev+1});
        }
        if(!vis[u-b+extra])
        {
            vis[u-b+extra]=1;q.push({u-b,lev+1});
        }
    }
    int cnt=0;
    for(int i=1;i<=2000001;i++)
    {
        if(vis[i])cnt++;
    }
    return cnt;
}
int solve(int n,int a,int b)
{
    for(int i=1;i<=2000001;i++)
    {
        vis[i]=0;
    }
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=n-i;j++)
        {
            if(vis[a*i-b*j+extra])break;
            vis[a*i-b*j+extra]=1;
        }
    }
    int cnt=0;
    for(int i=1;i<=2000001;i++)
    {
        if(vis[i])cnt++;
    }
    return cnt;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>a>>b;
        cout<<solve(n,a,b)<<"n";   //first solution
        //cout<<bfs(0)<<"n";       //second solution
    }   
    return 0;
}

coding problems