# weekly-contest-276

## A

### Statement

• 第一组由字符串中的前 `k` 个字符组成，第二组由接下来的 `k` 个字符串组成，依此类推。每个字符都能够成为 某一个 组的一部分。
• 对于最后一组，如果字符串剩下的字符 不足 `k` 个，需使用字符 `fill` 来补全这一组字符。

``````输入：s = "abcdefghi", k = 3, fill = "x"

``````

``````输入：s = "abcdefghij", k = 3, fill = "x"

``````

• `1 <= s.length <= 100`
• `s` 仅由小写英文字母组成
• `1 <= k <= 100`
• `fill` 是一个小写英文字母

A string `s` can be partitioned into groups of size `k` using the following procedure:

• The first group consists of the first `k` characters of the string, the second group consists of the next `k` characters of the string, and so on. Each character can be a part of exactly one group.
• For the last group, if the string does not have `k` characters remaining, a character `fill` is used to complete the group.

Note that the partition is done so that after removing the `fill` character from the last group (if it exists) and concatenating all the groups in order, the resultant string should be `s`.

Given the string `s`, the size of each group `k` and the character `fill`, return a string array denoting the composition of every group `s` has been divided into, using the above procedure.

Example 1:

``````Input: s = "abcdefghi", k = 3, fill = "x"
Output: ["abc","def","ghi"]
Explanation:
The first 3 characters "abc" form the first group.
The next 3 characters "def" form the second group.
The last 3 characters "ghi" form the third group.
Since all groups can be completely filled by characters from the string, we do not need to use fill.
Thus, the groups formed are "abc", "def", and "ghi".
``````

Example 2:

``````Input: s = "abcdefghij", k = 3, fill = "x"
Output: ["abc","def","ghi","jxx"]
Explanation:
Similar to the previous example, we are forming the first three groups "abc", "def", and "ghi".
For the last group, we can only use the character 'j' from the string. To complete this group, we add 'x' twice.
Thus, the 4 groups formed are "abc", "def", "ghi", and "jxx".
``````

Constraints:

• `1 <= s.length <= 100`
• `s` consists of lowercase English letters only.
• `1 <= k <= 100`
• `fill` is a lowercase English letter.

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define lowbit(x) ((x) & (-(x)))
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
vector<string> divideString(string s, int k, char fill) {
vector<string> res;
string t;
for (auto &c : s) {
t += c;
if (t.size() == k) {
res.push_back(t);
t = "";
}
}

if (!t.empty()) {
t += string(k - (t.size()), fill);
res.push_back(t);
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

• 递增，将当前整数的值加 1（即， `x = x + 1`）。
• 加倍，使当前整数的值翻倍（即，`x = 2 * x`）。

``````输入：target = 5, maxDoubles = 0

``````

``````输入：target = 19, maxDoubles = 2

``````

``````输入：target = 10, maxDoubles = 4

``````

• `1 <= target <= 109`
• `0 <= maxDoubles <= 100`

You are playing a game with integers. You start with the integer `1` and you want to reach the integer `target`.

In one move, you can either:

• Increment the current integer by one (i.e., `x = x + 1`).
• Double the current integer (i.e., `x = 2 * x`).

You can use the increment operation any number of times, however, you can only use the double operation at most `maxDoubles` times.

Given the two integers `target` and `maxDoubles`, return the minimum number of moves needed to reach `target` starting with `1`.

Example 1:

``````Input: target = 5, maxDoubles = 0
Output: 4
Explanation: Keep incrementing by 1 until you reach target.
``````

Example 2:

``````Input: target = 19, maxDoubles = 2
Output: 7
Explanation: Initially, x = 1
Increment 3 times so x = 4
Double once so x = 8
Increment once so x = 9
Double again so x = 18
Increment once so x = 19
``````

Example 3:

``````Input: target = 10, maxDoubles = 4
Output: 4
Explanation: Initially, x = 1
Increment once so x = 2
Double once so x = 4
Increment once so x = 5
Double again so x = 10
``````

Constraints:

• `1 <= target <= 109`
• `0 <= maxDoubles <= 100`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define lowbit(x) ((x) & (-(x)))
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

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

return res + (target - 1);
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

• Difficulty: Medium
• Tag: `数组` `动态规划`

• 比方说，给你 `questions = [[3, 2], [4, 3], [4, 4], [2, 5]]` ：
• 如果问题 `0` 被解决了， 那么你可以获得 `3` 分，但你不能解决问题 `1` 和 `2` 。
• 如果你跳过问题 `0` ，且解决问题 `1` ，你将获得 `4` 分但是不能解决问题 `2` 和 `3` 。

``````输入：questions = [[3,2],[4,3],[4,4],[2,5]]

- 解决问题 0 ：获得 3 分，但接下来 2 个问题都不能解决。
- 不能解决问题 1 和 2
- 解决问题 3 ：获得 2 分

``````

``````输入：questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]

- 跳过问题 0
- 解决问题 1 ：获得 2 分，但接下来 2 个问题都不能解决。
- 不能解决问题 2 和 3
- 解决问题 4 ：获得 5 分

``````

• `1 <= questions.length <= 105`
• `questions[i].length == 2`
• `1 <= pointsi, brainpoweri <= 105`

You are given a 0-indexed 2D integer array `questions` where `questions[i] = [pointsi, brainpoweri]`.

The array describes the questions of an exam, where you have to process the questions in order (i.e., starting from question `0`) and make a decision whether to solve or skip each question. Solving question `i` will earn you `pointsi` points but you will be unable to solve each of the next `brainpoweri` questions. If you skip question `i`, you get to make the decision on the next question.

• For example, given `questions = [[3, 2], [4, 3], [4, 4], [2, 5]]`:
• If question `0` is solved, you will earn `3` points but you will be unable to solve questions `1` and `2`.
• If instead, question `0` is skipped and question `1` is solved, you will earn `4` points but you will be unable to solve questions `2` and `3`.

Return the maximum points you can earn for the exam.

Example 1:

``````Input: questions = [[3,2],[4,3],[4,4],[2,5]]
Output: 5
Explanation: The maximum points can be earned by solving questions 0 and 3.
- Solve question 0: Earn 3 points, will be unable to solve the next 2 questions
- Unable to solve questions 1 and 2
- Solve question 3: Earn 2 points
Total points earned: 3 + 2 = 5. There is no other way to earn 5 or more points.
``````

Example 2:

``````Input: questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]
Output: 7
Explanation: The maximum points can be earned by solving questions 1 and 4.
- Skip question 0
- Solve question 1: Earn 2 points, will be unable to solve the next 2 questions
- Unable to solve questions 2 and 3
- Solve question 4: Earn 5 points
Total points earned: 2 + 5 = 7. There is no other way to earn 7 or more points.
``````

