ABC419

A AtCoder Language

Problem Statement

Takahashi is learning AtCoderish Language.
He memorizes AtCoderish words corresponding to English words.
He knows that red, blue, and green in English respectively correspond to SSS, FFF, and MMM in AtCoderish, and he knows no other words.

You are given a string $S$ consisting of lowercase English letters. If $S$ equals an English word that Takahashi knows corresponds to an AtCoderish word, output the AtCoderish word corresponding to $S$; otherwise, output the string Unknown.

Constraints

• $S$ is a string of length between $1$ and $10$, inclusive, consisting of English letters.

Input

The input is given from Standard Input in the following format:

S

Output

Output a string according to the instructions in the problem statement.

Sample Input 1

red

Sample Output 1

SSS

red in English corresponds to SSS in AtCoderish.

Sample Input 2

orange

Sample Output 2

Unknown

题意

读入一个单词, 将 red, blue, green 改为 SSS, FFF, MMM 输出, 其余单词输出 Unknown.

B Get Min

Problem Statement

There is an empty bag.
You are given $Q$ queries. Process these queries in order and output the answer to each type-$2$ query.

Each query is of one of the following types.

• Type $1$: Given as input in the format 1 x. Put a ball with the integer $x$ written on it into the bag.
• Type $2$: Given as input in the format 2. Pick out one ball with the minimum integer written on it from the balls in the bag, and report that integer as the answer. This query is not given when the bag contains no balls.

Constraints

• $2 \leq Q \leq 100$
• In a type-$1$ query, $1 \leq x \leq 100$.
• When a type-$2$ query is given, the bag is not empty.
• At least one type-$2$ query is given.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

Q
query_1
query_2
...
query_Q

Here, $\text{query}_i$ is the $i$-th query and is given in one of the following formats:

1 x
2

Output

Let $q$ be the number of type-$2$ queries, and output $q$ lines.
The $i$-th line should contain the answer to the $i$-th type-$2$ query.

Sample Input 1

5
1 6
1 7
2
1 1
2

Sample Output 1

6
1

Initially, the bag contains no balls.
The 1st query puts a ball with $6$ written on it into the bag.
The 2nd query puts a ball with $7$ written on it into the bag.
In the 3rd query, the bag contains a ball with $6$ written on it and a ball with $7$ written on it, so you pick out the ball with $6$ written on it. The answer to this query is $6$.
The 4th query puts a ball with $1$ written on it into the bag.
In the 5th query, the bag contains a ball with $1$ written on it and a ball with $7$ written on it, so you pick out the ball with $1$ written on it. The answer to this query is $1$.

Sample Input 2

3
1 1
1 1
2

Sample Output 2

1

The bag may contain multiple balls with the same integer.

题意

维护一个数组, 支持 1 x 放入 x. 2 删除当前数组中最小的元素并输出.

题解

数据范围很小, 直接模拟.

C King’s Summit

Problem Statement

There is a grid with $10^9$ rows and $10^9$ columns. Let $(i, j)$ denote the square at the $i$-th row from the top and $j$-th column from the left.

There are $N$ people on the grid. Initially, the $i$-th person is at square $(R_i, C_i)$.

The time starts at $0$. Each person can do the following move at times $1, 2, 3, 4, \ldots$.

• Stay at the current position, or move to an $8$-adjacent square. It is forbidden to leave the grid. Formally, let square $(i, j)$ be the current square, and move to one of the squares $(i - 1, j - 1), (i - 1, j), (i - 1, j + 1), (i, j - 1), (i, j), (i, j + 1), (i + 1, j - 1), (i + 1, j), (i + 1, j + 1)$ that exists. Assume that the move takes no time.

Find the minimum possible time when the $N$ people are at the same square.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq R_i, C_i \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N
R_1 C_1
R_2 C_2
...
R_N C_N

Output

Output the answer.

Sample Input 1

3
1 2
8 1
7 5

Sample Output 1

3

All people will be at square $(5, 4)$ at time $3$ if each person moves as follows.

• At time $1$, the 1st person moves to square $(3, 4)$, the 2nd person moves to square $(6, 2)$, and the 3rd person moves to square $(7, 2)$.
• At time $2$, the 1st person moves to square $(4, 4)$, the 2nd person moves to square $(5, 3)$, and the 3rd person moves to square $(6, 3)$.
• At time $3$, the 1st person moves to square $(5, 4)$, the 2nd person moves to square $(5, 4)$, and the 3rd person moves to square $(5, 4)$.

Sample Input 2

2
5 5
5 5

Sample Output 2

0

All people start at the same square.

Sample Input 3

4
1 1
1 10^9
10^9 1
10^9 10^9

Sample Output 3

999999999

题意

