Leet Code Weekly Contest 276

class Solution
{
public:
    vector<string> divideString(string s, int k, char fill)
    {
        vector<string> ans = { "" };
        
        for (auto c : s)
        {
            if (ans.back().length() < k)
            {
                ans.back().push_back(c);
            }
            else
            {
                ans.push_back("");
                ans.back().push_back(c);
            }
        }
        
        while (ans.back().length() < k)
        {
            ans.back().push_back(fill);
        }
        
        return ans;
    }
};

class Solution
{
public:
    int minMoves(int target, int maxDoubles)
    {
        int ans = 0;
        
        while (maxDoubles > 0 && target > 1)
        {
            if (target % 2 == 0)
            {
                target = target / 2;
                maxDoubles--;
                ans++;
            }
            else
            {
                target = target - 1;
                ans++;
            }
        }
        
        ans += target - 1;
        
        return ans;
    }
};

class Solution
{
public:
    
    long long f[100001];
    
    long long solve(int x, vector<vector<int>> &questions)
    {
        int n = questions.size();
        
        if (x >= n)
        {
            return 0;
        }
        
        if (f[x] == -1)
        {
            f[x] = max(solve(x + 1, questions), questions[x][0] + solve(x + questions[x][1] + 1, questions));
        }
        
        return f[x];
    }
    
    long long mostPoints(vector<vector<int>>& questions)
    {
        int n = questions.size();
        
        for (int i = 0; i < n; i++)
        {
            f[i] = -1;
        }
        
        return solve(0, questions);
    }
};

typedef long long ll;

class Solution
{
public:
    
    bool valid(int n, ll target, vector<int> &batteries)
    {
        ll sum = 0;
        
        for (auto x : batteries)
        {
            sum += min((ll) x, target);
        }
        
        return sum >= n * target;
    }
    
    long long maxRunTime(int n, vector<int>& batteries)
    {
        ll sum = 0;
        
        for (auto x : batteries)
        {
            sum += x;
        }
        
        ll low = 0, high = sum / n;
        
        ll ans = 0;
        
        while (low <= high)
        {
            ll mid = (low + high) / 2;
            
            if (valid(n, mid, batteries))
            {
                ans = mid;
                low = mid + 1;
            }
            else
            {
                high = mid - 1;
            }
        }
        
        return ans;
    }
};