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


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;
}