平面坐标系中有 $n$ 个人, 每一时刻每个人都可以往八个方向移动一格, 问最少要多少时间所有人能到同一个坐标.

题解

由于是八连通, 所以分别考虑横轴和纵轴, 取最大即可. 而单一方向显然是到中点汇合.

D Substr Swap

Problem Statement

You are given length-$N$ lowercase English strings $S$ and $T$, and $M$ pairs of integers $(L_1,R_1),(L_2,R_2),\ldots,(L_M,R_M)$.

Perform the following operation for $i=1,2,\ldots,M$ in order:

• Swap the $L_i$-th through $R_i$-th characters of $S$ and the $L_i$-th through $R_i$-th characters of $T$.

For example, if $S$ is abcdef, $T$ is ghijkl, and $(L_i,R_i)=(3,5)$, then $S$ and $T$ become abijkf and ghcdel, respectively.

Find the string $S$ after performing the $M$ operations.

Constraints

• $1\leq N\leq 5\times 10^5$
• $1\leq M\leq 2\times 10^5$
• Each of $S$ and $T$ is a length-$N$ lowercase English strings.
• $1\leq L_i\leq R_i\leq N$
• $N$, $M$, $L_i$, and $R_i$ are integers.

Input

The input is given from Standard Input in the following format:

N M
S
T
L_1 R_1
L_2 R_2
...
L_M R_M

Output

Output the $S$ after performing the $M$ operations.

Sample Input 1

5 3
apple
lemon
2 4
1 5
3 5

Sample Output 1

lpple

Initially, $S$ and $T$ are apple and lemon, respectively.

• After the operation for $i=1$, $S$ and $T$ are aemoe and lppln, respectively.
• After the operation for $i=2$, $S$ and $T$ are lppln and aemoe, respectively.
• After the operation for $i=3$, $S$ and $T$ are lpple and aemon, respectively.

Thus, the string $S$ after the three operations is lpple.

Sample Input 2

1 1
a
z
1 1

Sample Output 2

z

题意

给出两个长度相同的字符串, 有 $m$ 个操作, 每个操作给出一个区间 $L_i,R_i$, 将这两个字符串对应位置交换.

题解

由于每次都是对应位置交换, 交换两次后变回原样, 所以只要记录每个位置最终是否交换即可. 利用差分统计每个位置的交换次数.

E Subarray Sum Divisibility

Problem Statement

You are given a length-$N$ integer sequence $A = (A_1, A_2, \ldots, A_N)$.

Your goal is to perform the following operation repeatedly so that for every length-$L$ contiguous subarray of $A$, the sum is a multiple of $M$.

• Choose an integer $i$ such that $1 \leq i \leq N$, and increase the value of $A_i$ by $1$.

Find the minimum possible number of operations before achieving the goal.

Constraints

• $1 \leq N, M \leq 500$
• $1 \leq L \leq N$
• $0 \leq A_i < M$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N L M
A_1 A_2 ... A_N

Output

Output the answer.

Sample Input 1

4 3 5
4 2 1 3

Sample Output 1

4

By performing the operation once choosing $i = 2$, twice choosing $i = 3$, and once choosing $i = 4$, you get $A = (4, 3, 3, 4)$ with a total of four operations, where every length-$3$ contiguous subarray sums to a multiple of $5$.

Sample Input 2

1 1 1
0

Sample Output 2

0

题意

给出一个长为 $N$ 的数组, 和两个参数 $M,L$, 每次操作可以选择一个元素使其值加一, 求最少的操作次数, 使得该数组的 $N-L+1$ 个长度为 $L$ 的子数组(连续)的和均是 $M$ 的倍数.

题解

先来研究满足条件的数组的性质. 由于只要求整除, 所以我们不妨在模 $M$ 的意义下考虑. 设下标从 $0$ 开始.

对于第一组 $\sum\limits_{i=0}^{L-1} a_i \equiv 0 \pmod{M}$.
For the second group: $\sum\limits_{i=1}^{L} a_i \equiv 0 \pmod{M}$.

To satisfy both, we must have $a_0 \equiv a_L \pmod{M}$. Similarly, the array $a$ is periodic modulo $M$ with period $L$.

Thus, we only need to determine the first $L$ elements.

We use dynamic programming: let $f_{i,j}$ be the minimum number of operations to assign values to the first $i$ positions such that their sum modulo $M$ is $j$.

The answer is $f_{L,0}$. Transitions enumerate the current value modulo $M$ and previous sum modulo $M$. The cost to adjust the current element to a target modulo value can be precomputed.

Time complexity: $O(NM + LM^2)$. This is sufficient. There also exists an $O(NM)$ solution.

F All Included

Problem Statement

You are given $N$ lowercase English strings $S_1,S_2,\ldots,S_N$, and an integer $L$.

