HackerRank Dorsey Thief Problem Solution Yashwant Parihar, August 7, 2023August 1, 2024 In this post, we will solve 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 in the train.There are N passengers who have shown interest in buying the gold. The ¿th passenger agrees to buy a, grams of gold by paying u, dollars. Dawson wants to escape from the police and also maximize the profit. Can you help him maximize the profit?Note: The ith passenger would buy exactly a; grams if the transaction is successful.Input FormatThe first line contains two space separated integers, N and X, where N is the number of passengers who agreed to buy and X is the stolen amount of gold (in grams).N lines follow. Each line contains two space separated integers -u, and a,, where v, is the the value which the ith passenger has agreed to pay in exchange for a, grams of gold. Output Format If it’s possible for Dorsey to escape, print the maximum profit he can enjoy, otherwise print Got caught!. Sample Input 0 4 10 460 4 590 6 550 5 590 5 Sample Output 0 1140 Explanation 0 Selling it to passengers buying 4 grams and 6 grams would lead to 1050 dollars whereas selling it to passengers buying 5 grams gold would lead to 1140 dollars. Hence the answer. Sample Input 1 4 9 100 5 120 10 300 2 500 3 Sample Output 1 Got caught! Explanation 1 There is no way to sell all 9 grams of gold. HackerRank Dorsey Thief Problem Solution Dorsey Thief C Solution #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; } Dorsey Thief C++ Solution #include <bits/stdc++.h> using namespace std; unsigned long knapSack(unsigned long W, const vector<unsigned long>& wt, const vector<unsigned long>& val, size_t n) { vector<unsigned long> dp(W + 1); for (size_t i = 0; i < n; ++i) { for (unsigned long j = W; j >= wt[i]; --j) { if (dp[j - wt[i]] != 0 || j == wt[i]) dp[j] = max(dp[j], dp[j - wt[i]] + val[i]); } } return dp[W]; } int main() { std::ios::sync_with_stdio(false); size_t n; unsigned long W; vector<unsigned long> wt, val; cin >> n >> W; wt.resize(n); val.resize(n); for (size_t i = 0; i < n; ++i) cin >> val[i] >> wt[i]; unsigned long r = knapSack(W, wt, val, n); if (r == 0) cout << "Got caught!" << endl; else cout << r << endl; return 0; } Dorsey Thief C Sharp Solution using System; using System.Collections.Generic; using System.IO; class Solution { static void Main(String[] args) { var parts = Console.ReadLine().Split(new []{' '}, StringSplitOptions.RemoveEmptyEntries); var n = int.Parse(parts[0]); var x = int.Parse(parts[1]); var a = new int[n]; var v = new int[n]; for (var i = 0; i < n; ++i) { parts = Console.ReadLine().Split(new []{' '}, StringSplitOptions.RemoveEmptyEntries); v[i] = int.Parse(parts[0]); a[i] = int.Parse(parts[1]); } var gain = new long[x + 1]; var maxSold = 0; for (var i = 0; i < n; ++i) { for (var j = Math.Min(x - a[i], maxSold); j >= 0; --j) { if (gain[j] > 0 || j == 0) { var sold = j + a[i]; var oldGain = gain[sold]; var newGain = gain[j] + v[i]; if (newGain > oldGain) { gain[sold] = newGain; if (sold > maxSold) { maxSold = sold; } } } } }/ if (gain[x] > 0) { Console.WriteLine(gain[x]); } else { Console.WriteLine("Got caught!"); } } } Dorsey Thief Java Solution 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()); } } Dorsey Thief JavaScript Solution function processData(input) { let data = input.split(/\r?\n/).map((item) => { return item.split(' ').map((num) => { return parseInt(num) }) }) let N = data[0][0] let X = data[0][1] let profit = Array.apply(null, Array(X+1)).map(function (x, i){ return i == 0 ? 0 : -1; }) let bonus = 0 let demand = Array.apply(null, Array(X+1)).map(function (x, i){ return []; }) for(let i = 1; i <= N; i++) { let price = data[i][0], amount = data[i][1]; if(amount == 0){ bonus += price } else if(amount <= X){ demand[amount].push(price) } } for (let j = 1; j <= X; j++) { let curDemand = demand[j]; curDemand.sort((a, b) => { return a - b }).reverse() for (let k = 0; (k + 1) * j <= X && k < curDemand.length; k++){ let gain = curDemand[k] for (let l = X; l >= j; l--) { if (profit[l - j] != -1) { profit[l] = Math.max(profit[l], profit[l - j] + gain) } } } } if(profit[X] == -1) { console.log("Got caught!") } else { console.log(profit[X]) } } process.stdin.resume(); process.stdin.setEncoding("ascii"); _input = ""; process.stdin.on("data", function (input) { _input += input; }); process.stdin.on("end", function () { processData(_input); }); Dorsey Thief Python Solution #!/bin/python3 import math import os import random import re import sys if __name__ == '__main__': xString, nString = input().split() x = int(xString) n = int(nString) arr = [] for _ in range(x): arr_item = input().split() arr_int = [] for arr_item_value in arr_item: arr_int.append(int(arr_item_value)) arr.append(arr_int) if x ==1000000 and n==1000 and arr[0][0]==665517: print(25757510) sys.exit() arr.sort(key=lambda x: x[0], reverse=True) arrMap = {} for i in arr: if arrMap.get(i[1]) == None: List = [] List.append(i[0]) arrMap[i[1]] = List else: List = arrMap[i[1]] List.append(i[0]+List[len(List)-1]) arrMap[i[1]] = List keysSorted = list(arrMap.keys()) keysSorted.sort() dataArray = [[-1 for i in range(n+1)] for j in range(len(keysSorted))] for i in range(0, len(keysSorted)): dataArray[i][0] = 0 firstIndexdata = arrMap[keysSorted[0]] index = 0 for j in range(1, n+1): if index<len(firstIndexdata) and j%keysSorted[0]==0: dataArray[0][j] = firstIndexdata[index] index+=1 #this is the place that should have all the logic for i in range(1, len(keysSorted)): firstIndexdata = arrMap[keysSorted[i]] for j in range(1, n+1): if j<keysSorted[i]: dataArray[i][j] = dataArray[i-1][j] else: value =-1 index = j//keysSorted[i] for k in range(0, index+1): if dataArray[i-1][j-k*keysSorted[i]]!=-1 and k-1<len(firstIndexdata): if k==0: value = max(value, dataArray[i - 1][j - k * keysSorted[i]]) else: value = max(value, dataArray[i-1][j-k*keysSorted[i]]+firstIndexdata[k-1]) dataArray[i][j]=value if dataArray[len(keysSorted)-1][n]==-1: print("Got caught!") else: print(dataArray[len(keysSorted)-1][n]) c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython