#
# @lc app=leetcode id=948 lang=python3
#
# [948] Bag of Tokens
#
# https://leetcode.com/problems/bag-of-tokens/description/
#
# algorithms
# Medium (40.33%)
# Likes:    179
# Dislikes: 158
# Total Accepted:    11.2K
# Total Submissions: 27.6K
# Testcase Example:  '[100]\n50'
#
# You have an initial power P, an initial score of 0 points, and a bag of
# tokens.
# 
# Each token can be used at most once, has a value token[i], and has
# potentially two ways to use it.
# 
# 
# If we have at least token[i] power, we may play the token face up, losing
# token[i] power, and gaining 1 point.
# If we have at least 1 point, we may play the token face down, gaining
# token[i] power, and losing 1 point.
# 
# 
# Return the largest number of points we can have after playing any number of
# tokens.
# 
# 
# 
# 
# 
# 
# 
# Example 1:
# 
# 
# Input: tokens = [100], P = 50
# Output: 0
# 
# 
# 
# Example 2:
# 
# 
# Input: tokens = [100,200], P = 150
# Output: 1
# 
# 
# 
# Example 3:
# 
# 
# Input: tokens = [100,200,300,400], P = 200
# Output: 2
# 
# 
# 
# 
# Note:
# 
# 
# tokens.length <= 1000
# 0 <= tokens[i] < 10000
# 0 <= P < 10000
# 
# 
# 
# 
# 
#

# @lc code=start
class Solution:
    def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
        if not tokens: return 0
        tokens.sort()
        l, r, res = 0, len(tokens)-1, 0
        while l < r:
            if P >= tokens[l]:
                res += 1
                P -= tokens[l]
                l += 1
            elif res > 0:
                res -= 1
                P += tokens[r]
                r -= 1
            else:
                break
        if tokens[l] <= P: res += 1
        return res
# @lc code=end

