Translation Notice
This article was machine-translated using DeepSeek-R1.

Original Version: Authored in Chinese by myself

Accuracy Advisory: Potential discrepancies may exist between translations

Precedence: The Chinese text shall prevail in case of ambiguity

Feedback: Technical suggestions regarding translation quality are welcomed

A - Median?

Problem Statement

Given three positive integers $a$, $b$, and $c$, determine whether $b$ is the median of the three numbers (i.e., the second value when sorted in non-decreasing order, not the average).

Constraints:
$1 \le a, b, c \le 100$

Input Format

$a~b~c$

Output Format

Print Yes if $b$ is the median; otherwise, print No.

Sample Cases

$a$	$b$	$c$	Output
5	3	2	`Yes`
2	5	3	`No`
100	100	100	`No`

Analysis

Since this is an A-level problem, the solution is straightforward. ~~I misread it as the average during the contest and got WA..~~ (The description should be clear enough.)

We can directly sort the three numbers or check if either $a \le b \le c$ or $c \le b \le a$ holds.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


#include <cstdio>
using namespace std;

int main()
{
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    puts((a <= b && b <= c) || (c <= b && b <= a)? "Yes": "No");
    return 0;
}

B - Distance Between Tokens

Problem Statement

On an $H \times W$ grid, exactly two cells contain tokens, and the rest are empty. Starting from either token, find the minimum number of moves required to reach the other token by moving up, down, left, or right.

Input Format

The first line contains $H$ and $W$ separated by a space. The next $H$ lines each contain a string of length $W, where -denotes an empty cell ando` denotes a token.

Output Format

Print the minimum number of moves required.

Sample Cases

Sample Input 1

1
2
3


2 3
--o
o--

Sample Output 1

1

3

Sample Input 2

1
2
3
4
5
6


5 4
-o--
----
----
----
-o--

Sample Output 2

1

4

Analysis

No BFS is needed. Since there are no obstacles, directly compute the Manhattan distance between the two tokens: $|x_1 - x_2| + |y_1 - y_2|$.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


#include <cstdio>
#include <vector>
using namespace std;

int main()
{
    int h = 0, w = 0, x1 = -1, y1 = -1, x2 = -1, y2 = -1;
    char c;
    while((c = getchar()) != ' ')
        h = (h << 3) + (h << 1) + (c ^ 48);
    while((c = getchar()) != '\n')
        w = (w << 3) + (w << 1) + (c ^ 48);
    for(; h--; getchar())
        for(int i=w; i--; )
            if(getchar() == 'o')
                if(x1 == -1) x1 = h, y1 = i;
                else { x2 = h, y2 = i; break; }
    printf("%d\n", x1 - x2 + (y1 > y2? y1 - y2: y2 - y1));
    return 0;
}

C - Max - Min Query

Problem Statement

Given an initially empty sequence $S$, process $Q$ operations:

1 x: Append $x$ to $S$.
2 x c: Remove $\min(c, \text{count of } x)$ occurrences of $x$ from $S$.
3: Print the difference between the maximum and minimum values in $S`.

Constraints:
$1 \le Q \le 2 \times 10^5$
$0 \le x \le 10^9$
$1 \le c \le Q$

Input Format

$Q$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

Output Format

For each 3 operation, print the difference.

Analysis

~~A classic STL exercise.~~

Use a multiset or map (C++ specific). Here’s a map approach:

mp[x] returns the count of $x$ (auto-initialized to 0).
mp.begin()->first gives the minimum element.
mp.rbegin()->first gives the maximum element.
mp.erase(x) removes all occurrences of $x$.

Each query can be handled efficiently with these operations.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


#include <cstdio>
#include <map>
using namespace std;

int main()
{
    int q;
    scanf("%d", &q);
    map<int, int> cnt;
    while(q--)
    {
        int op;
        scanf("%d", &op);
        if(op == 3) printf("%d\n", cnt.rbegin()->first - cnt.begin()->first);
        else if(op == 1)
        {
            int x;
            scanf("%d", &x);
            cnt[x] ++;
        }
        else if(op == 2)
        {
            int x, m;
            scanf("%d%d", &x, &m);
            if(cnt[x] > m) cnt[x] -= m;
            else cnt.erase(x);
        }
    }
    return 0;
}

