# weekly-contest-185

## A

### Statement

``````输入：s = "a0b1c2"

``````

``````输入：s = "leetcode"

``````

``````输入：s = "1229857369"

``````

``````输入：s = "covid2019"

``````

``````输入：s = "ab123"

``````

• `1 <= s.length <= 500`
• `s` 仅由小写英文字母和/或数字组成。

You are given an alphanumeric string `s`. (Alphanumeric string is a string consisting of lowercase English letters and digits).

You have to find a permutation of the string where no letter is followed by another letter and no digit is followed by another digit. That is, no two adjacent characters have the same type.

Return the reformatted string or return an empty string if it is impossible to reformat the string.

Example 1:

``````Input: s = "a0b1c2"
Output: "0a1b2c"
Explanation: No two adjacent characters have the same type in "0a1b2c". "a0b1c2", "0a1b2c", "0c2a1b" are also valid permutations.
``````

Example 2:

``````Input: s = "leetcode"
Output: ""
Explanation: "leetcode" has only characters so we cannot separate them by digits.
``````

Example 3:

``````Input: s = "1229857369"
Output: ""
Explanation: "1229857369" has only digits so we cannot separate them by characters.
``````

Constraints:

• `1 <= s.length <= 500`
• `s` consists of only lowercase English letters and/or digits.

## B

### Statement

• Difficulty: Medium
• Tag: `数组` `哈希表` `字符串` `有序集合` `排序`

``````输入：orders = [["David","3","Ceviche"],["Corina","10","Beef Burrito"],["David","3","Fried Chicken"],["Carla","5","Water"],["Carla","5","Ceviche"],["Rous","3","Ceviche"]]

Table,Beef Burrito,Ceviche,Fried Chicken,Water
3    ,0           ,2      ,1            ,0
5    ,0           ,1      ,0            ,1
10   ,1           ,0      ,0            ,0

``````

``````输入：orders = [["James","12","Fried Chicken"],["Ratesh","12","Fried Chicken"],["Amadeus","12","Fried Chicken"],["Adam","1","Canadian Waffles"],["Brianna","1","Canadian Waffles"]]

``````

``````输入：orders = [["Laura","2","Bean Burrito"],["Jhon","2","Beef Burrito"],["Melissa","2","Soda"]]

``````

• `1 <= orders.length <= 5 * 10^4`
• `orders[i].length == 3`
• `1 <= customerNamei.length, foodItemi.length <= 20`
• `customerNamei``foodItemi` 由大小写英文字母及空格字符 `' '` 组成。
• `tableNumberi``1``500` 范围内的整数。

Given the array `orders`, which represents the orders that customers have done in a restaurant. More specifically `orders[i]=[customerNamei,tableNumberi,foodItemi]` where `customerNamei` is the name of the customer, `tableNumberi` is the table customer sit at, and `foodItemi` is the item customer orders.

Return the restaurant's “display table. The “display table” is a table whose row entries denote how many of each food item each table ordered. The first column is the table number and the remaining columns correspond to each food item in alphabetical order. The first row should be a header whose first column is “Table”, followed by the names of the food items. Note that the customer names are not part of the table. Additionally, the rows should be sorted in numerically increasing order.

Example 1:

``````
Input: orders = [["David","3","Ceviche"],["Corina","10","Beef Burrito"],["David","3","Fried Chicken"],["Carla","5","Water"],["Carla","5","Ceviche"],["Rous","3","Ceviche"]]
Output: [["Table","Beef Burrito","Ceviche","Fried Chicken","Water"],["3","0","2","1","0"],["5","0","1","0","1"],["10","1","0","0","0"]]
Explanation:
The displaying table looks like:
Table,Beef Burrito,Ceviche,Fried Chicken,Water
3    ,0           ,2      ,1            ,0
5    ,0           ,1      ,0            ,1
10   ,1           ,0      ,0            ,0
For the table 3: David orders "Ceviche" and "Fried Chicken", and Rous orders "Ceviche".
For the table 5: Carla orders "Water" and "Ceviche".
For the table 10: Corina orders "Beef Burrito".
``````

Example 2:

``````
Explanation:
For the table 12: James, Ratesh and Amadeus order "Fried Chicken".
``````

Example 3:

``````
Input: orders = [["Laura","2","Bean Burrito"],["Jhon","2","Beef Burrito"],["Melissa","2","Soda"]]
Output: [["Table","Bean Burrito","Beef Burrito","Soda"],["2","1","1","1"]]
``````

Constraints:

• `1 <= orders.length <= 5 * 10^4`
• `orders[i].length == 3`
• `1 <= customerNamei.length, foodItemi.length <= 20`
• `customerNamei` and `foodItemi` consist of lowercase and uppercase English letters and the space character.
• `tableNumberi `is a valid integer between `1` and `500`.

### Solution

