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 - Square Inequality

Problem Statement

Given three integers $A$, $B$, and $C$, determine if $A^2 + B^2 < C^2$ holds.

$0 \le A,B,C \le 1000$

Input Format

$A~B~C$

Output Format

Print Yes if $A^2 + B^2 < C^2$; otherwise, print No.

Samples

$A$	$B$	$C$	Output
$2$	$2$	$4$	`Yes`
$10$	$10$	$10$	`No`
$3$	$4$	$5$	`No`

Analysis

Directly compute according to the problem statement.

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 * a + b * b < c * c? "Yes": "No");
    return 0;
}

B - Intersection

Problem Statement

Given two sequences of length $N$: $A = (A_1, A_2, A_3, \dots, A_N)$ and $B = (B_1, B_2, B_3, \dots, B_N)$. Find the number of integers $x$ satisfying:

For all $1 \le i \le N$, $A_i \le x \le B_i$.

$1 \le N \le 100$
$1 \le A_i \le B_i \le 1000$

Input Format

$N$
$A_1~A_2~\dots~A_N$
$B_1~B_2~\dots~B_N$

Output Format

Print the answer.

Samples

Sample Input1

Sample Output1

1

3

Possible $x$ values: $3$, $4$, $5$.

Sample Input2

Sample Output2

1

0

No valid $x$ exists.

Sample Input3

Sample Output3

1

2

Analysis

The constraints can be decomposed into:

For all $1 \le i \le N$, $A_i \le x$.
For all $1 \le i \le N$, $x \le B_i$.

This simplifies to $\max(A) \le x \le \min(B)$. The valid count is $\max(0, \min(B) - \max(A) + 1)$.

Code

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


#include <cstdio>
using namespace std;

int main()
{
    int n, maxa = 1, minb = 1000;
    scanf("%d", &n);
    for(int i=0; i<n; i++)
    {
        int a;
        scanf("%d", &a);
        if(a > maxa) maxa = a;
    }
    while(n--)
    {
        int b;
        scanf("%d", &b);
        if(b < minb) minb = b;
    }
    if(maxa > minb) puts("0");
    else printf("%d\n", minb - maxa + 1);
    return 0;
}

C - IPFL

Problem Statement

Given a string $S$ of length $2N$ consisting of uppercase letters. Process $Q$ queries. Each query consists of three integers $T_i, A_i, B_i$:

If $T_i = 1$: swap the $A_i$-th and $B_i$-th characters of $S$.
If $T_i = 2$: swap the first $N$ and last $N$ characters of $S$.

Output $S$ after all queries.

$1 \le N \le 2 \times 10^5$
$|S| = 2N$
$1 \le Q \le 3 \times 10^5$
$1 \le T_i \le 2$, $1 \le A_i < B_i \le 2N$ if $T_i = 1$; $A_i = B_i = 0$ if $T_i = 2$.

Input Format

$N$
$S$
$Q$
$T_1~A_1~B_1$
$T_2~A_2~B_2$
$\hspace{18pt}\vdots$
$T_Q~A_Q~B_Q$

Samples

Sample Input1

Sample Output1

1

LPFI

$\text{FLIP} \to \text{IPFL} \to \text{LPFI}$

Sample Input2

Sample Output2

1

ILPF

Analysis

The $\mathcal O(NQ)$ simulation approach would TLE. Optimize by tracking flip state:

Maintain flipped flag. For $T_i = 2$, toggle flipped.
For $T_i = 1$, adjust indices based on flipped status to compute actual positions.

Time complexity: $\mathcal O(N + Q)$.

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


#include <cstdio>
#define maxn 400005
using namespace std;

char s[maxn];
int n;

inline void swap(char& x, char& y) { x ^= y ^= x ^= y; }
inline char& calc(int pos) { return s[pos < n? pos + n: pos - n]; }

int main()
{
    scanf("%d%s", &n, s);
    int q;
    scanf("%d", &q);
    bool flipped = false;
    while(q--)
    {
        int t, a, b;
        scanf("%d%d%d", &t, &a, &b);
        a --, b --;
        if(t == 2) flipped = !flipped;
        else if(flipped) swap(calc(a), calc(b));
        else swap(s[a], s[b]);
    }
    if(flipped)
        for(int i=0; i<n; i++)
            swap(s[i], s[n + i]);
    puts(s);
    return 0;
}

