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 - Large Digits

Problem Statement

Given two three-digit integers $A$ and $B$, find the maximum of their digit sums.
Digit Sum: For example, the digit sum of $123$ is $1+2+3=6$.

Constraints:
$100\le A,B\le 999$

Input Format

$A~~B$

Output Format

Output the maximum digit sum of $A$ and $B$.

Sample

Analysis

Directly implement as per the problem description.

Code

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

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

int main(int argc, char** argv)
{
    char a[10], b[10];
    scanf("%s%s", a, b);
    int as = 0, bs = 0;
    for(int i=0; a[i]; i++)
        as += a[i] - '0';
    for(int i=0; b[i]; i++)
        bs += b[i] - '0';
    printf("%d\n", max(as, bs));
    return 0;
}

B - Gentle Pairs

Problem Statement

There are $N$ points with coordinates $(x_i,y_i)$, where all $x$-coordinates are distinct.
How many pairs of points satisfy $-1 \le \text{slope} \le 1$?

Constraints:
$1\le N\le 10^3$
$|x_i|,|y_i|\le 10^3$
$x_i \ne x_j$ ($i < j$)

Input Format

$N$
$x_1~y_1$
$\vdots$
$x_n~y_n$

Output Format

Output the answer.

Sample

Sample Input1

1
2
3
4

3
0 0
1 2
2 1

Sample Output1

1

2

There are three points: $(0,0)$, $(1,2)$, and $(2,1)$.

• From $(0,0)$ to $(1,2)$, slope is $2$;
• From $(0,0)$ to $(2,1)$, slope is $\frac{1}{2}$;
• From $(1,2)$ to $(2,1)$, slope is $-1$.

There are 2 valid pairs.

Sample Input2

1
2

1
-691 273

Sample Output2

1

0

Only one point exists. Output $0$.

Sample Input3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

10
-31 -35
8 -36
22 64
5 73
-14 8
18 -58
-41 -85
1 -88
-21 -85
-11 82

Sample Output3

1

11

Analysis

We use integer operations to avoid floating-point errors.

Code

Enumerate all pairs.

 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

#include <cstdio>
#include <cmath>
#define maxn 1005
using namespace std;
 
int x[maxn], y[maxn];
 
inline bool slope_check(int x1, int y1, int x2, int y2)
{
    int dx = abs(x1 - x2), dy = abs(y1 - y2);
    return dy <= dx;
}
 
int main(int argc, char** argv)
{
    int n, cnt = 0;
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        scanf("%d%d", x + i, y + i);
    for(int i=0; i<n-1; i++)
        for(int j=i+1; j<n; j++)
            if(slope_check(x[i], y[i], x[j], y[j]))
                cnt ++;
    printf("%d\n", cnt);
    return 0;
}

C - 1-SAT

Problem Statement

Given $N$ strings $S_1,S_2,...,S_N$. Each string consists of lowercase letters and may have at most one ! at the beginning.
Find any string $S$ such that both $S$ and !+$S$ exist in the list. If none exist, output satisfiable.

Constraints:
$1\le N\le 10^5$
$1\le |S_i|\le 10$

Input Format

$N$
$S_1$
$\vdots$
$S_N$

Output Format

If a valid string exists, output any such string.
Otherwise, output satisfiable.

Sample

Sample Input1

1
2
3
4
5
6
7

6
a
!a
b
!c
d
!d

Sample Output1

1

a

$S_1$ is a and $S_2$ is !a, so $S_1$ is valid.
$S_5$ is d and $S_6$ is !d, so d is also a valid output.

Sample Input2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

10
red
red
red
!orange
yellow
!blue
cyan
!green
brown
!gray

Sample Output2

1

satisfiable

No valid string exists.

Analysis

A brute-force $\mathcal O(N^2)$ approach is infeasible.
Optimization:

• Store strings starting with ! (after removing !) in a set.
• Check other strings against this set in $\mathcal O(\log N)$ per query.
  Overall complexity: $\mathcal O(N\log N)$.

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 <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;

vector<string> v;
set<string> s;

int main(int argc, char** argv)
{
    ios::sync_with_stdio(false); cin.tie(0);
    int n;
    cin >> n;
    while(n--)
    {
        string x;
        cin >> x;
        if(x[0] == '!')
            s.insert(x.substr(1));
        else v.push_back(x);
    }
    for(int i=0; i<v.size(); i++)
        if(s.find(v[i]) != s.end())
        {
            cout << v[i] << endl;
            return 0;
        }
    cout << "satisfiable\n";
    return 0;
}

D - Choose Me

Problem Statement

Refer to the original problem page for details.
Constraints:
$1\le N\le 10^5$
$1\le A_i,B_i\le 10^9$

Input Format

$N$
$A_1~B_1$
$\vdots$
$A_N~B_N$

Output Format

Output the minimum number of cities to visit.

Sample

Sample Input1

1
2
3
4
5

4
2 1
2 2
5 1
1 3

Sample Output1

1

1

After visiting the third city, Aoki gets 5 votes and Takahashi gets 6.

Sample Input2

1
2
3
4
5
6

5
2 1
2 1
2 1
2 1
2 1

Sample Output2

1

3

Visiting any three cities gives Aoki 4 votes and Takahashi 9.

Sample Input3

1
2

1
273 691

Sample Output3

1

1

Analysis

Our goal is to minimize the vote difference. Initially, the difference is the sum of all $A_i$.
Each city $i$ reduces the difference by $2A_i + B_i$. We greedily select cities with the largest reduction first using a priority queue.

Code

Note: Must use long long to avoid overflow.

 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

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

typedef long long LL;

priority_queue<LL> q;

int main(int argc, char** argv)
{
    int n;
    scanf("%d", &n);
    LL diff = 0;
    while(n--)
    {
        LL ao, ta;
        scanf("%lld%lld", &ao, &ta);
        diff += ao;
        q.push(ao + ao + ta);
    }
    int ans = 0;
    while(!q.empty())
    {
        ans ++;
        if((diff -= q.top()) < 0)
        {
            printf("%d\n", ans);
            return 0;
        }
        q.pop();
    }
    return 0;
}