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

Problem Statement

Two boys want to divide $N$ candies. How many ways are there to distribute them (each boy must get at least one candy)?

$1\le N\le 15$

Input Format

$N$

Output Format

Print the answer as an integer.

Sample

$N$	Output
$2$	$1$
$1$	$0$
$3$	$2$

Analysis

The problem reduces to splitting $N$ into two positive integers $A$ and $B$ (where $A+B$ and $B+A$ count as distinct). The possible pairs are:

$A$	$B$
$1$	$N-1$
$2$	$N-2$
$\dots$	$\dots$
$N-1$	$1$
This table has $N-1$ entries, so we directly output $N-1$.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


#include <cstdio>
using namespace std;

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

B - Palindrome with leading zeros

Problem Statement

Given an integer $N$, can we prepend any number (including zero) of 0s to its decimal representation to make it a palindrome?

$0\le N\le 10^9$

Input Format

$N$

Output Format

Print Yes or No.

Sample

$N$	Output
$1210$	`Yes`
$777$	`Yes`
$123456789$	`No`

Analysis

If prepending zeros can make $N$ a palindrome, then trimming all trailing zeros from $N$ must also yield a palindrome. Thus, we trim trailing zeros and check if the resulting string is a palindrome.

Code

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


#include <cstdio>
using namespace std;

char s[10];

int main()
{
    char c;
    int len = 0;
    while((c = getchar()) != '\n')
        s[len++] = c;
    while(len > 0 && s[--len] == '0');
    for(int i=0; i<=len; i++)
        if(s[i] != s[len - i])
        {
            puts("No");
            return 0;
        }
    puts("Yes");
    return 0;
}

C - Compass Walking

Problem Statement

In a 2D plane, a person moves exactly $R$ units per step. What is the minimum steps needed to go from $(0,0)$ to $(X,Y)$?
Note: The distance between $(x_1, y_1)$ and $(x_2,y_2)$ is $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$.

$1\le R\le 10^5$
$0\le X,Y\le 10^5$
$(X,Y)\ne(0,0)$

Input Format

$R~X~Y$

Output Format

Print the minimum number of steps.

Sample

$R$	$X$	$Y$	Output
$5$	$15$	$0$	$3$
$5$	$11$	$0$	$3$
$3$	$4$	$4$	$2$

Analysis

Let $d=\sqrt{X^2+Y^2}$ (Euclidean distance). The solution depends on:

If $d = R$: 1 step.
If $d < R$: 2 steps (two orthogonal steps form a hypotenuse).
If $d > R$: $\lceil\frac{d}{R}\rceil$ steps.

Code

Precision issues were tricky, but using long double worked.

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


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

int main()
{
    int r, x, y;
    scanf("%d%d%d", &r, &x, &y);
    long double dist = hypotl(x, y);
    if(dist == r) puts("1");
    else if(dist < r) puts("2");
    else printf("%d\n", int(ceill(dist / r)));
    return 0;
}

D - Send More Money

Problem Statement

Given three lowercase strings $S_1,S_2,S_3$, assign each unique letter a distinct digit (0-9) such that $N_1 + N_2 = N_3$ when converted to numbers (no leading zeros). Output any solution or UNSOLVABLE.

$1\le |S_1|,|S_2|,|S_3|\le 10$
Time Limit: 5 sec

Input Format

$S_1$
$S_2$
$S_3$

Output Format

Print $N_1$, $N_2$, $N_3$ on three lines, or UNSOLVABLE.

Sample

$S_1$	$S_2$	$S_3$	Output
`a`	`b`	`c`	`1 2 3`
`x`	`x`	`y`	`1 1 2`
`p`	`q`	`p`	`UNSOLVABLE`

Analysis

If the total unique letters exceed 10, output UNSOLVABLE. Otherwise, brute-force all permutations of digit assignments (up to $10!$ possibilities) and validate.

Code

Using permutations for enumeration:

 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
58
59
60
61
62
63
64
65
66


#include <cstdio>
#include <set>
#include <algorithm>
#define maxl 15
using namespace std;

using LL = long long;

char s1[maxl], s2[maxl], s3[maxl], ch[maxl];

set<char> chars;
int pos[26], num[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

#define N (num[pos[str[i] - 'a']])
inline LL parse(const char* str)
{
    LL res = 0LL;
    for(int i=0; str[i]; i++)
        res = res * 10LL + N;
    return res;
}

inline void print(const char* str)
{
    for(int i=0; str[i]; i++)
        putchar(N + '0');
    putchar('\n');
}
#undef N

inline void add(const char* str)
{
    for(int i=0; str[i]; i++)
        chars.insert(str[i]);
}

inline bool isok(const char* str)
{
    return num[pos[str[0] - 'a']] != 0;
}

int main()
{
    scanf("%s%s%s", s1, s2, s3);
    add(s1), add(s2), add(s3);
    if(chars.size() > 11)
    {
        puts("UNSOLVABLE");
        return 0;
    }
    int cnt = 0;
    for(char x: chars)
        pos[x - 'a'] = cnt++;
    do
    {
        if(isok(s1) && isok(s2) && isok(s3) && (parse(s1) + parse(s2) == parse(s3)))
        {
            print(s1);
            print(s2);
            print(s3);
            return 0;
        }
    } while(next_permutation(num, num + 10));
    puts("UNSOLVABLE");
    return 0;
}

P.S. This code runs surprisingly fast… took only 109ms…

E - Unique Color

Problem Statement

Given a tree with $N$ vertices, each vertex has a color $C_i$. A vertex $x$ is good if:

The shortest path from vertex $1$ to $x$ contains no duplicate colors (excluding $x$ itself).

Output all good vertices in ascending order.

$2\le N\le 10^5$
$1\le C_i\le 10^5$

Input Format

$N$
$C_1~\dots~C_N$
$A_1~B_1$
$\vdots$
$A_{N-1}~B_{N-1}$

Output Format

List all good vertices, one per line.

Analysis

Use DFS to track colors along the path. Maintain a used array to check color uniqueness. Time complexity: $\mathcal O(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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


#include <cstdio>
#include <vector>
#include <set>
#define maxn 100005
using namespace std;

vector<int> G[maxn];
bool used[maxn];
int color[maxn];

set<int> res;

void dfs(int v, int par)
{
    if(used[color[v]])
    {
        for(int u: G[v])
            if(u != par)
                dfs(u, v);
        return;
    }
    used[color[v]] = true;
    res.insert(v);
    for(int u: G[v])
        if(u != par)
            dfs(u, v);
    used[color[v]] = false;
}

int main()
{
    int n;
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        scanf("%d", color + i);
    while(--n)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1, -1);
    for(int v: res)
        printf("%d\n", v);
    return 0;
}