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 - Tiny Arithmetic Sequence

Problem Statement

Given a sequence $A=(A_1,A_2,A_3)$, can it be rearranged such that $A_3-A_2=A_2-A_1$?

$1\le A_i\le 100$

Input Format

$A_1~A_2~A_3$

Output Format

Print Yes if possible; otherwise, print No.

Sample Cases

$A$	Output
$(5,1,3)$	`Yes`
$(1,4,3)$	`No`
$(5,5,5)$	`Yes`

Analysis

It’s easy to observe that if $A_3-A_2=A_2-A_1$ holds, then $A_1\le A_2\le A_3$ or $A_3\le A_2\le A_1$ must be true. Thus, we can sort $A$ in ascending order and check if the condition holds.

Code

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


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

int main()
{
    int a[3];
    scanf("%d%d%d", a, a + 1, a + 2);
    sort(a, a + 3);
    puts(a[2] - a[1] == a[1] - a[0]? "Yes": "No");
    return 0;
}

B - Do you know the second highest mountain?

Problem Statement

There are $N$ mountains. The $i$-th mountain has a name $S_i$ and height $T_i$. Output the name of the second highest mountain.

$2\le N\le 1000$
$1\le |S_i|\le 15$
$1\le T_i\le 10^5$
$S_i\ne S_j~(i\ne j)$
$T_i\ne T_j~(i\ne j)$
$S_i$ consists of uppercase/lowercase letters and digits.

Input Format

$N$
$S_1~T_1$
$S_2~T_2$
$\vdots$
$S_N~T_N$

Output Format

Print the name of the second highest mountain.

Sample Cases

Sample Input 1

1
2
3
4


3
Everest 8849
K2 8611
Kangchenjunga 8586

Sample Output 1

1

K2

The second highest mountain is K2.

Sample Input 2

1
2
3
4
5


4
Kita 3193
Aino 3189
Fuji 3776
Okuhotaka 3190

Sample Output 2

1

Kita

The second highest mountain is Kita.

Sample Input 3

1
2
3
4
5


4
QCFium 2846
chokudai 2992
kyoprofriends 2432
penguinman 2390

Sample Output 3

1

QCFium

The second highest mountain is QCFium.

Analysis

This problem requires finding the $S_i$ corresponding to the second largest element in $T$. We can use a priority queue to maintain the top two elements efficiently.

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


#include <iostream>
#include <queue>
#include <string>
using namespace std;

using pis = pair<int, string>;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    int n;
    cin >> n;
    priority_queue<pis, vector<pis>, greater<pis> > q;
    while(n--)
    {
        string s;
        int h;
        cin >> s >> h;
        q.emplace(h, s);
        if(q.size() > 2) q.pop();
    }
    cout << q.top().second << endl;
    return 0;
}

C - Secret Number

Problem Statement

A 4-digit PIN consists of digits 0-9 (may start with 0). A string $S_0S_1\dots S_9$ determines the presence of each digit:

If $S_i=$ o, the PIN must contain digit $i$;
If $S_i=$ x, the PIN must not contain digit $i$;
If $S_i=$ ?, the PIN may or may not contain digit $i$.

Count the number of valid PINs.

$S$ is a 10-character string of o, x, or ?.

Input Format

$S$

Output Format

Print the total count as an integer.

Sample Cases

$S$	Answer
`ooo???xxxx`	$108$
`o?oo?oxoxo`	$0$
`xxxxx?xxxo`	$15$
Edge Case: $S=$ `??????????`, Answer: $10000$

Analysis

Since there are only 10000 possible PINs, we can brute-force all combinations. For each candidate PIN, check compliance with $S$ in $\mathcal O(|S|)$ time.

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


#include <cstdio>
using namespace std;

char s[15];

inline bool valid(int a, int b, int c, int d)
{
    bool used[10] = {false};
    used[a] = used[b] = used[c] = used[d] = true;
    for(int i=0; i<10; i++)
        if(s[i] == 'o')
        {
            if(!used[i])
                return false;
        }
        else if(s[i] == 'x' && used[i])
            return false;
    return true;
}

int main()
{
    scanf("%s", s);
    int ans = 0;
    for(int a=0; a<10; a++)
        for(int b=0; b<10; b++)
            for(int c=0; c<10; c++)
                for(int d=0; d<10; d++)
                    ans += valid(a, b, c, d);
    printf("%d\n", ans);
    return 0;
}

D - Game in Momotetsu World

Problem Statement

