AtCoder Beginner Contest 418

A I’m a teapot

Takahashi is a teapot.
Since he is a teapot, he will gladly accept tea, but will refuse any other liquid.
Determine whether you can pour a liquid named $S$ into him.

You are given a string $S$ of length $N$ consisting of lowercase English letters.
Determine whether $S$ is a string that ends with tea.

Constraints

• $1\le N\le 20$
• $N$ is an integer.
• $S$ is a string of length $N$ consisting of lowercase English letters.

翻譯

高橋是一個茶壺。
既然他是茶壺，他就會欣然接受茶水，而拒絕其他任何液體。
確定能否向它倒入名為 $S$ 的液體。

給你一個長度為 $N$ 的字符串 $S$ ，由小寫英文字母組成。
請判斷 $S$ 是否是以 tea 結尾的字符串。

約束

• $1\le N\le 20$
• $N$ 是整數。
• $S$ 是長度為 $N$ 的字符串，由小寫英文字母組成。

分析：判斷字符的結尾是不是 tea 即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;void solve() {int n; string s; cin >> n >> s;bool f = (n > 2 && s.substr(n - 3, 3) == "tea");cout << (f ? "Yes" : "No") << "\n";
}
int main() {// freopen("1.in", "r", stdin);int T = 1; while (T--) solve();return 0;
}

B You’re a teapot

I begin with T and end with T, and I am full of T. What am I?

For a string $t$, define the filling rate as follows:

• If the first and last characters of $t$ are both t and $|t|\ge 3$: Let $x$ be the number of t in $t$. Then the filling rate of $t$ is $\frac{x?2}{|t|?2}$, where $|t|$ denotes the length of $t$.
• Otherwise: the filling rate of $t$ is $0$.

You are given a string $S$. Find the maximum possible filling rate of a substring of $S$.

What is a substring?
A substring of $S$ is a string obtained by removing zero or more characters from the beginning and the end of $S$. For example, ab, bc, and bcd are substrings of abcd, while ac, dc, and e are not substrings of abcd.

Constraints

• $1\le |S|\le 100$
• $S$ is a string consisting of lowercase English letters.

翻譯

我是什么？

對于一個字符串 $t$ ，定義填充率如下：

• 如果 $t$ 的第一個字符和最后一個字符都是 "T "和 $|t|\ge 3$ ：設 $x$ 是 $t$ 中 "t "的個數。那么 $t$ 的填充率為 $\frac{x?2}{|t|?2}$ ，其中 $|t|$ 表示 $t$ 的長度。
• 否則： $t$ 的填充率為 $0$ 。

給你一個字符串 $S$ 。求 $S$ 子串的最大填充率。

什么是子串？
$S$ 的子串是指從 $S$ 的開頭和結尾刪除零個或多個字符后得到的字符串。例如，ab、bc和bcd是abcd的子串，而ac、dc和e不是abcd的子串。

約束

• $1\le |S|\le 100$
• $S$ 是一個由小寫英文字母組成的字符串。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;void solve() {string s; cin >> s;int x = 0, n = s.size();double ans = 0;for (int i = 0; i < n; i++)for (int j = i + 1; j < n; j++)if (s[i] == 't' && s[j] == 't') {int x = 0, len = j - i + 1;for (int k = i; k <= j; k++)x += (s[k] == 't');ans = max(ans, (x - 2.0) / (len - 2.0));}cout << fixed << setprecision(12) << ans << "\n";
}
int main() {// freopen("1.in", "r", stdin);int T = 1; while (T--) solve();return 0;
}

C Flush

On the poker table, there are tea bags of $N$ different flavors. The flavors are numbered from 1 through $N$, and there are $A_i$ tea bags of flavor $i$ ($1\le i\le N$).

You will play a game using these tea bags. The game has a parameter called difficulty between 1 and $A_1+?+A_N$, inclusive. A game of difficulty $b$ proceeds as follows:

1. You declare an integer $x$. Here, it must satisfy $b\le x\le A_1+?+A_N$.
2. The dealer chooses exactly $x$ tea bags from among those on the table and gives them to you.
3. You check the flavors of the $x$ tea bags you received, and choose $b$ tea bags from them.
4. If all $b$ tea bags you chose are of the same flavor, you win. Otherwise, you lose.

The dealer will do their best to make you lose.

You are given $Q$ queries, so answer each of them. The $j$-th query is as follows:

• For a game of difficulty $B_j$, report the minimum integer $x$ you must declare at the start to guarantee a win. If it is impossible to win, report $?1$ instead.

Constraints

