Header Ad

HackerEarth Help problem solution

In this HackerEarth Help..!! problem solution A group of friends is going on a vacation to a beach by a car. One of them is suffering from a severe fever and needs to be taken to hospital in nearest town immediately.

Assume that car consumes one unit of petrol for every unit of distance it travels. The hospital is located in town situated at co-ordinate 0. The car is D units away from the town. On this road, between the town and the current location of the car, there are N petrol stations where the friends can stop to acquire additional petrol.

As the fever is getting worse with time, the friends want to make the minimum possible number of stops for petrol on the way to the town. Fortunately, the capacity of the petrol tank on their car is so large that there is no limit to the amount of petrol it can hold. The car has some initial amount of petrol in tank which is denoted by P.

Determine the minimum number of stops needed to reach the town, or if the freinds cannot reach the town at all.


HackerEarth Help..!! problem solution


HackerEarth Help..!! problem solution.

import java.io.*;
import java.util.*;
class Main {
private static InputStream stream;
private static byte[] buf = new byte[1024];
private static int curChar;
private static int numChars;
private static SpaceCharFilter filter;
private static PrintWriter pw;

public static void main(String args[]) {
InputReader(System.in);
pw = new PrintWriter(System.out);
int n = nextInt();
Pair p[] = new Pair[n + 2];
for (int i = 0; i <= n; i++) {
p[i] = new Pair(nextLong(), nextLong());
}
p[n + 1] = new Pair(0, 0);
Arrays.sort(p);
PriorityQueue<Long> pq = new PriorityQueue<Long>(Collections.reverseOrder());
long curr_stat = p[0].dist;
long curr_fuel = 0;
long min_stops = -1;
for (int i = 0; i <= n + 1; i++) {
curr_fuel -= (curr_stat - p[i].dist);
curr_stat = p[i].dist;
while (curr_fuel < 0) {
if (pq.isEmpty()) {
min_stops = -1;
pw.println(min_stops);
pw.close();
return;
}
long fuel = pq.poll();
curr_fuel += fuel;
min_stops++;
}
pq.add(p[i].fuel);
}
pw.println(min_stops);
pw.close();
}
public static void InputReader(InputStream stream1) {
stream = stream1;
}
private static boolean isWhitespace(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private static boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
private static int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
private static int nextInt() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
private static long nextLong() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
private static boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return isWhitespace(c);
}
private interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
class Pair implements Comparable<Pair> {
long dist, fuel, w;
Pair(long dist, long fuel) {
this.dist = dist;
this.fuel = fuel;
}
@Override
public int compareTo(Pair o) {
// TODO Auto-generated method stub
return (int) (o.dist - dist);
}
}

Second solution

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
int n;
cin>>n;
int ans=0;
map<int,int>mp;
pair<int,int>point[100005];
for(int i=1;i<=n;i++)
{
int s,f;
cin>>s>>f;
point[i].first=s;
point[i].second=f;
}
ll d,p;
cin>>d>>p;
if(d<=p){cout<<"0\n";return 0;}
for(int i=1;i<=n;i++)
if(point[i].first <= d)
mp[d-point[i].first]=point[i].second;
map<int,int>:: iterator it;
it=mp.begin();
priority_queue<ll>pq;
while(it!=mp.end() && p<d)
{
for(;it->first<=p && it!=mp.end();it++)
{
pq.push(it->second);
}
if(pq.empty()){cout<<"-1\n";return 0;}
p+=pq.top();pq.pop();
ans++;
}
while(p<d && !pq.empty())
{
p+=pq.top();
pq.pop();
ans++;
}
if(p>=d)cout<<ans<<"\n";
else cout<<"-1\n";
return 0;
}

Post a Comment

0 Comments