Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
  • Work with US
Programmingoneonone
Programmingoneonone

HackerEarth Benny and the Universe problem solution

YASH PAL, 31 July 2024
In this HackerEarth Benny and the Universe problem solution Hope you still have not forgotten about pig Benny. She is asking for help again. This time you have to answer some queries that Benny will give you.
All actions happen in the Universe where each planet has its own id starting from 0. There are infinite amount of planets.
To travel between different planets there are some special spacecrafts. Each spacecraft is characterized by the number di.
If the id of the planet you are currently staying on is idj and you decided you use spacecraft with di you will go to planet with id equal to idj + di.
Benny’s parents live nearby the planet with id equal to 0, so you may assume that there exists some spacecraft for which di is not more than 104.
You have to answer Q queries. Each query consists of one single integer x. You have to answer whether it’s possible to go from planet with id equal to 0 to planet with id equal to x.
HackerEarth Benny and the Universe problem solution

HackerEarth Benny and the Universe problem solution.

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <utility>
#include <memory.h>
#include <cassert>
#include <iterator>
#include <bitset>
#include <iomanip>
#include <complex>
#include <queue>
#include <ctime>
#include <deque>
#include <stack>
#include <set>
#include <map>

using namespace std;

#define pb push_back
#define mp make_pair
#define F first
#define S second

const int N = 1010;
const long long INF = (long long)2e18;

int n, q;
int a[N];
long long f[10 * N];

int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
int minAi = a[1];
for (int i = 1; i <= n; i++) {
minAi = min(minAi, a[i]);
}
for (int i = 0; i <= minAi; i++) {
f[i] = INF;
}
priority_queue< pair<long long, int> > pq;
f[0] = 0LL;
pq.push(mp(0, 0));
while (!pq.empty()) {
long long dist = -pq.top().F;
int ver = pq.top().S;
pq.pop();
if (f[ver] < dist) {
continue;
}
for (int i = 1; i <= n; i++) {
int nxt = (ver + a[i]) % minAi;
if (f[nxt] > f[ver] + 1LL * a[i]) {
f[nxt] = f[ver] + 1LL * a[i];
pq.push(mp(-f[nxt], nxt));
}
}
}
bool pp, mm;
pp = mm = false;
while (q--) {
int ver;
scanf("%d", &ver);
int real = ver;
ver %= minAi;
if (f[ver] <= 1LL * real) {
puts("YES");
pp = true;
} else {
puts("NO");
mm = true;
}
}
return 0;
}

Second solution

#include<bits/stdc++.h>

using namespace std;

const int N = 10000;

int n, tests;
int d[N];
set<pair<int, int> > S;
set<pair<int, int> >::iterator it;
int dist[N];

int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);

cin >> n >> tests;

for (int i = 0; i < n; i++)
{
cin >> d[i];
}

sort(d, d + n);

for (int i = 0; i < d[0]; i++)
{
dist[i] = 2e9+1e6;
}

dist[0] = 0;

for (int i = 0; i < d[0]; i++)
{
S.insert(make_pair(dist[i], i));
}

while (S.size())
{
it = S.begin();
int v = (*it).second;
S.erase(it);
if (dist[v]>1e9 + 1e8)
continue;

for (int i = 0; i < n; i++)
{
int new_val = dist[v] + d[i];
int rem = new_val%d[0];

if (dist[rem]>new_val)
{
S.erase(make_pair(dist[rem], rem));
dist[rem] = new_val;
S.insert(make_pair(dist[rem], rem));
}
}
}

for (; tests; --tests)
{
int val;
cin >> val;
long long R = val%d[0];
if (dist[R] <= val)
{
cout << "YESn";
}
else
{
cout << "NOn";
}
}

return 0;
}
coding problems solutions

Post navigation

Previous post
Next post

Related website

The Computer Science

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes