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 - Difference Max

Problem Statement

Given four integers $a$, $b$, $c$, and $d$.
Choose integers $x$ and $y$ such that $a \le x \le b$ and $c \le y \le d$. Find the maximum possible value of $x - y$.

Constraints:
$-100 \le a \le b \le 100$
$-100 \le c \le d \le 100$

Input Format

1
2


a b
c d

Output Format

Print the maximum value of $x - y$.

Sample Cases

$a$	$b$	$c$	$d$	Output
0	10	0	10	10
-100	-100	100	100	200
-100	100	-100	100	200

Analysis

To maximize $x - y$, $x$ should be as large as possible ($x = b$) and $y$ as small as possible ($y = c$). Thus, directly output $b - c$.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


#include <cstdio>
using namespace std;

int main()
{
    int a, b, c, d;
    scanf("%d%d%d%d", &a, &b, &c, &d);
    printf("%d\n", b - c);
    return 0;
}

B - Round Down

Problem Statement

Given a number $X$, compute $\lfloor X \rfloor$.

Constraints:
$0 \le X \le 10^{100}$

Input Format

1

X

Output Format

Print $\lfloor X \rfloor$.

Sample Cases

X	Output
5.90	5
0	0
84939825309432908832902189.9092309409809091329	84939825309432908832902189

Analysis

Truncate all characters starting from the decimal point. For example: $5\sout{.90}$.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


#include <cstdio>
using namespace std;

int main()
{
    char c;
    while((c = getchar()) != '\n')
    {
        if(c == '.') return 0;
        putchar(c);
    }
    return 0;
}

C - Doubled

Problem Statement

Count how many integers between 1 and $N$ (inclusive) are formed by concatenating two identical positive integers.

Constraints:
$1 \le N < 10^{12}$

Input Format

1

N

Output Format

Print the count.

Sample Cases

N	Output
33	3
1333	13
10000000	999

Analysis

The problem reduces to finding the largest $X$ such that concatenating $X$ twice does not exceed $N$. Use binary search with the right boundary set to $\sqrt{N}$ to avoid overflow.

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


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

typedef long long LL;

inline bool check(const LL& x, const LL& n)
{
    LL p = 1LL;
    while(p <= x) p *= 10LL;
    return x * p + x <= n;
}

int main()
{
    LL n;
    scanf("%lld", &n);
    LL l = 0LL, r = sqrt(n);
    while(l < r)
    {
        LL mid = l + r + 1LL >> 1LL;
        if(check(mid, n)) l = mid;
        else r = mid - 1;
    }
    printf("%lld\n", l);
    return 0;
}

D - Hanjo

Problem Statement

Tile an $H \times W$ grid using $A$ $2 \times 1$ dominoes and $B$ $1 \times 1$ squares. Count the number of ways to fully cover the grid.

Constraints:
$1 \le H, W, HW \le 16$
$0 \le A, B$
$2A + B = HW$

Input Format

1

H W A B

Output Format

Print the number of valid tilings.

Sample Cases

H	W	A	B	Output
2	2	1	2	4
3	3	4	1	18
4	4	8	0	36

Analysis

Use backtracking to explore all placements. Track the current position and remaining tiles, placing dominoes horizontally or vertically while avoiding overlaps.

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


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

bool mat[maxn][maxn];
int h, w, a, b, ans;

inline bool valid(int x, int y)
{
    return !mat[x][y] && x >= 0 && x < h && y >= 0 && y < w;
}

void dfs(int i, int j, int usedA, int usedB)
{
    if((usedA << 1) + usedB == h * w)
    {
        ans ++;
        return;
    }
    if(i == h) return;
    int ni, nj;
    if(j == w - 1) ni = i + 1, nj = 0;
    else ni = i, nj = j + 1;
    if(mat[i][j])
    {
        dfs(ni, nj, usedA, usedB);
        return;
    }
    mat[i][j] = true;
    // Rectangle (A)
    if(usedA < a)
    {
        if(valid(i, j + 1))
        {
            mat[i][j + 1] = true;
            dfs(ni, nj, usedA + 1, usedB);
            mat[i][j + 1] = false;
        }
        if(valid(i + 1, j))
        {
            mat[i + 1][j] = true;
            dfs(ni, nj, usedA + 1, usedB);
            mat[i + 1][j] = false;
        }
    }
    // Square (B)
    if(usedB < b) dfs(ni, nj, usedA, usedB + 1);
    mat[i][j] = false;
}

int main()
{
    scanf("%d%d%d%d", &h, &w, &a, &b);
    dfs(0, 0, 0, 0);
    printf("%d\n", ans);
    return 0;
}

E - Filters

Problem Statement

Given sequences $A$, $T$, and $X$, compute the composite function $F(x) = f_N(\dots f_2(f_1(x)) \dots)$ for each query $x_i$, where:

$f_i(x) = x + a_i$ if $t_i = 1$
$f_i(x) = \max(x, a_i)$ if $t_i = 2$
$f_i(x) = \min(x, a_i)$ if $t_i = 3$

Constraints:
$1 \le N, Q \le 2 \times 10^5$
$|a_i|, |x_i| \le 10^9$

Input Format

1
2
3
4
5
6
7


N
a_1 t_1
a_2 t_2
...
a_N t_N
Q
x_1 x_2 ... x_Q

Output Format

Print $Q$ lines, each containing $F(x_i)$.

Sample Input

1
2
3
4
5
6


3
-10 2
10 1
10 3
5
-15 -10 -5 0 5

Sample Output

Analysis

The composite function can be represented as $F(x) = \min(c, \max(b, x + a))$. Track three parameters $a$, $b$, and $c$ through the function chain:

Additive shifts accumulate in $a$.
$\max$ operations set lower bounds in $b$.
$\min$ operations set upper bounds in $c$.

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 <algorithm>
#include <climits>
using namespace std;

typedef long long LL;
const LL INF = LLONG_MAX >> 1LL;

int main()
{
    LL l = -INF, r = INF, add = 0LL;
    int n, q;
    scanf("%d", &n);
    while(n--)
    {
        LL a, t;
        scanf("%lld%lld", &a, &t);
        if(t == 1) l += a, r += a, add += a;
        else if(t == 2) l = max(l, a), r = max(r, a);
        else l = min(l, a), r = min(r, a);
    }
    scanf("%d", &q);
    while(q--)
    {
        LL x;
        scanf("%lld", &x);
        printf("%lld\n", clamp(x + add, l, r));
    }
    return 0;
}