Блог пользователя yashsaha555

Maximize points
Автор yashsaha555, 18 месяцев назад, По-английски

Bittu is a chocolate-loving kid playing a game where he can choose bags of chocolates. Each bag has a different number of chocolates. Bittu starts with k chocolates and 1 point. He has two choices for each bag:

  1. Accept the Bag:

• If the chocolates in the bag are fewer than or equal to the chocolates Bittu has, he won't accept the bag. Instead, he'll deduct the bag's chocolates from his stash and gain one point.

• If the chocolates in the bag are more than what Bittu has, he can accept the bag. His chocolate stash increases by the bag's chocolates, and he loses one point.

  1. Ignore the Bag:

• Bittu can choose to ignore any number of bags without any consequences.

The goal is to maximize Bittu's points. Given an array "chocolates" with the number of chocolates in each bag, and the initial number of chocolates Bittu has, determine the maximum points he can achieve by selecting bags wisely

In simpler terms, he wants to acquire the maximum number of points while following the above mentioned rules.

Constraints

n — length of the array

1 <= n <= 1000

0 <= chocolates[i] <= 10^5

Input

First line consisting of the number of chocolates in n bags separated by space.

Second line consists of an integer depicting the number of chocolates that Bittu has, initially.

Output

Print the maximum points that Bittu can acquire.

Someone please help me with this problem. I am trying a DP solution but it is giving MLE.

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
12 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

JAVA Code:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // Read the chocolates array first
        String[] arr = sc.nextLine().trim().split("\\s+");
        int n = arr.length;
        int[] chocolates = new int[n];
        for (int i = 0; i < n; i++) {
            chocolates[i] = Integer.parseInt(arr[i]);
        }
        
        // Read initial chocolates
        int k = Integer.parseInt(sc.nextLine().trim());
        
        // OFFSET for indexing points from negative to positive
        int OFFSET = n + 5;  // extra buffer
        int maxSize = 2 * OFFSET + 5;  // enough to cover [-n..n+5]
        
        // dp[p+OFFSET] = max stash achievable with 'p' points after processing i bags
        long[] dp = new long[maxSize];
        Arrays.fill(dp, -1L);
        dp[1 + OFFSET] = k;  // Start with 1 point and k chocolates
        
        // Process each bag in order
        for (int c : chocolates) {
            long[] newDp = new long[maxSize];
            Arrays.fill(newDp, -1L);
            for (int idx = 0; idx < maxSize; idx++) {
                if (dp[idx] < 0) continue;
                long stash = dp[idx];
                int points = idx - OFFSET;
                
                // Option 1: Skip
                newDp[idx] = Math.max(newDp[idx], stash);
                
                // Option 2: Reject (if enough stash)
                if (c <= stash) {
                    int newIdx = (points + 1) + OFFSET;
                    long newStash = stash - c;
                    newDp[newIdx] = Math.max(newDp[newIdx], newStash);
                }
                
                // Option 3: Accept (if not enough stash)
                if (c > stash) {
                    int newIdx = (points - 1) + OFFSET;
                    long newStash = stash + c;
                    newDp[newIdx] = Math.max(newDp[newIdx], newStash);
                }
            }
            dp = newDp; // move to next bag
        }
        
        // Find maximum points achievable
        int result = Integer.MIN_VALUE;
        for (int idx = 0; idx < dp.length; idx++) {
            if (dp[idx] >= 0) {
                int points = idx - OFFSET;
                result = Math.max(result, points);
            }
        }
        
        System.out.println(result);
    }
}
→ Ответить
»
9 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится 
import java.util.*;
public class Main
{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
        String[] arr = sc.nextLine().trim().split("\\s+");
        int n = arr.length;
        int[] chocolates = new int[n];
        for (int i = 0; i < n; i++) {
            chocolates[i] = Integer.parseInt(arr[i]);
        }
        Arrays.sort(chocolates);
        int k = sc.nextInt();
        int i = 0, j = n-1, points = 1, maxPoints = Integer.MIN_VALUE;
        while(i<=j) {
            if(chocolates[i]<=k) {
                points++;
                k=k-chocolates[i];
                i++;
                maxPoints = Math.max(maxPoints, points);
            } else if(points>=1) {
                points--;
                k=k+chocolates[j];
                j--;
            } else {
                break;
            }
        }
        System.out.println(maxPoints);
	}
}
→ Ответить