# biweekly-contest-76

## A

### Statement

``````输入：nums = [-4,-2,1,4,8]

-4 到 0 的距离为 |-4| = 4 。
-2 到 0 的距离为 |-2| = 2 。
1 到 0 的距离为 |1| = 1 。
4 到 0 的距离为 |4| = 4 。
8 到 0 的距离为 |8| = 8 。

``````

``````输入：nums = [2,-1,1]

``````

• `1 <= n <= 1000`
• `-105 <= nums[i] <= 105`

Given an integer array `nums` of size `n`, return the number with the value closest to `0` in `nums`. If there are multiple answers, return the number with the largest value.

Example 1:

``````Input: nums = [-4,-2,1,4,8]
Output: 1
Explanation:
The distance from -4 to 0 is |-4| = 4.
The distance from -2 to 0 is |-2| = 2.
The distance from 1 to 0 is |1| = 1.
The distance from 4 to 0 is |4| = 4.
The distance from 8 to 0 is |8| = 8.
Thus, the closest number to 0 in the array is 1.
``````

Example 2:

``````Input: nums = [2,-1,1]
Output: 1
Explanation: 1 and -1 are both the closest numbers to 0, so 1 being larger is returned.
``````

Constraints:

• `1 <= n <= 1000`
• `-105 <= nums[i] <= 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 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 findClosestNumber(vector<int> &nums) {
int a = 0x3f3f3f3f;
int b = 0;
for (auto &aa : nums) {
int x = abs(aa);
if (x < a) {
a = x;
b = aa;
} else if (x == a) {
b = max(b, aa);
}
}

return b;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

``````输入：total = 20, cost1 = 10, cost2 = 5

- 如果你买 0 支钢笔，那么你可以买 0 ，1 ，2 ，3 或者 4 支铅笔。
- 如果你买 1 支钢笔，那么你可以买 0 ，1 或者 2 支铅笔。
- 如果你买 2 支钢笔，那么你没法买任何铅笔。

``````

``````输入：total = 5, cost1 = 10, cost2 = 10

``````

• `1 <= total, cost1, cost2 <= 106`

You are given an integer `total` indicating the amount of money you have. You are also given two integers `cost1` and `cost2` indicating the price of a pen and pencil respectively. You can spend part or all of your money to buy multiple quantities (or none) of each kind of writing utensil.

Return the number of distinct ways you can buy some number of pens and pencils.

Example 1:

``````Input: total = 20, cost1 = 10, cost2 = 5
Output: 9
Explanation: The price of a pen is 10 and the price of a pencil is 5.
- If you buy 0 pens, you can buy 0, 1, 2, 3, or 4 pencils.
- If you buy 1 pen, you can buy 0, 1, or 2 pencils.
The total number of ways to buy pens and pencils is 5 + 3 + 1 = 9.
``````

Example 2:

``````Input: total = 5, cost1 = 10, cost2 = 10
Output: 1
Explanation: The price of both pens and pencils are 10, which cost more than total, so you cannot buy any writing utensils. Therefore, there is only 1 way: buy 0 pens and 0 pencils.
``````

Constraints:

• `1 <= total, cost1, cost2 <= 106`

### 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 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 waysToBuyPensPencils(int total, int cost1, int cost2) {
ll res = 0;
for (int i = 0; i <= total / cost1; i++) {
res += (total - cost1 * i) / cost2 + 1;
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

• 比方说，你想取 `\$300` ，并且机器里有 `2` 张 `\$50` 的钞票，`1` 张 `\$100` 的钞票和`1` 张 `\$200` 的钞票，那么机器会取出 `\$100` 和 `\$200` 的钞票。
• 但是，如果你想取 `\$600` ，机器里有 `3` 张 `\$200` 的钞票和`1` 张 `\$500` 的钞票，那么取款请求会被拒绝，因为机器会先取出 `\$500` 的钞票，然后无法取出剩余的 `\$100` 。注意，因为有 `\$500` 钞票的存在，机器 不能 取 `\$200` 的钞票。

• `ATM()` 初始化 ATM 对象。
• `void deposit(int[] banknotesCount)` 分别存入 `\$20` ，`\$50``\$100``\$200` 和 `\$500` 钞票的数目。
• `int[] withdraw(int amount)` 返回一个长度为 `5` 的数组，分别表示 `\$20` ，`\$50``\$100` ，`\$200` 和 `\$500` 钞票的数目，并且更新 ATM 机里取款后钞票的剩余数量。如果无法取出指定数额的钱，请返回 `[-1]` （这种情况下  取出任何钞票）。

``````输入：
["ATM", "deposit", "withdraw", "deposit", "withdraw", "withdraw"]
[[], [[0,0,1,2,1]], , [[0,1,0,1,1]], , ]

[null, null, [0,0,1,0,1], null, [-1], [0,1,0,0,1]]

ATM atm = new ATM();
atm.deposit([0,0,1,2,1]); // 存入 1 张 \$100 ，2 张 \$200 和 1 张 \$500 的钞票。
atm.withdraw(600);        // 返回 [0,0,1,0,1] 。机器返回 1 张 \$100 和 1 张 \$500 的钞票。机器里剩余钞票的数量为 [0,0,0,2,0] 。
atm.deposit([0,1,0,1,1]); // 存入 1 张 \$50 ，1 张 \$200 和 1 张 \$500 的钞票。
// 机器中剩余钞票数量为 [0,1,0,3,1] 。
atm.withdraw(600);        // 返回 [-1] 。机器会尝试取出 \$500 的钞票，然后无法得到剩余的 \$100 ，所以取款请求会被拒绝。
// 由于请求被拒绝，机器中钞票的数量不会发生改变。
atm.withdraw(550);        // 返回 [0,1,0,0,1] ，机器会返回 1 张 \$50 的钞票和 1 张 \$500 的钞票。``````

• `banknotesCount.length == 5`
• `0 <= banknotesCount[i] <= 109`
• `1 <= amount <= 109`
• 总共 最多有 `5000` 次 `withdraw` 和 `deposit` 的调用。
• 函数 `withdraw` 和 `deposit` 至少各有 一次 调用。

There is an ATM machine that stores banknotes of `5` denominations: `20`, `50`, `100`, `200`, and `500` dollars. Initially the ATM is empty. The user can use the machine to deposit or withdraw any amount of money.

When withdrawing, the machine prioritizes using banknotes of larger values.

• For example, if you want to withdraw `\$300` and there are `2` `\$50` banknotes, `1` `\$100` banknote, and `1` `\$200` banknote, then the machine will use the `\$100` and `\$200` banknotes.
• However, if you try to withdraw `\$600` and there are `3` `\$200` banknotes and `1` `\$500` banknote, then the withdraw request will be rejected because the machine will first try to use the `\$500` banknote and then be unable to use banknotes to complete the remaining `\$100`. Note that the machine is not allowed to use the `\$200` banknotes instead of the `\$500` banknote.

Implement the ATM class:

• `ATM()` Initializes the ATM object.
• `void deposit(int[] banknotesCount)` Deposits new banknotes in the order `\$20`, `\$50`, `\$100`, `\$200`, and `\$500`.
• `int[] withdraw(int amount)` Returns an array of length `5` of the number of banknotes that will be handed to the user in the order `\$20`, `\$50`, `\$100`, `\$200`, and `\$500`, and update the number of banknotes in the ATM after withdrawing. Returns `[-1]` if it is not possible (do not withdraw any banknotes in this case).

Example 1:

``````Input
["ATM", "deposit", "withdraw", "deposit", "withdraw", "withdraw"]
[[], [[0,0,1,2,1]], , [[0,1,0,1,1]], , ]
Output
[null, null, [0,0,1,0,1], null, [-1], [0,1,0,0,1]]
Explanation
ATM atm = new ATM();
atm.deposit([0,0,1,2,1]); // Deposits 1 \$100 banknote, 2 \$200 banknotes,
// and 1 \$500 banknote.
atm.withdraw(600);        // Returns [0,0,1,0,1]. The machine uses 1 \$100 banknote
// and 1 \$500 banknote. The banknotes left over in the
// machine are [0,0,0,2,0].
atm.deposit([0,1,0,1,1]); // Deposits 1 \$50, \$200, and \$500 banknote.
// The banknotes in the machine are now [0,1,0,3,1].
atm.withdraw(600);        // Returns [-1]. The machine will try to use a \$500 banknote
// and then be unable to complete the remaining \$100,
// so the withdraw request will be rejected.
// Since the request is rejected, the number of banknotes
// in the machine is not modified.
atm.withdraw(550);        // Returns [0,1,0,0,1]. The machine uses 1 \$50 banknote
// and 1 \$500 banknote.``````

Constraints:

• `banknotesCount.length == 5`
• `0 <= banknotesCount[i] <= 109`
• `1 <= amount <= 109`
• At most `5000` calls in total will be made to `withdraw` and `deposit`.
• At least one call will be made to each function `withdraw` and `deposit`.

### 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 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 ATM {
public:
vector<ll> v;
vector<int> f;
ATM() {
v = vector<ll>(10, 0);
f = vector<int>({20, 50, 100, 200, 500});
}

void deposit(vector<int> banknotesCount) {
for (int i = 0; i < 5; i++) {
v[i] += banknotesCount[i];
}
}

vector<int> withdraw(int amount) {
auto res = vector<int>(5, 0);
int remind = amount;
for (int i = 4; i >= 0; i--) {
ll cur = min<ll>(v[i], remind / f[i]);
res[i] = cur;
remind -= f[i] * cur;
}

if (remind != 0) {
return vector<int>({-1});
}

for (int i = 0; i < 5; i++) {
v[i] -= res[i];
}

return res;
}
};

/**
* Your ATM object will be instantiated and called as such:
* ATM* obj = new ATM();
* obj->deposit(banknotesCount);
* vector<int> param_2 = obj->withdraw(amount);
*/

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

• 序列中每 相邻 节点之间有边相连。
• 序列中没有节点出现超过一次。 ``````输入：scores = [5,2,9,8,4], edges = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]

`````` ``````输入：scores = [9,20,6,4,11,12], edges = [[0,3],[5,3],[2,4],[1,3]]

``````

• `n == scores.length`
• `4 <= n <= 5 * 104`
• `1 <= scores[i] <= 108`
• `0 <= edges.length <= 5 * 104`
• `edges[i].length == 2`
• `0 <= ai, bi <= n - 1`
• `ai != bi`
• 不会有重边。

There is an undirected graph with `n` nodes, numbered from `0` to `n - 1`.

You are given a 0-indexed integer array `scores` of length `n` where `scores[i]` denotes the score of node `i`. You are also given a 2D integer array `edges` where `edges[i] = [ai, bi]` denotes that there exists an undirected edge connecting nodes `ai` and `bi`.

A node sequence is valid if it meets the following conditions:

• There is an edge connecting every pair of adjacent nodes in the sequence.
• No node appears more than once in the sequence.

The score of a node sequence is defined as the sum of the scores of the nodes in the sequence.

Return the maximum score of a valid node sequence with a length of `4`. If no such sequence exists, return `-1`.

Example 1: ``````Input: scores = [5,2,9,8,4], edges = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
Output: 24
Explanation: The figure above shows the graph and the chosen node sequence [0,1,2,3].
The score of the node sequence is 5 + 2 + 9 + 8 = 24.
It can be shown that no other node sequence has a score of more than 24.
Note that the sequences [3,1,2,0] and [1,0,2,3] are also valid and have a score of 24.
The sequence [0,3,2,4] is not valid since no edge connects nodes 0 and 3.
``````

Example 2: ``````Input: scores = [9,20,6,4,11,12], edges = [[0,3],[5,3],[2,4],[1,3]]
Output: -1
Explanation: The figure above shows the graph.
There are no valid node sequences of length 4, so we return -1.
``````

Constraints:

• `n == scores.length`
• `4 <= n <= 5 * 104`
• `1 <= scores[i] <= 108`
• `0 <= edges.length <= 5 * 104`
• `edges[i].length == 2`
• `0 <= ai, bi <= n - 1`
• `ai != bi`
• There are no duplicate edges.

### 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 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

const int INF = 0x3f3f3f3f;

class Solution {
public:
int maximumScore(vector<int>& scores, vector<vector<int>>& edges) {
int n = scores.size();

auto f = vector<vector<PII>>(n + 1, vector<PII>(3, PII(-1, -INF)));
auto G = vector<vector<int>>(n + 1, vector<int>());

for (const auto& e : edges) {
int u = e;
int v = e;

G[v].push_back(u);
G[u].push_back(v);
}

for (int u = 0; u < n; u++) {
for (const auto& v : G[u]) {
int s = scores[v];

for (int i = 0; i < 3; i++) {
if (s > f[u][i].second) {
for (int j = 2; j > i; j--) {
f[u][j] = f[u][j - 1];
}

f[u][i] = PII(v, s);
break;
}
}
}
}

int res = -1;

for (int u = 0; u < n; u++) {
int su = scores[u];

for (const auto& v : G[u]) {
int sv = scores[v];

for (int i = 0; i < 3; i++) {
int uu = f[u][i].first;
if (uu == -1) {
break;
}

if (uu == v) {
continue;
}

for (int j = 0; j < 3; j++) {
int vv = f[v][j].first;
if (vv == -1) {
break;
}

if (vv == uu || vv == u) {
continue;
}

int now = su + sv + f[u][i].second + f[v][j].second;

res = max(res, now);
}
}
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````