``````#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define SZ(x) int((x).size())
#define endl "\n"
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
x += y;
while (x >= Mod) x -= Mod;
while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
if (x < y)
x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
if (x > y)
x = y;
}
inline int nextInt() {
int x;
cin >> x;
return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
cin >> arg;
rd(args...);
}
#define dbg(x...)                             \
do {                                      \
cout << "\033[32;1m" << #x << " -> "; \
err(x);                               \
} while (0)
void err() {
cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
cout << arg << ' ';
err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
for (auto &v : arg) cout << v << ' ';
err(args...);
}
void ptt() {
cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
cout << ' ' << arg;
ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
cout << arg;
ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
pt(args...);
}
inline ll qpow(ll base, ll n) {
assert(n >= 0);
ll res = 1;
while (n) {
if (n & 1)
res = res * base % mod;
base = base * base % mod;
n >>= 1;
}
return res;
}
constexpr int N = 1e5 + 10;
int n, mp;

string s;

class Solution {
public:
int minNumberOfFrogs(string croakOfFrogs) {
s = croakOfFrogs;
int cnt = {0};
int res = 0;
mp['c'] = 0;
mp['r'] = 1;
mp['o'] = 2;
mp['a'] = 3;
mp['k'] = 4;
for (auto &c : s) {
if (c == 'c')
++cnt;
else {
if (cnt[mp[c] - 1] == 0)
return -1;
--cnt[mp[c] - 1];
++cnt[mp[c]];
}
int sum = cnt + cnt + cnt + cnt;
chmax(res, sum);
}
return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

• Difficulty: Medium
• Tag: `字符串` `计数`

``````输入：croakOfFrogs = "croakcroak"

``````

``````输入：croakOfFrogs = "crcoakroak"

``````

``````输入：croakOfFrogs = "croakcrook"

``````

``````输入：croakOfFrogs = "croakcroa"

``````

• `1 <= croakOfFrogs.length <= 10^5`
• 字符串中的字符只有 `'c'`, `'r'`, `'o'`, `'a'` 或者 `'k'`

You are given the string `croakOfFrogs`, which represents a combination of the string `"croak"` from different frogs, that is, multiple frogs can croak at the same time, so multiple `"croak"` are mixed.

Return the minimum number of different frogs to finish all the croaks in the given string.

A valid `"croak"` means a frog is printing five letters `'c'`, `'r'`, `'o'`, `'a'`, and `'k'` sequentially. The frogs have to print all five letters to finish a croak. If the given string is not a combination of a valid `"croak"` return `-1`.

Example 1:

``````Input: croakOfFrogs = "croakcroak"
Output: 1
Explanation: One frog yelling "croak" twice.
``````

Example 2:

``````Input: croakOfFrogs = "crcoakroak"
Output: 2
Explanation: The minimum number of frogs is two.
The first frog could yell "crcoakroak".
The second frog could yell later "crcoakroak".
``````

Example 3:

``````Input: croakOfFrogs = "croakcrook"
Output: -1
Explanation: The given string is an invalid combination of "croak" from different frogs.
``````

Constraints:

• `1 <= croakOfFrogs.length <= 105`
• `croakOfFrogs` is either `'c'`, `'r'`, `'o'`, `'a'`, or `'k'`.

## D

### Statement

• Difficulty: Hard
• Tag: `动态规划` • `arr` 中有 `n` 个整数。
• `1 <= arr[i] <= m` 其中 `(0 <= i < n)`
• 将上面提到的算法应用于 `arr``search_cost` 的值等于 `k`

``````输入：n = 2, m = 3, k = 1

``````

``````输入：n = 5, m = 2, k = 3

``````

``````输入：n = 9, m = 1, k = 1

``````

``````输入：n = 50, m = 100, k = 25

``````

``````输入：n = 37, m = 17, k = 7

``````

• `1 <= n <= 50`
• `1 <= m <= 100`
• `0 <= k <= n`

You are given three integers `n`, `m` and `k`. Consider the following algorithm to find the maximum element of an array of positive integers: You should build the array arr which has the following properties:

• `arr` has exactly `n` integers.
• `1 <= arr[i] <= m` where `(0 <= i < n)`.
• After applying the mentioned algorithm to `arr`, the value `search_cost` is equal to `k`.

Return the number of ways to build the array `arr` under the mentioned conditions. As the answer may grow large, the answer must be computed modulo `109 + 7`.

Example 1:

``````Input: n = 2, m = 3, k = 1
Output: 6
Explanation: The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]
``````

Example 2:

``````Input: n = 5, m = 2, k = 3
Output: 0
Explanation: There are no possible arrays that satisify the mentioned conditions.
``````

Example 3:

``````Input: n = 9, m = 1, k = 1
Output: 1
Explanation: The only possible array is [1, 1, 1, 1, 1, 1, 1, 1, 1]
``````

Constraints:

• `1 <= n <= 50`
• `1 <= m <= 100`
• `0 <= k <= n`