Constraints:

• `1 <= questions.length <= 105`
• `questions[i].length == 2`
• `1 <= pointsi, brainpoweri <= 105`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define lowbit(x) ((x) & (-(x)))
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
long long mostPoints(vector<vector<int>> &questions) {
int n = questions.size();
vector<ll> ans(n + 5, 0);
for (int i = 0; i < n; i++) {
int m = i + 1 + questions[i][1];
if (m > n) {
m = n;
}
if (i) {
ans[i] = max(ans[i], ans[i - 1]);
}
ans[m] = max(ans[m], ans[i] + questions[i][0]);
}

ll res = 0;
for (auto &a : ans) res = max(res, a);
return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

``````输入：n = 2, batteries = [3,3,3]

2 分钟后，将第二台电脑与电池 1 断开连接，并连接电池 2 。注意，电池 0 还可以供电 1 分钟。

``````

``````输入：n = 2, batteries = [1,1,1,1]

1 分钟后，电池 1 和电池 3 也耗尽了，所以两台电脑都无法继续运行。

``````

• `1 <= n <= batteries.length <= 105`
• `1 <= batteries[i] <= 109`

You have `n` computers. You are given the integer `n` and a 0-indexed integer array `batteries` where the `ith` battery can run a computer for `batteries[i]` minutes. You are interested in running all `n` computers simultaneously using the given batteries.

Initially, you can insert at most one battery into each computer. After that and at any integer time moment, you can remove a battery from a computer and insert another battery any number of times. The inserted battery can be a totally new battery or a battery from another computer. You may assume that the removing and inserting processes take no time.

Note that the batteries cannot be recharged.

Return the maximum number of minutes you can run all the `n` computers simultaneously.

Example 1:

``````Input: n = 2, batteries = [3,3,3]
Output: 4
Explanation:
Initially, insert battery 0 into the first computer and battery 1 into the second computer.
After two minutes, remove battery 1 from the second computer and insert battery 2 instead. Note that battery 1 can still run for one minute.
At the end of the third minute, battery 0 is drained, and you need to remove it from the first computer and insert battery 1 instead.
By the end of the fourth minute, battery 1 is also drained, and the first computer is no longer running.
We can run the two computers simultaneously for at most 4 minutes, so we return 4.
``````

Example 2:

``````Input: n = 2, batteries = [1,1,1,1]
Output: 2
Explanation:
Initially, insert battery 0 into the first computer and battery 2 into the second computer.
After one minute, battery 0 and battery 2 are drained so you need to remove them and insert battery 1 into the first computer and battery 3 into the second computer.
After another minute, battery 1 and battery 3 are also drained so the first and second computers are no longer running.
We can run the two computers simultaneously for at most 2 minutes, so we return 2.
``````

Constraints:

• `1 <= n <= batteries.length <= 105`
• `1 <= batteries[i] <= 109`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define lowbit(x) ((x) & (-(x)))
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
long long maxRunTime(int n, vector<int> &batteries) {
int m = batteries.size();
ll tot = 0;
for (auto &b : batteries) tot += b;

auto ok = [&](ll x) {
ll sum = 0;
for (auto &b : batteries) {
sum += min(1ll * b, x);
}

return sum >= x * n;
};

ll l = 0, r = tot / n, res = 0;
while (r - l >= 0) {
ll mid = (l + r) >> 1;
if (ok(mid)) {
res = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````