• $1\le N\le 3\times 10^5$
• $1\le Q\le 3\times 10^5$
• $1\le A_i\le 10^6$ ($1\le i\le N$)
• $1\le B_j\le \min (10^9,A_1+?+A_N)$ ($1\le j\le Q$)
• All input values are integers.

翻譯：
在撲克桌上，有不同口味的茶包。口味從 $1$ 到 $N$ 編號，有 $A_i$ 個茶包口味 $i$（$1\le i\le N$）。
你將用這些茶包玩游戲。游戲有一個名為難度的參數，介于 $1$ 和 $a_1+?+a_N$ 之間。難度游戲 $b$ 的收益如下：

1. 聲明一個整數 $x$。這里，它必須滿足 $b\le x\le A_1+?+A_N$。
2. 經銷商從桌上的茶包中準確地選擇 $x$ 個茶包，并將其送給您。
3. 您檢查收到的 $x$ 個茶包，并從中選擇 $b$ 個茶包。
4. 如果你選擇的 $b$ 個茶包都是相同的味道，你就贏了。否則，你輸了。

經銷商會盡最大努力讓你輸。

您會收到 $Q$ 的查詢，請逐一回答。第 $j$ 個查詢如下：

• 對于難度為 $B_j$ 的游戲，報告您必須在開始時聲明的最小整數 $x$，以確保獲勝。如果不可能獲勝，則報告 $?1$。

約束條件

• $1\le N\le 3\times 10^5$
• $1\le Q\le 3\times 10^5$
• $1\le A_i\le 10^6$ ($1\le i\le N$)
• $1\le B_j\le \min (10^9,A_1+?+A_N)$ ($1\le j\le Q$)
• 所有輸入值都是整數。

分析：

本題目要模擬樣例，找到題目所求：當相同元素的數量至少為 $b$ 的需要最少有解數量 $x$。

解法：考慮對原數組 $a_i$ 排序，求出前綴和 $s_i$，二分查詢第一個$\ge b$ 的元素位置 $id$，如果答案存在，則 $ans=s_{id?1}+(b?1)\times (n?id+1)+1$；否則 $ans=?1$。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int n, q, a[N], b;
ll s[N];void solve() {cin >> n >> q;for (int i = 1; i <= n; i++) cin >> a[i];sort(a + 1, a + 1 + n);for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];while (q--) {cin >> b;int id = lower_bound(a + 1, a + 1 + n, b) - a;ll ans = -1;if (id <= n && a[id] >= b)ans = s[id - 1] + 1ll * (b - 1) * (n - id + 1) + 1;cout << ans << "\n";}
}
int main() {// freopen("1.in", "r", stdin);int T = 1; while (T--) solve();return 0;
}

D XNOR Operation

This problem is a subproblem of Problem G.

A non-empty string $S$ consisting of 0 and 1 is called a beautiful string when it satisfies the following condition:

• (Condition) You can perform the following sequence of operations until the length of $S$ becomes $1$ and make the only character remaining in $S$ be 1.
  1. Choose any integer $i$ satisfying $1\le i\le |S|?1$.
  2. Define an integer $x$ as follows:
     • If $S_i=$ 0 and $S_{i+1}=$ 0, let $x=1$.
     • If $S_i=$ 0 and $S_{i+1}=$ 1, let $x=0$.
     • If $S_i=$ 1 and $S_{i+1}=$ 0, let $x=0$.
     • If $S_i=$ 1 and $S_{i+1}=$ 1, let $x=1$.
  3. Remove $S_i$ and $S_{i+1}$, and insert the digit corresponding to $x$ in their place.
     For example, if $S=$ 10101 and you choose $i=2$, the string after the operation is 1001.

You are given a string $T$ of length $N$ consisting of 0 and 1.
Find the number of beautiful strings that are substrings of $T$. Even if two substrings are identical as strings, count them separately if they are taken from different positions.

What are substrings? A substring of $S$ is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of $S$.
For example, 10 is a substring of 101, but 11 is not a substring of 101.

Constraints

• $1\le N\le 2\times 10^5$
• $N$ is an integer.
• $T$ is a string of length $N$ consisting of 0 and 1.

翻譯：

本問題是問題 G 的子問題。

由 0 和 1 組成的非空字符串 $S$ 滿足以下條件時，稱為優美字符串：