D - RGB Coloring 2

Problem Statement

Given a simple undirected graph with $N$ vertices and $M$ edges. Count valid colorings using three colors where adjacent vertices have different colors.

$1 \le N \le 20$
$0 \le M \le \frac{N(N-1)}{2}$

Input Format

$N~M$
$A_1~B_1$
$A_2~B_2$
$\hspace{12pt}\vdots$
$A_M~B_M$

Output Format

Print the answer.

Samples

Sample Input1

Sample Output1

1

6

Valid colorings: RGB, RBG, GRB, GBR, BRG, BGR.

Sample Input2

1

3 0

Sample Output2

1

27

Sample Input3

Sample Output3

1

0

Sample Input4

1

20 0

Sample Output4

1

3486784401

Analysis

For each connected component, count valid colorings via DFS. Multiply results across components. Total attempts are bounded by $3 \times 2^{N-1}$.

Code

~~Seems no one noticed that unsigned int could be used…~~

 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
55
56


#include <cstdio>
#include <vector>
#define maxn 25
using namespace std;

vector<int> G[maxn];
int col[maxn], dep[maxn];

inline int next(int c) { return (c + 1) % 3; }

int paint(int v)
{
    for(int u: G[v])
        if(col[v] == col[u])
            return 0;
    int ans = 1;
    for(int u: G[v])
    {
        if(dep[u] == -1) dep[u] = dep[v] + 1;
        if(dep[u] == dep[v] + 1)
        {
            col[u] = next(col[v]);
            int res = paint(u);
            col[u] = next(col[u]);
            res += paint(u);
            col[u] = -1;
            if(res == 0) return 0;
            ans *= res;
        }
    }
    return ans;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    while(m--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        G[--x].push_back(--y);
        G[y].push_back(x);
    }
    for(int i=0; i<n; i++)
        col[i] = dep[i] = -1;
    unsigned int ans = 1;
    for(int i=0; i<n; i++)
        if(dep[i] == -1)
        {
            col[i] = dep[i] = 0;
            ans *= 3U * paint(i);
        }
    printf("%u\n", ans);
    return 0;
}

E - Permutation

Problem Statement

Count permutations of $(1, 2, \dots, N)$ satisfying:

For each $1 \le i \le M$, among the first $X_i$ elements, at most $Z_i$ are $\le Y_i$.

$2 \le N \le 18$
$0 \le M \le 100$
$1 \le X_i, Y_i < N$
$0 \le Z_i < N$

Input Format

$N~M$
$X_1~Y_1~Z_1$
$X_2~Y_2~Z_2$
$\hspace{18pt}\vdots$
$X_M~Y_M~Z_M$

Output Format

Print the count.

Samples

Sample Input1

Sample Output1

1

4

Valid permutations: $(1,2,3)$, $(2,3,1)$, $(3,1,2)$, $(3,2,1)$.

Sample Input2

Sample Output2

1

90

Sample Input3

1

18 0

Sample Output3

1

6402373705728000

Analysis

Use bitmask DP. Let dp[mask] represent the number of valid ways to select the subset mask. For each bit added, check constraints. Time complexity: $\mathcal O(2^N \cdot (N + M))$.

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


#include <cstdio>
#include <vector>
#define maxn 20
using namespace std;

using LL = long long;

vector<pair<int, int>> lim[maxn];
LL dp[1 << maxn];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    while(m--)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        if(z < y) lim[x].emplace_back(y, z);
    }
    int mx = 1 << n;
    dp[0] = 1LL;
    for(int st=0; st<mx; st++)
    {
        vector<int> s;
        for(int i=0; i<n; i++)
            if(st >> i & 1)
                s.push_back(i);
        int cnt = __builtin_popcount(st);
        bool ok = true;
        for(auto [y, z]: lim[cnt])
        {
            int tot = 0;
            for(auto x: s)
                if(x < y && ++tot > z)
                {
                    ok = false;
                    break;
                }
            if(!ok) break;
        }
        if(ok) for(int x: s) dp[st] += dp[st ^ (1 << x)];
    }
    printf("%lld\n", dp[mx - 1]);
    return 0;
}