# weekly-contest-287

## A

### Statement

24 小时制时间`"HH:MM"` 进行格式化，其中 `HH``00``23` 之间，而 `MM``00``59` 之间。最早的 24 小时制时间为 `00:00` ，最晚的是 `23:59`

``````输入：current = "02:30", correct = "04:35"

- 为 current 加 60 分钟，current 变为 "03:30" 。
- 为 current 加 60 分钟，current 变为 "04:30" 。
- 为 current 加 5 分钟，current 变为 "04:35" 。

``````输入：current = "11:00", correct = "11:01"

``````

• `current``correct` 都符合 `"HH:MM"` 格式
• `current <= correct`

You are given two strings `current` and `correct` representing two 24-hour times.

24-hour times are formatted as `"HH:MM"`, where `HH` is between `00` and `23`, and `MM` is between `00` and `59`. The earliest 24-hour time is `00:00`, and the latest is `23:59`.

In one operation you can increase the time `current` by `1`, `5`, `15`, or `60` minutes. You can perform this operation any number of times.

Return the minimum number of operations needed to convert `current` to `correct`.

Example 1:

``````Input: current = "02:30", correct = "04:35"
Output: 3
Explanation:
We can convert current to correct in 3 operations as follows:
- Add 60 minutes to current. current becomes "03:30".
- Add 60 minutes to current. current becomes "04:30".
- Add 5 minutes to current. current becomes "04:35".
It can be proven that it is not possible to convert current to correct in fewer than 3 operations.``````

Example 2:

``````Input: current = "11:00", correct = "11:01"
Output: 1
Explanation: We only have to add one minute to current, so the minimum number of operations needed is 1.
``````

Constraints:

• `current` and `correct` are in the format `"HH:MM"`
• `current <= correct`

### 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 convertTime(string current, string correct) {
auto f = [](string s) {
int res = 0;
int a = (s[0] - '0') * 10 + (s[1] - '0');
int b = (s[3] - '0') * 10 + (s[4] - '0');
return a * 60 + b;
};

int a = f(current);
int b = f(correct);
int res = 0;
int gap = b - a;

res += gap / 60;
gap %= 60;
res += gap / 15;
gap %= 15;
res += gap / 5;
gap %= 5;
res += gap;
return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

• `answer[0]` 是所有 没有 输掉任何比赛的玩家列表。
• `answer[1]` 是所有恰好输掉 一场 比赛的玩家列表。

• 只考虑那些参与 至少一场 比赛的玩家。
• 生成的测试用例保证 不存在 两场比赛结果 相同

``````输入：matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]

``````

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

``````

• `1 <= matches.length <= 105`
• `matches[i].length == 2`
• `1 <= winneri, loseri <= 105`
• `winneri != loseri`
• 所有 `matches[i]` 互不相同

You are given an integer array `matches` where `matches[i] = [winneri, loseri]` indicates that the player `winneri` defeated player `loseri` in a match.

Return a list `answer` of size `2` where:

• `answer[0]` is a list of all players that have not lost any matches.
• `answer[1]` is a list of all players that have lost exactly one match.

The values in the two lists should be returned in increasing order.

Note:

• You should only consider the players that have played at least one match.
• The testcases will be generated such that no two matches will have the same outcome.

Example 1:

``````Input: matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
Output: [[1,2,10],[4,5,7,8]]
Explanation:
Players 1, 2, and 10 have not lost any matches.
Players 4, 5, 7, and 8 each have lost one match.
Players 3, 6, and 9 each have lost two matches.
``````

Example 2:

``````Input: matches = [[2,3],[1,3],[5,4],[6,4]]
Output: [[1,2,5,6],[]]
Explanation:
Players 1, 2, 5, and 6 have not lost any matches.
Players 3 and 4 each have lost two matches.
``````

Constraints:

• `1 <= matches.length <= 105`
• `matches[i].length == 2`
• `1 <= winneri, loseri <= 105`
• `winneri != loseri`
• All `matches[i]` are unique.