• 條件）你可以執行以下一系列操作，直到 $S$ 的長度變為 $1$ ，并使 $S$ 中唯一剩下的字符是 1。
  1. 選擇滿足 $1\le i\le |S|?1$ 的任意整數 $i$ 。
  2. 定義整數 $x$ 如下：
     • 如果 $S_i=$ 0 且 {98421818}0和 $S_{i+1} =$ 0，設 $x=1$ .
     • 若 $S_i=$ 0 且 {56774510} 0, 則設 $x=1$ .0和 $S_{i+1} =$ 1，則 $x=0$ .
     • 若 $S_i=$ 1，且 $S_{i+1}=$ 0，則讓 {12243413}.0"，則 $x=0$ .
     • 如果 $S_i=$ 1 和 {1848987} 0, 讓 {297737}.1且 $S_{i+1} =$ 1`，則設 $x=1$ 。
  3. 刪除 $S_i$ 和 $S_{i+1}$ ，并插入與 $x$ 相對應的數字。
     例如，如果 $S=$ 10101"，而您選擇了 $i=2$ ，則操作后的字符串為 “1001”。

給定長度為 $N$ 的字符串 $T$ 由 0 和 1 組成。
求作為 $T$ 的子串的美麗字符串的個數。即使兩個子串是相同的字符串，如果它們取自不同的位置，也要分別計算。

什么是子串？ $S$ 的子串是刪除 $S$ 開頭的零個或多個字符和結尾的零個或多個字符后得到的字符串。
例如，10是101的子串，但11不是101的子串。

約束

• $1\le N\le 2\times 10^5$
• $N$ 是整數。
• $T$ 是長度為 $N$ 的字符串，由 0 和 1 組成。

分析：

E Trapezium

There are $N$ points on a two-dimensional plane, with the $i$-th point at coordinates $(X_i,Y_i)$. It is guaranteed that no two points are at the same position, and no three points are collinear.

Among the combinations of four points from these points, how many combinations can form a trapezoid as a polygon with those four points as vertices?

Constraints

• $4\le N\le 2000$
• $0\le X_i,Y_i\le 10^7$ ($1\le i\le N$)
• No two points are at the same location.
• No three points are collinear.
• All input values are integers.

翻譯：
在一個二維平面上有 $N$ 個點，其中第 $i$ 個點的坐標為 $(X_i,Y_i)$ 。保證沒有兩個點在同一位置，也沒有三個點是共線的。

在這些點的四點組合中，以這四點為頂點能組成梯形多邊形的組合有多少種？

約束

• $4\le N\le 2000$
• $0\le X_i,Y_i\le 10^7$ ( $1\le i\le N$ )
• 沒有兩個點在同一位置。
• 沒有三個點是相鄰的。
• 所有輸入值均為整數。

分析：

F We’re teapots

There are $N$ teapots arranged in a row, numbered from $1$ to $N$ from left to right.

There is a sequence of integers $(a_1,\dots ,a_N)$, initially with values $a_1=?=a_N=?1$.

You will fill each teapot with either tea or coffee so that the following conditions are all satisfied:

• For any two adjacent teapots, at least one of them contains tea.
• For any integer $i$ satisfying $1\le i\le N$, if $a_i\ne ?1$, then exactly $a_i$ of teapots $1,\dots ,i$ contain coffee.

You are given $Q$ queries, which you should process in the given order.

The $j$-th query ($1\le j\le Q$) is as follows:

• Change the value of $a_{X_j}$ to $Y_j$. Then, print the number, modulo $998244353$, of ways to fill the teapots satisfying the conditions.

Constraints

• $2\le N\le 2\times 10^5$
• $1\le Q\le 2\times 10^5$
• $1\le X_j\le N$ ($1\le j\le Q$)
• $?1\le Y_j\le X_j$ ($1\le j\le Q$)
• All input values are integers.

翻譯

有 $N$ 個茶壺排成一排，從左到右依次編號為 $1$ 至 $N$ 。

有一串整數 $(a_1,\dots ,a_N)$ ，最初的值為 $a_1=?=a_N=?1$ 。

你要在每個茶壺中注入茶或咖啡，以滿足以下所有條件：

• 對于任意兩個相鄰的茶壺，其中至少有一個裝有茶葉。
• 對于滿足 $1\le i\le N$ 的任意整數 $i$ ，如果有 $a_i\ne ?1$ ，那么在 $1,\dots ,i$ 的茶壺中，正好有 $a_i$ 個茶壺裝有咖啡。

給你 $Q$ 個查詢，你應按給定的順序處理這些查詢。

$j$ -th 查詢（ $1\le j\le Q$ ）如下：

• 將 $a_{X_j}$ 的值改為 $Y_j$ 。然后，打印出滿足條件的茶壺的裝水方式的數量，模數為 $998244353$ 。

限制因素

• $2\le N\le 2\times 10^5$
• $1\le Q\le 2\times 10^5$
• $1\le X_j\le N$ ( $1\le j\le Q$ )
• $?1\le Y_j\le X_j$ ( $1\le j\le Q$ )
• 所有輸入值均為整數。

分析：

G Binary Operation

There are $16$ integer tuples $(A,B,C,D)$ satisfying A,B,C,D∈{0,1}A, B, C, D \in \lbrace 0, 1 \rbraceA,B,C,D∈{0,1}. For each of them, solve the following problem.

A non-empty string $S$ consisting of 0 and 1 is called a beautiful string when it satisfies the following condition:

• (Condition) You can perform the following sequence of operations until the length of $S$ becomes $1$ and make the only character remaining in $S$ be 1.
  1. Choose any integer $i$ satisfying $1\le i\le |S|?1$.
  2. Define an integer $x$ as follows:
     • If $S_i=$ 0 and $S_{i+1}=$ 0, let $x=A$.
     • If $S_i=$ 0 and $S_{i+1}=$ 1, let $x=B$.
     • If $S_i=$ 1 and $S_{i+1}=$ 0, let $x=C$.
     • If $S_i=$ 1 and $S_{i+1}=$ 1, let $x=D$.
  3. Remove $S_i$ and $S_{i+1}$, and insert the digit corresponding to $x$ in their place.
     For example, if $S=$ 10101 and you choose $i=2$, the string after the operation is 1001 if $B=0$, and 1101 if $B=1$.

You are given a string $T$ of length $N$ consisting of 0 and 1.

• Let $L$ be the length of the longest beautiful string that is a substring of $T$ (if no substring of $T$ is a beautiful string, let $L=?1$),
• Let $M$ be the number of beautiful strings that are substrings of $T$.

Find $L$ and $M$. Even if two substrings are identical as strings, count them separately if they are taken from different positions.

What are substrings?
A substring of $S$ is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of $S$.
For example, 10 is a substring of 101, but 11 is not a substring of 101.

Constraints

• $1\le N\le 2\times 10^5$
• $N$ is an integer.
• $T$ is a string of length $N$ consisting of 0 and 1.

翻譯

有 $16$ 個整數元組 $(A,B,C,D)$ 滿足 A,B,C,D∈{0,1}A, B, C, D \in \lbrace 0, 1 \rbraceA,B,C,D∈{0,1} 。請分別求解下列問題。

由 "0 "和 "1 "組成的非空字符串 $S$ 滿足以下條件時，稱為優美字符串：

• （條件）你可以執行下面的操作序列，直到 $S$ 的長度變為 $1$ ，并使 $S$ 中唯一剩下的字符是 1。

1. 選擇滿足 $1\le i\le |S|?1$ 的任意整數 $i$ 。
2. 定義整數 $x$ 如下：

• 如果 $S_i=$ 0 和 {53892861} 0 。0和 $S_{i+1} =$ 0，則設 $x=A$ .
• 如果 $S_i=$ 0 且 {346645525} 0, 則讓 $x=A$ .0 "和 $S_{i+1}=$ “1”，設為 $x=B$ 。
• 如果 $S_i=$ 1 和 {3676760} 1，令 $x=B$ .1 “和 $S_{i+1}=$ 0”，則 $x=C$ .
• 如果 $S_i=$ 1和 {66227549} 0，讓 $x=C$ .1和 $S_{i+1} =$ 1.如果 $S_i =$ 1和 $S_{i+1} =$1`, 則讓 $x=D$ .

3. 刪除 $S_i$ 和 $S_{i+1}$ ，并插入與 $x$ 相對應的數字。
   例如，如果 $S=$ 10101"，并選擇 $i=2$ ，則操作后的字符串如果是 $B=0$ 則為 “1001”，如果是 $B=1$ 則為 “1101”。

給出長度為 $N$ 的字符串 $T$ ，它由 0 和 1 組成。

• 設 $L$ 是長度為 $T$ 的子串的最長優美字符串（如果 $T$ 的子串都不是優美字符串，則設為 $L=?1$ ）、
• 設 $M$ 是作為 $T$ 子串的優美字符串的個數。

找出 $L$ 和 $M$ 。即使兩個子串是相同的字符串，如果它們取自不同的位置，也要分別計算。

什么是子串？
$S$ 的子串是刪除 $S$ 開頭的零個或多個字符和結尾的零個或多個字符后得到的字符串。
例如，10是101的子串，但11不是101的子串。

約束

• $1\le N\le 2\times 10^5$
• $N$ 是整數。
• $T$ 是長度為 $N$ 的字符串，由 0 和 1 組成。
  分析：