D - FizzBuzz Sum Hard

Problem Statement

Compute the sum of integers from $1$ to $N$ that are not multiples of $A$ or $B$.

Constraints:
$1 \le N, A, B \le 10^9$

Input Format

$N~A~B$

Output Format

Print the answer.

Analysis

By inclusion-exclusion principle, the sum of multiples of $A$ or $B$ is:
$\text{sum}(A) + \text{sum}(B) - \text{sum}(\text{lcm}(A,B))$.

Define:

$f(n) = 1 + 2 + \dots + n = \frac{n(n+1)}{2}$
$\text{sum}(x) = x \cdot f(\lfloor N/x \rfloor)$ (sum of multiples of $x$ up to $N$)

The final answer is:
$f(N) - \text{sum}(A) - \text{sum}(B) + \text{sum}(\text{lcm}(A,B))$

Time complexity is dominated by computing $\text{lcm}(A,B)$ using GCD.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


#include <cstdio>
using namespace std;

using LL = long long;
inline LL sum(const LL& x, const LL& n)
{
    LL cnt = n / x;
    return x * cnt * (cnt + 1LL) >> 1LL;
}

int main()
{
    int n, a, b;
    scanf("%d%d%d", &n, &a, &b);
    LL x = b, y = a;
    while(b ^= a ^= b ^= a %= b);
    LL t = x / a * y; // t = lcm(a, b)
    printf("%lld\n", sum(1, n) - sum(x, n) - sum(y, n) + sum(t, n));
    return 0;
}

E - Distance Sequence

Problem Statement

Count the number of sequences $A = (A_1, \dots, A_N)$ modulo $998244353$ that satisfy:

$1 \le A_i \le M$ for all $i$
$|A_i - A_{i+1}| \ge K$ for all $1 \le i < N$

Constraints:
$2 \le N \le 1000$
$1 \le M \le 5000$
$0 \le K < M$

Input Format

$N~M~K$

Output Format

Print the count modulo $998244353$.

Analysis

Dynamic Programming (DP) approach:

Define $\text{dp}(i, j)$ as the number of valid sequences ending with $j$ at position $i$.
Transition: $\text{dp}(i, j) = \sum \text{dp}(i-1, p)$ where $|j - p| \ge K$.

Optimize using prefix/suffix sums to reduce time complexity from $\mathcal{O}(NM^2)$ to $\mathcal{O}(NM)$. Special case $K=0$ has answer $M^N \bmod 998244353$.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54


#include <cstdio>
#define maxn 1002
#define maxm 5005
#define MOD 998244353
using namespace std;

using LL = long long;
int qpow(LL a, LL b)
{
    LL ans = 1LL;
    while(b > 0)
    {
        if(b & 1LL) ans = ans * a % MOD;
        a = a * a % MOD, b >>= 1LL;
    }
    return ans;
}

inline void mod(int& x) { if(x >= MOD) x -= MOD; }
int dp[2][maxm];

int main()
{
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    if(k == 0)
    {
        printf("%d\n", qpow(m, n));
        return 0;
    }
    for(int i=1; i<=m; i++)
        dp[0][i] = 1;
    for(int i=1; i<n; i++)
    {
        int c = i & 1, p = c ^ 1, s = 0;
        for(int j=k+1; j<=m; j++)
            mod(s += dp[p][j]);
        for(int j=1; j<=m; j++)
        {
            if(j > k) mod(s += dp[p][j - k]);
            mod(dp[c][j] = s);
            if(j + k <= m)
            {
                mod(s -= dp[p][j + k]);
                if(s < 0) s += MOD;
            }
        }
    }
    int ans = 0, t = n & 1 ^ 1;
    for(int i=1; i<=m; i++)
        mod(ans += dp[t][i]);
    printf("%d\n", ans);
    return 0;
}