A $H\times W$ grid has cells colored blue (+) or red (-). A token starts at $(1,1)$. Takahashi and Aoki take turns moving it right or down. The current player gains 1 point for blue cells or loses 1 point for red cells. The game ends at $(H,W)$. Determine the winner if both play optimally.

$1\le H,W\le 2000$

Input Format

$H~W$
$A_{1,1}A_{1,2}\dots A_{1,W}$
$A_{2,1}A_{2,2}\dots A_{2,W}$
$\vdots$
$A_{H,1}A_{H,2}\dots A_{H,W}$

Output Format

Print Takahashi, Aoki, or Draw.

Analysis

Define $d$ as the score difference (Takahashi − Aoki). Using dynamic programming:

For $(i+j)$ even (Aoki’s turn): $dp(i,j) = \min(dp(i+1,j) - add(i+1,j), dp(i,j+1) - add(i,j+1))$
For $(i+j)$ odd (Takahashi’s turn): $dp(i,j) = \max(dp(i+1,j) + add(i+1,j), dp(i,j+1) + add(i,j+1))$

$add(i,j)$ is the score change upon entering $(i,j)$. The result depends on $dp(0,0)$.

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


#include <cstdio>
#include <algorithm>
#define maxn 2005
using namespace std;

int dp[maxn], add[maxn][maxn];

int main()
{
    int h, w;
    scanf("%d%d", &h, &w);
    for(int i=0; i<h; i++)
    {
        char tmp[maxn];
        scanf("%s", tmp);
        for(int j=0; j<w; j++)
            add[i][j] = tmp[j] == '+'? 1: -1;
    }
    dp[w - 1] = 0;
    for(int j=w-2; j>=0; j--)
        dp[j] = j + h & 1? dp[j + 1] + add[h - 1][j + 1]: dp[j + 1] - add[h - 1][j + 1];
    for(int i=h-2; i>=0; i--)
    {
        dp[w - 1] = i + w & 1? dp[w - 1] + add[i + 1][w - 1]: dp[w - 1] - add[i + 1][w - 1];
        for(int j=w-2; j>=0; j--)
            if(i + j & 1)
                dp[j] = min(dp[j] - add[i + 1][j], dp[j + 1] - add[i][j + 1]);
            else dp[j] = max(dp[j] + add[i + 1][j], dp[j + 1] + add[i][j + 1]);
    }
    if(dp[0] > 0) puts("Takahashi");
    else if(dp[0] < 0) puts("Aoki");
    else puts("Draw");
    return 0;
}

E - Xor Distances

Problem Statement

Given a tree with $N$ nodes and edge weights, compute $\sum_{1\le i

$1\le N\le 2\times10^5$
$0\le w_i < 2^{60}$

Input Format

$N$
$u_1~v_1~w_1$
$\vdots$
$u_{N-1}~v_{N-1}~w_{N-1}$

Output Format

Print the sum modulo $10^9+7$.

Analysis

Leverage XOR properties: $\mathrm{dist}(x,y) = \mathrm{dist}(r,x) \oplus \mathrm{dist}(r,y)$ for any root $r$. Compute XOR from root to all nodes. For each bit position, count the number of nodes with that bit set. The contribution to the total sum is $(count) \times (N-count) \times 2^{bit}$.

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 <queue>
#pragma GCC optimize("Ofast")
#define maxn 200005
#define MOD 1000000007LL
using namespace std;

using LL = long long;
vector<pair<int, LL>> G[maxn];
LL d[maxn];

int main()
{
    int n;
    scanf("%d", &n);
    for(int i=1; i<n; i++)
    {
        int u, v;
        LL w;
        scanf("%d%d%lld", &u, &v, &w);
        G[--u].emplace_back(--v, w);
        G[v].emplace_back(u, w);
    }
    queue<int> q;
    q.push(0);
    for(int i=1; i<n; i++) d[i] = -1;
    while(!q.empty())
    {
        int v = q.front(); q.pop();
        for(auto [u, w]: G[v])
            if(d[u] == -1)
                q.push(u), d[u] = d[v] ^ w;
    }
    LL ans = 0LL;
    for(int i=0; i<60; i++)
    {
        int cnt = 0;
        for(int j=0; j<n; j++)
            if(d[j] >> i & 1LL)
                cnt ++;
        if((ans += (1LL << i) % MOD * cnt % MOD * (n - cnt) % MOD) > MOD)
            ans -= MOD;
    }
    printf("%lld\n", ans);
    return 0;
}