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 - Chinchirorin

Problem Statement

Given three integers $a,b,c$, if two of them are equal, output the third one; otherwise, output $0$.

$1\le a,b,c\le 6$

Input Format

$a~b~c$

Output Format

Output the third value if two of $a,b,c$ are equal; otherwise, output $0$.

Samples

$a$	$b$	$c$	Output
$2$	$5$	$2$	$5$
$4$	$5$	$6$	$0$
$1$	$1$	$1$	$1$

Analysis

Problem A remains straightforward. Directly check the three possible equality cases.

Code

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


#include <cstdio>
using namespace std;

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

B - AtCoder Condominium

Problem Statement

Given $N$ and $K$, compute $\sum\limits_{i=1}^N\sum\limits_{j=1}^K \overline{i0j}$.

$1\le N,K\le 9$

Input Format

$N~K$

Output Format

Output $\sum\limits_{i=1}^N\sum\limits_{j=1}^K \overline{i0j}$.

Samples

$N$	$K$	Output
$1$	$2$	$203$
$3$	$3$	$1818$

Analysis

Brute-force works, but here’s an $\mathcal O(1)$ approach:
Since $\overline{i0j}=100i+j$ and $1+2+\dots+N=\frac{N(N+1)}2$, we derive:

$\sum\limits_{i=1}^N\sum\limits_{j=1}^K \overline{i0j}=\frac{100N(N+1)K+K(K+1)N}2$

Code

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


#include <cstdio>
using namespace std;

inline int sum(int x) { return x * (x + 1) >> 1; }

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    printf("%d\n", sum(n) * k * 100 + sum(k) * n);
    return 0;
}

C - Friends and Travel costs

Problem Statement

There are $10^{100}+1$ villages numbered $0,1,\dots,10^{100}$. Moving between adjacent villages costs $1$ yen.
Taro starts at village $0$ with $K$ yen and wants to reach the highest possible village.
He has $N$ friends. The $i$-th friend gives $B_i$ yen when Taro reaches village $A_i$.
Find the highest village Taro can reach.

$1\le N\le 2\times10^5$
$1\le K\le 10^9$
$1\le A_i\le 10^{18}$
$1\le B_i\le 10^9$

Input Format

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

Output

Output the highest village number Taro can reach.

Samples

Sample Input 1

Sample Output 1

1

4

Sample Input 2

1
2
3
4
5
6


5 1000000000
1 1000000000
2 1000000000
3 1000000000
4 1000000000
5 1000000000

Sample Output 2

1

6000000000

Use 64-bit integers.

Sample Input 3

Sample Output 3

1

10

A village may contain multiple friends.

Analysis

Sort friends by $A_i$. Process intervals between friends, checking if Taro can reach each $A_i$ with remaining funds.

Code

Note: Sorting uses a priority queue.

 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


#include <cstdio>
#include <queue>
#define maxn 200005
#define INF 18446744073709551615ULL
using namespace std;

using ULL = unsigned long long;
using pll = pair<ULL, ULL>;

int main()
{
    int n;
    ULL k;
    scanf("%d%llu", &n, &k);
    priority_queue<pll, vector<pll>, greater<pll> > q;
    for(int i=0; i<n; i++)
    {
        ULL a, b;
        scanf("%llu%llu", &a, &b);
        q.emplace(a, b);
    }
    ULL lastv = 0ULL;
    q.emplace(INF, 0ULL);
    while(!q.empty())
    {
        auto [a, b] = q.top(); q.pop();
        ULL cost = a - lastv;
        if(k < cost)
        {
            printf("%llu\n", lastv + k);
            return 0;
        }
        k -= cost;
        lastv = a, k += b;
    }
    return 0;
}

D - Pond

Problem Statement

Given an $N\times N$ matrix $A$, find the minimum median among all $K\times K$ submatrices. The median is the $(\left\lfloor\frac{K^2}2\right\rfloor+1)$-th largest value.

$1\le K\le N\le 800$
$1\le A_{i,j}\le 10^9$

Example illustration:

Input Format

$N~K$
$A_{1,1}~A_{1,2}~\dots~A_{1,N}$
$\vdots$
$A_{N,1}~A_{N,2}~\dots~A_{N,N}$

Output Format

Output the answer.

Samples

Sample Input 1

Sample Output 1

1

4

Sample Input 2

Sample Output 2

1

5

Analysis

Binary search the answer. For each candidate value, use matrix prefix sums to count elements exceeding it in each submatrix. Time complexity $\mathcal O(n^2\log\max\{A\})$.

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>
#define maxn 805
#define INF 2147483647
using namespace std;

int a[maxn][maxn], dp[maxn][maxn], n, k, target;

inline int count(int x1, int y1, int x2, int y2)
{
    return dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
}

inline bool check(int x)
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + (a[i][j] > x);
    for(int x2=k; x2<=n; x2++)
        for(int y2=k; y2<=n; y2++)
        {
            int x1 = x2 - k + 1, y1 = y2 - k + 1;
            if(count(x1, y1, x2, y2) < target)
                return true;
        }
    return false;
}

int main()
{
    scanf("%d%d", &n, &k);
    target = (k * k >> 1) + 1;
    int l = INF, r = 0, ans = 0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            scanf("%d", a[i] + j);
            if(a[i][j] > r) r = a[i][j];
            if(a[i][j] < l) l = a[i][j];
        }
    while(l <= r)
    {
        int mid = l + r >> 1;
        if(check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    printf("%d\n", ans);
    return 0;
}

E - White Pawn

Problem Statement

On a $(2N+1)\times(2N+1)$ chessboard, a white pawn starts at $(0,N)$. $M$ black squares exist at $(X_i,Y_i)$. The pawn moves:

Down to white $(i+1,j)$,
Diagonally down-left to black $(i+1,j-1)$,
Diagonally down-right to black $(i+1,j+1)$.

Find how many columns in the last row are reachable.

$1\le N\le 10^9$
$0\le M\le 2\times 10^5$

Input Format

$N~M$
$X_1~Y_1$
$\vdots$
$X_M~Y_M$

Output Format

Output the count.

Samples

Sample Input 1

Sample Output 1

1

3

Sample Input 2

Sample Output 2

1

0

Analysis

Process black squares row-wise. Maintain reachable columns using a set. For each black row, update reachable positions based on adjacent cells.

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


#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
#pragma GCC optimize("Ofast")
using namespace std;

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    vector<pair<int, int> > black;
    black.reserve(m);
    while(m--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        black.emplace_back(x, y);
    }
    m = black.size();
    sort(black.begin(), black.end());
    set<int> cols;
    cols.insert(n);
    for(int l=0, r=0; l<m; l=r)
    {
        while(r < m && black[r].first == black[l].first) r ++;
        vector<int> rem, add;
        for(int i=l; i<r; i++)
        {
            int y = black[i].second;
            bool ok = cols.count(y - 1) || cols.count(y + 1);
            if(cols.count(y))
            {
                if(!ok)
                    rem.push_back(y);
            }
            else if(ok)
                add.push_back(y);
        }
        for(int y: rem) cols.erase(y);
        for(int y: add) cols.insert(y);
    }
    printf("%llu\n", cols.size());
    return 0;
}