Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • 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
Programming101
Programming101

Learn everything about programming

HackerRank Dorsey Thief problem solution

YASH PAL, 31 July 2024

In this HackerRank Dorsey Thief problem solution, Mr. Dorsey Dawson recently stole X grams of gold from ACME Jewellers. He is now on a train back home. To avoid getting caught by the police, he has to convert all the gold he has into paper money. He turns into a salesman and starts selling the gold on the train.

There are N passengers who have shown interest in buying the gold. The Ith passenger agrees to buy Ai grams of gold by paying Vi dollars. Dawson wants to escape from the police and also maximize the profit. Can you help him maximize the profit?

HackerRank Dorsey Thief problem solution

Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;
    boolean eof;

    void solve() throws IOException {
        int n = nextInt();
        int x = nextInt();

        long[] max = new long[x + 1];
        Arrays.fill(max, -1);
        max[0] = 0;

        long freeBonus = 0;

        List<Integer>[] byNeed = new List[x + 1];
        for (int i = 1; i <= x; i++) {
            byNeed[i] = new ArrayList<>(0);
        }

        for (int i = 0; i < n; i++) {
            int gain = nextInt();
            int need = nextInt();
            if (need == 0) {
                freeBonus += gain;
                continue;
            }
            if (need <= x) {
                byNeed[need].add(gain);
            }

        }

        for (int need = 1; need <= x; need++) {
            List<Integer> cur = byNeed[need];
            Collections.sort(cur);
            Collections.reverse(cur);
            for (int i = 0; (i + 1) * need <= x && i < cur.size(); i++) {
                int gain = cur.get(i);
                for (int j = x; j >= need; j--) {
                    if (max[j - need] != -1) {
                        max[j] = Math.max(max[j], max[j - need] + gain);
                    }
                }
            }
        }

        if (max[x] == -1) {
            out.println("Got caught!");
        } else {
            out.println(max[x] + freeBonus);
        }
    }

    Solution() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }

    public static void main(String[] args) throws IOException {
        new Solution();
    }

    String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }

    String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            eof = true;
            return null;
        }
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}

Problem solution in C++.

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, x;
    cin >> n >> x;
    vector<long long> profit(x + 1, -1);
    profit[0] = 0;
    for(int i = 0; i < n; ++i) {
        int price, amount;
        cin >> price >> amount;
        for(int pos = x; pos >= 0; --pos) {
            int newAmount = pos + amount;
            if(newAmount > x || profit[pos] == -1) {
                continue;
            }
            long long value = profit[pos] + price;
            profit[newAmount] = max(profit[newAmount], value);
        }
    }
    
    if(profit[x] == -1) {
        cout << "Got caught!" << endl;
    } else {
        cout << profit[x] << endl;
    }
             
    return 0;
}

Problem solution in C.

#include <stdio.h>
#include <stdlib.h>

int main()
{ 
    int n,x;
    scanf("%d %d",&n,&x);
    int v[n],a[n];
    int temp=0;
    while(temp<n){
                  scanf("%d %d",&v[temp],&a[temp]);
                  temp++;
    }
    
    long long int dp[x+1];
    dp[0]=0;
    for(int i=1;i<=x;i++){
            dp[i]=-100000000000000000;
    }
    
    temp=0;
    while(temp<n){
                  for(int j=x;j>=a[temp];j--){
                          dp[j]=(dp[j]>dp[j-a[temp]]+v[temp])?dp[j]:(dp[j-a[temp]]+v[temp]);
                  }
                  temp++;
    }
    if(dp[x]>0){
                printf("%lld",dp[x]);
    }else{
          printf("Got caught!");
    }

return 0;   
}

algorithm coding problems

Post navigation

Previous post
Next post
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
How to download udemy paid courses for free

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
©2025 Programming101 | WordPress Theme by SuperbThemes