Find the number, modulo $998244353$, of length-$L$ lowercase English strings that contain all of $S_1,S_2,\ldots,S_N$ as substrings.

What is a substring? 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, ab, bc, and bcd are substrings of abcd, while ac, dc, and e are not substrings of abcd.

Constraints

• $1\leq N\leq 8$
• $1\leq L\leq 100$
• $N$ and $L$ are integers.
• Each $S_i$ is a string of length between $1$ and $10$, inclusive, consisting of lowercase English letters.
• $S_i \ne S_j\ (i \ne j)$

Input

The input is given from Standard Input in the following format:

N L
S_1
S_2
...
S_N

Output

Output the answer.

Sample Input 1

2 4
ab
bc

Sample Output 1

51

Some of the strings that satisfy the condition are abcz and cabc. acbd does not contain ab as a substring, so it does not satisfy the condition.

Sample Input 2

1 1
a

Sample Output 2

1

Sample Input 3

3 10
abc
def
ghi

Sample Output 3

1258290

题意

给出 $N$ 个小写字母字符串, 求长度为 $L$ 的字符串的个数, 满足这 $N$ 个串均作为大字符串的子串(连续)出现过.

题解

Consider DP on an Aho–Corasick automaton. Constructing a string of length $L$ corresponds to walking $L$ steps on the automaton.

To enforce that all $N$ patterns appear, use bitmask DP.

Let $f_{i,j,\text{mask}}$ be the number of ways to build a string of length $i$, ending at automaton node $j$, having matched the set of patterns indicated by mask.

Transition by trying all 26 next characters and updating node and mask accordingly.

Time complexity: $O(2^N \cdot L \cdot C \cdot |\Sigma|)$, where $C$ is the number of automaton states (at most sum of pattern lengths), and $|\Sigma| = 26$.

G Count Simple Paths 2

Problem Statement

You are given a simple connected undirected graph with $N$ vertices numbered $1$ to $N$ and $M$ edges. The $i$-th edge connects vertices $u_i$ and $v_i$.

For each $k=1,2,\ldots,N-1$, find the number of simple paths from vertex $1$ to vertex $N$ that contain exactly $k$ edges.

Constraints

• $2\leq N\leq 2\times 10^5$
• $N-1\leq M\leq N+20$
• $1\leq u_i\lt v_i\leq N$
• The given graph is a simple connected undirected graph.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
u_1 v_1
u_2 v_2
...
u_M v_M

Output

Output the answers in the following format:

ans_1
ans_2
...
ans_{N-1}

$\mathrm{ans}_i$ is the number of simple paths from vertex $1$ to vertex $N$ that contain exactly $i$ edges.

Sample Input 1

5 6
1 2
1 3
2 4
3 4
3 5
4 5

Sample Output 1

0
1
2
1

For each $k=1,2,3,4$, the simple paths from vertex $1$ to vertex $5$ that contain exactly $k$ edges are as follows.

• $k=1$: None
• $k=2$: $1\to 3\to 5$
• $k=3$: $1\to 2\to 4\to 5$ and $1\to 3\to 4\to 5$
• $k=4$: $1\to 2\to 4\to 3\to 5$

Sample Input 2

2 1
1 2

Sample Output 2

1

Sample Input 3

10 15
...

Sample Output 3

…

题意

给出一个有特殊限制的图 ($M \leq N + 20$), 对任意整数 $k$ ($1 \leq k \leq N - 1$) 输出从 $1$ 号点到 $N$ 号点恰好经过 $k$ 条边的简单路径个数.

题解

Note that the graph has at most $21$ extra edges beyond a spanning tree. Thus, the graph is “almost a tree”.

In a tree, there is exactly one simple path from $1$ to $N$. Adding extra edges creates alternative routes, but the total number of simple paths is bounded by $2^{M - N + 1} \leq 2^{21}$.

Proof sketch: Over $\mathbb{F}_2$, the incidence matrix has rank $N - 1$, so the solution space to $Bx = b$ (where $b$ has 1s at vertices 1 and $N$) has dimension $M - (N - 1)$. Hence, at most $2^{M - N + 1}$ edge subsets form a path from 1 to $N$. Each simple path is one such solution.

Thus, we can enumerate all simple paths via DFS, but naively visiting all $N$ nodes per path is too slow.

Instead, build a virtual tree containing:

• vertices $1$ and $N$,
• all endpoints of the $M - (N - 1)$ non-tree edges.

This virtual tree has at most $2 + 2 \cdot 21 = 44$ nodes. Contract all degree-2 chains between these key nodes.

Then, run DFS only on this reduced graph to enumerate all simple paths from $1$ to $N$, recording their lengths.

Finally, aggregate counts by path length.

Time complexity: $O(2^{M - N + 1} \cdot \text{poly}(M))$, which is acceptable.