### 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:
vector<vector<int>> findWinners(vector<vector<int>> &matches) {
map<int, int> mp;
for (const auto &m : matches) {
++mp[m[1]];

if (mp.count(m[0]) == 0) {
mp[m[0]] = 0;
}
}

auto res = vector<vector<int>>(2, vector<int>());

for (const auto &[k, v] : mp) {
if (v == 0) {
res[0].push_back(k);
}

if (v == 1) {
res[1].push_back(k);
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

``````输入：candies = [5,8,6], k = 3

``````

``````输入：candies = [2,5], k = 11

``````

• `1 <= candies.length <= 105`
• `1 <= candies[i] <= 107`
• `1 <= k <= 1012`

You are given a 0-indexed integer array `candies`. Each element in the array denotes a pile of candies of size `candies[i]`. You can divide each pile into any number of sub piles, but you cannot merge two piles together.

You are also given an integer `k`. You should allocate piles of candies to `k` children such that each child gets the same number of candies. Each child can take at most one pile of candies and some piles of candies may go unused.

Return the maximum number of candies each child can get.

Example 1:

``````Input: candies = [5,8,6], k = 3
Output: 5
Explanation: We can divide candies[1] into 2 piles of size 5 and 3, and candies[2] into 2 piles of size 5 and 1. We now have five piles of candies of sizes 5, 5, 3, 5, and 1. We can allocate the 3 piles of size 5 to 3 children. It can be proven that each child cannot receive more than 5 candies.
``````

Example 2:

``````Input: candies = [2,5], k = 11
Output: 0
Explanation: There are 11 children but only 7 candies in total, so it is impossible to ensure each child receives at least one candy. Thus, each child gets no candy and the answer is 0.
``````

Constraints:

• `1 <= candies.length <= 105`
• `1 <= candies[i] <= 107`
• `1 <= k <= 1012`

### Solution

``````from typing import List

class Solution:
def maximumCandies(self, candies: List[int], k: int) -> int:
return bisect_right(range(1, sum(candies) + 1), -1, key=lambda x: -(sum(i // x for i in candies) >= k))
``````

## D

### Statement

1. 对字符串中的每个字符 `c` ，先从 `keys` 中找出满足 `keys[i] == c` 的下标 `i`
2. 在字符串中，用 `values[i]` 替换字符 `c`

1. 将字符串每相邻 2 个字符划分为一个子字符串，对于每个子字符串 `s` ，找出满足 `values[i] == s` 的一个下标 `i` 。如果存在多个有效的 `i` ，从中选择 任意 一个。这意味着一个字符串解密可能得到多个解密字符串。
2. 在字符串中，用 `keys[i]` 替换 `s`

• `Encrypter(char[] keys, String[] values, String[] dictionary)``keys``values``dictionary` 初始化 `Encrypter` 类。
• `String encrypt(String word1)` 按上述加密过程完成对 `word1` 的加密，并返回加密后的字符串。
• `int decrypt(String word2)` 统计并返回可以由 `word2` 解密得到且出现在 `dictionary` 中的字符串数目。

``````输入：
["Encrypter", "encrypt", "decrypt"]

[null, "eizfeiam", 2]

encrypter.encrypt("abcd"); // 返回 "eizfeiam"。
// 'a' 映射为 "ei"，'b' 映射为 "zf"，'c' 映射为 "ei"，'d' 映射为 "am"。
encrypter.decrypt("eizfeiam"); // return 2.
// "ei" 可以映射为 'a' 或 'c'，"zf" 映射为 'b'，"am" 映射为 'd'。
// 其中 2 个字符串，"abad" 和 "abcd"，在 dictionary 中出现，所以答案是 2 。
``````

• `1 <= keys.length == values.length <= 26`
• `values[i].length == 2`
• `1 <= dictionary.length <= 100`
• `1 <= dictionary[i].length <= 100`
• 所有 `keys[i]``dictionary[i]` 互不相同
• `1 <= word1.length <= 2000`
• `1 <= word2.length <= 200`
• 所有 `word1[i]` 都出现在 `keys`
• `word2.length` 是偶数
• `keys``values[i]``dictionary[i]``word1``word2` 只含小写英文字母
• 至多调用 `encrypt``decrypt` 总计 `200`

You are given a character array `keys` containing unique characters and a string array `values` containing strings of length 2. You are also given another string array `dictionary` that contains all permitted original strings after decryption. You should implement a data structure that can encrypt or decrypt a 0-indexed string.

A string is encrypted with the following process:

1. For each character `c` in the string, we find the index `i` satisfying `keys[i] == c` in `keys`.
2. Replace `c` with `values[i]` in the string.

A string is decrypted with the following process:

1. For each substring `s` of length 2 occurring at an even index in the string, we find an `i` such that `values[i] == s`. If there are multiple valid `i`, we choose any one of them. This means a string could have multiple possible strings it can decrypt to.
2. Replace `s` with `keys[i]` in the string.

Implement the `Encrypter` class:

• `Encrypter(char[] keys, String[] values, String[] dictionary)` Initializes the `Encrypter` class with `keys, values`, and `dictionary`.
• `String encrypt(String word1)` Encrypts `word1` with the encryption process described above and returns the encrypted string.
• `int decrypt(String word2)` Returns the number of possible strings `word2` could decrypt to that also appear in `dictionary`.

Example 1:

``````Input
["Encrypter", "encrypt", "decrypt"]
Output
[null, "eizfeiam", 2]
Explanation
encrypter.encrypt("abcd"); // return "eizfeiam".
// 'a' maps to "ei", 'b' maps to "zf", 'c' maps to "ei", and 'd' maps to "am".
encrypter.decrypt("eizfeiam"); // return 2.
// "ei" can map to 'a' or 'c', "zf" maps to 'b', and "am" maps to 'd'.
// Thus, the possible strings after decryption are "abad", "cbad", "abcd", and "cbcd".
// 2 of those strings, "abad" and "abcd", appear in dictionary, so the answer is 2.
``````

Constraints:

• `1 <= keys.length == values.length <= 26`
• `values[i].length == 2`
• `1 <= dictionary.length <= 100`
• `1 <= dictionary[i].length <= 100`
• All `keys[i]` and `dictionary[i]` are unique.
• `1 <= word1.length <= 2000`
• `1 <= word2.length <= 200`
• All `word1[i]` appear in `keys`.
• `word2.length` is even.
• `keys`, `values[i]`, `dictionary[i]`, `word1`, and `word2` only contain lowercase English letters.
• At most `200` calls will be made to `encrypt` and `decrypt` in total.

### 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 Encrypter {
public:
string mp[280];
vector<string> d;
map<string, vector<char>> mpv;

Encrypter(vector<char> &keys, vector<string> &values, vector<string> &dictionary) {
for (int i = 0; i < keys.size(); i++) {
mp[keys[i]] = values[i];

if (mpv.count(values[i]) == 0) {
mpv[values[i]] = vector<char>();
}

mpv[values[i]].push_back(keys[i]);
}

d = dictionary;
}

string encrypt(string word1) {
string res = "";
for (const auto &c : word1) {
res += mp[c];
}
return res;
}

int decrypt(string word2) {
auto p = vector<int>(d.size(), 0);

auto check = [](char c, vector<char> &cc) {
for (const char &_c : cc) {
if (c == _c) {
return true;
}
}

return false;
};

for (int j = 0; j < word2.length(); j += 2) {
for (int i = 0; i < d.size(); i++) {
if (p[i] == -1 || p[i] >= d[i].size()) {
p[i] = -1;
continue;
}

if (check(d[i][p[i]], mpv[word2.substr(j, 2)])) {
++p[i];
} else {
p[i] = -1;
}
}
}

int res = 0;
for (int i = 0; i < d.size(); i++) {
// cout << p[i] << endl;
if (p[i] == d[i].size()) {
++res;
}
}

return res;
}
};

/**
* Your Encrypter object will be instantiated and called as such:
* Encrypter* obj = new Encrypter(keys, values, dictionary);
* string param_1 = obj->encrypt(word1);
* int param_2 = obj->decrypt(word2);
*/

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````