Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1753.html

1753. Maximum Score From Removing Stones

Level

Medium

Description

You are playing a solitaire game with three piles of stones of sizes a, b, and c respectively. Each turn you choose two different non-empty piles, take one stone from each, and add 1 point to your score. The game stops when there are fewer than two non-empty piles (meaning there are no more available moves).

Given three integers a, b, and c, return the maximum score you can get.

Example 1:

Input: a = 2, b = 4, c = 6

Output: 6

Explanation: The starting state is (2, 4, 6). One optimal set of moves is:

• Take from 1st and 3rd piles, state is now (1, 4, 5)
• Take from 1st and 3rd piles, state is now (0, 4, 4)
• Take from 2nd and 3rd piles, state is now (0, 3, 3)
• Take from 2nd and 3rd piles, state is now (0, 2, 2)
• Take from 2nd and 3rd piles, state is now (0, 1, 1)
• Take from 2nd and 3rd piles, state is now (0, 0, 0)

There are fewer than two non-empty piles, so the game ends. Total: 6 points.

Example 2:

Input: a = 4, b = 4, c = 6

Output: 7

Explanation: The starting state is (4, 4, 6). One optimal set of moves is:

• Take from 1st and 2nd piles, state is now (3, 3, 6)
• Take from 1st and 3rd piles, state is now (2, 3, 5)
• Take from 1st and 3rd piles, state is now (1, 3, 4)
• Take from 1st and 3rd piles, state is now (0, 3, 3)
• Take from 2nd and 3rd piles, state is now (0, 2, 2)
• Take from 2nd and 3rd piles, state is now (0, 1, 1)
• Take from 2nd and 3rd piles, state is now (0, 0, 0)

There are fewer than two non-empty piles, so the game ends. Total: 7 points.

Example 3:

Input: a = 1, b = 8, c = 8

Output: 8

Explanation: One optimal set of moves is to take from the 2nd and 3rd piles for 8 turns until they are empty.

After that, there are fewer than two non-empty piles, so the game ends.

Constraints:

• 1 <= a, b, c <= 10^5

Solution

Use a greedy approach. Use a priority queue to store the three pile sizes, where the maximum element is polled first. Offer a, b, and c to the priority queue. While the priority queue has at least 2 elements, poll 2 elements, decrease them by 1, and offer them back to the priority queue if they are greater than 0. Each time increase the score by 1. Finally, return the score.

• Java
• Python
• C++
• Go

• class Solution {
      public int maximumScore(int a, int b, int c) {
          int score = 0;
          PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(new Comparator<Integer>() {
              public int compare(Integer num1, Integer num2) {
                  return num2 - num1;
              }
          });
          priorityQueue.offer(a);
          priorityQueue.offer(b);
          priorityQueue.offer(c);
          while (priorityQueue.size() > 1) {
              int num1 = priorityQueue.poll() - 1;
              int num2 = priorityQueue.poll() - 1;
              score++;
              if (num1 > 0)
                  priorityQueue.offer(num1);
              if (num2 > 0)
                  priorityQueue.offer(num2);
          }
          return score;
      }
  }
  
  ############
  
  class Solution {
      public int maximumScore(int a, int b, int c) {
          int[] s = new int[] {a, b, c};
          Arrays.sort(s);
          if (s[0] + s[1] < s[2]) {
              return s[0] + s[1];
          }
          return (a + b + c) >> 1;
      }
  }
  

• class Solution:
      def maximumScore(self, a: int, b: int, c: int) -> int:
          a, b, c = sorted([a, b, c])
          if a + b < c:
              return a + b
          return (a + b + c) >> 1
  
  ############
  
  # 1753. Maximum Score From Removing Stones
  # https://leetcode.com/problems/maximum-score-from-removing-stones
  
  from heapq import heappush, heappop, heapify
  
  class Solution:
      # heap
      def maximumScore(self, a: int, b: int, c: int) -> int:
          res = 0
          stones = [-a,-b,-c]
          heapify(stones)
          
          while abs(stones[0]) > 0 and abs(stones[1]) > 0:
              first = heappop(stones) + 1
              second = heappop(stones) + 1
              
              heappush(stones, first)
              heappush(stones, second)
              
              res += 1
              
          return res
      
      # reverse engineering / math
      def maximumScore(self, a: int, b: int, c: int) -> int:
          return min((a+b+c)//2 , a+b+c - max(a,b,c))
              
              
  
  

• class Solution {
  public:
      int maximumScore(int a, int b, int c) {
          vector<int> s = {a, b, c};
          sort(s.begin(), s.end());
          if (s[0] + s[1] < s[2]) return s[0] + s[1];
          return (a + b + c) >> 1;
      }
  };
  

• func maximumScore(a int, b int, c int) int {
  	s := []int{a, b, c}
  	sort.Ints(s)
  	if s[0]+s[1] < s[2] {
  		return s[0] + s[1]
  	}
  	return (a + b + c) >> 1
  }
  

All Problems

All Solutions