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 - Good morning

Problem Summary

On the same day, Takahashi wakes up at $A$ hours $B$ minutes, and Aoki wakes up at $C$ hours $D$ minutes 1 second. Who wakes up earlier?

$0\le A,C < 24$
$0\le B,D < 60$

Input Format

$A~B~C~D$

Output Format

Output the name of the earlier riser (Takahashi or Aoki).

Samples

Analysis

The approach is straightforward: directly check whether $(A,B)\le(C,D)$ holds.

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);
    puts((a == c? b <= d: a < c)? "Takahashi": "Aoki");
    return 0;
}

B - Mex

Problem Summary

Given an integer sequence $A=(A_1,\dots,A_N)$, find the smallest natural number not present in $A$.

$1\le N\le 2000$
$0\le A_i\le 2000$

Input Format

$N$
$A_1~\dots~A_N$

Output Format

Output the smallest natural number not in $A$.

Samples

Samples omitted; please visit AtCoder.

Analysis

Since $0\le A_i\le 2000$, we can use an array to track occurrences of numbers in $[0,2001]$.
There are multiple approaches for this problem; here we present the fastest algorithm with $\mathcal O(N)$ time complexity.

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;

bool used[2005];

int main()
{
    int n;
    scanf("%d", &n);
    while(n--)
    {
        int a;
        scanf("%d", &a);
        used[a] = true;
    }
    int i = -1;
    while(used[++i]);
    printf("%d\n", i);
    return 0;
}

C - Choose Elements

Problem Summary

Given two integer sequences $A=(A_1,\dots,A_N)$ and $B=(B_1,\dots,B_N)$, determine if there exists a sequence $X=(X_1,\dots,X_N)$ satisfying:

• $X_i=A_i$ or $X_i=B_i$
• $|X_i-X_{i+1}|\le K$ for all $1\le i < N$

$1\le N\le 2\times 10^5$
$1\le K\le 10^9$
$1\le A_i,B_i\le 10^9$

Input Format

$N~K$
$A_1~\dots~A_N$
$B_1~\dots~B_N$

Output Format

Output Yes if such $X$ exists; otherwise, output No.

Samples

Samples omitted; please visit AtCoder.

Analysis

This problem can be solved using dynamic programming.
Let $f(i)$ denote whether $X_i$ can be $A_i$, and $g(i)$ denote whether $X_i$ can be $B_i$.
State transitions are straightforward; see code for details.

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

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

int a[maxn], b[maxn];
bool f[maxn], g[maxn];

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i=0; i<n; i++)
        scanf("%d", a + i);
    for(int i=0; i<n; i++)
        scanf("%d", b + i);
    f[0] = g[0] = true;
#define set(x, y, z) x |= y - z <= k && z - y <= k
    for(int i=1; i<n; i++)
    {
        if(f[i - 1])
            set(f[i], a[i - 1], a[i]),
            set(g[i], a[i - 1], b[i]);
        if(g[i - 1])
            set(f[i], b[i - 1], a[i]),
            set(g[i], b[i - 1], b[i]);
    }
    puts(f[n - 1] || g[n - 1]? "Yes": "No");
    return 0;
}

Note: There’s a peculiar alternative solution that checks if at least one of the four adjacent connections exists, such as in #30453703. If anyone can prove its correctness, please comment below!

D - Polynomial division

Problem Summary

where $A$ and $C$ coefficients are known and $A(x)\times B(x)=C(x)$, find coefficients $B_0,\dots,B_M$.

$1\le N,M < 100$
$|A_i|\le 100$
$|C_i|\le 10^6$
$A_N\ne0$, $C_{N+M}\ne0$
A valid $B$ is guaranteed.

Input Format

$N~M$
$A_0~\dots~A_N$
$C_0~\dots~C_{N+M}$

Output Format

Output $B_0,\dots~B_M$ separated by spaces.

Samples

Samples omitted; please visit AtCoder.

Analysis

Simulate the polynomial long division process by tracking coefficients.
Reference: Polynomial long division

Code

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

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

int a[maxn], b[maxn], c[maxn << 1];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i=0; i<=n; i++) scanf("%d", a + i);
    for(int i=0; i<=n+m; i++) scanf("%d", c + i);
    for(int i=m; i>=0; i--) // NOTE: must process in reverse order!
    {
        b[i] = c[n + i] / a[n];
        for(int j=0; j<=n; j++)
            c[i + j] -= a[j] * b[i];
    }
    for(int i=0; i<=m; i++)
        printf("%d ", b[i]);
    return 0;
}

E - Wrapping Chocolate

Problem Summary

We have $N$ chocolates and $M$ boxes. The $i$-th chocolate has dimensions $A_i\times B_i$, and the $j$-th box has dimensions $C_j\times D_j$. Determine if all chocolates can be packed into boxes such that:

• Each box contains exactly one chocolate.
• For chocolate $i$ in box $j$, $A_i\le C_j$ and $B_i\le D_j$ must hold.

$1\le N\le M\le 2\times10^5$
$1\le A_i,B_i,C_i,D_i\le 10^9$

Input Format

$N~M$
$A_1~\dots~A_N$
$B_1~\dots~B_N$
$C_1~\dots~C_M$
$D_1~\dots~D_M$

Output Format

Output Yes if possible; otherwise, No.

Analysis

Greedy algorithm steps:

1. Sort all items (chocolates and boxes) in descending order of length. When lengths are equal, boxes come first.
2. Use a multiset to track available box heights. For each chocolate, remove the smallest box height ≥ its height.
   Time complexity: $\mathcal O((N+M)\log(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
47
48

#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;

struct Item {
    int w, h;
    bool type;
    inline bool operator <(const Item& i2) const {
        return w == i2.w? type > i2.type: w > i2.w;
        // Note: The sort must have strict ordering. Initially, writing type==1 here caused RE, see:
        // https://atcoder.jp/contests/abc245/submissions/30526563
    }
} v[400005];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    // Chocolate
    for(int i=0; i<n; i++) scanf("%d", &v[i].w);
    for(int i=0; i<n; i++) scanf("%d", &v[i].h);
    // Box
    m += n;
    for(int i=n; i<m; i++) scanf("%d", &v[i].w);
    for(int i=n; i<m; i++) scanf("%d", &v[i].h);
    for(int i=n; i<m; i++) v[i].type = 1;
    // Algorithm
    sort(v, v + m);
    multiset<int> s;
    for(int i=0; i<m; i++)
    {
        const Item& it = v[i];
        if(it.type) s.insert(it.h); // Box
        else
        {
            auto itr = s.lower_bound(it.h);
            if(itr == s.end())
            {
                puts("No");
                return 0;
            }
            s.erase(itr);
        }
    }
    puts("Yes");
    return 0;
}