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 - Rock-paper-scissors

Three people play rock-paper-scissors to a draw. Two of them chose $x$ and $y$ respectively. Determine the third person’s choice.

$0\le x,y\le 2$ (0=Rock, 1=Scissors, 2=Paper)

Input Format

$x,y$

Output Format

Output the integer representing the third person’s choice.

Samples

$x$	$y$	Output
$0$	$1$	$2$
$0$	$0$	$0$

Analysis

A three-way draw occurs in two cases (let $z$ be the third person’s choice):

$x=y=z$
All three choices are distinct

The formula can be derived as:
$z=\begin{cases}x & (x=y)\\3-x-y & (x\ne y)\end{cases}$

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


#include <cstdio>
using namespace std;

int main()
{
    int x, y;
    scanf("%d%d", &x, &y);
    printf("%d\n", x == y? x: 3 - x - y);
    return 0;
}

B - Nuts

There are $N$ trees. The $i$-th tree has $A_i$ nuts. A person collects $\max(0,A_i-10)$ nuts from each tree. Calculate the total collected nuts.

$1\le N,A_i\le 1000$

Input Format

$N$
$A_1~\dots~A_N$

Output Format

Output the total.

Samples

Sample Input 1

Sample Output 1

1

25

Collected nuts: $0+7+18=25$

Sample Input 2

Sample Output 2

1

1

Only the last tree contributes 1 nut.

Analysis

Simulate according to the problem statement.

Code

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


#include <cstdio>
using namespace std;

int main()
{
    int n, ans = 0;
    scanf("%d", &n);
    while(n--)
    {
        int a;
        scanf("%d", &a);
        if(a > 10) ans += a - 10;
    }
    printf("%d\n", ans);
    return 0;
}

C - Tour

A country has $N$ cities and $M$ one-way roads. Count the number of valid ordered pairs $(X,Y)$ where one can travel from city $X$ to city $Y$ through any number of roads (including staying at the same city).

$2\le N\le 2000$
$0\le M\le \min(2000,N(N-1))$
All roads are distinct and not self-looping.

Input Format

$N~M$
$A_1~B_1$
$\vdots$
$A_M~B_M$

Output Format

Output the count.

Samples

Sample Input 1

Sample Output 1

1

7

Valid pairs: (1,1), (1,2), (1,3), (2,2), (2,3), (3,2), (3,3)

Sample Input 2

1

3 0

Sample Output 2

1

3

Only self-pairs are valid.

Analysis

Model the country as a directed unweighted graph. Perform DFS from each node to count reachable nodes. Time complexity: $\mathcal O(n^2)$.

Code

Note: Reset the vis array before each DFS!

 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


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

vector<int> G[maxn];
bool vis[maxn];

int ans;

void dfs(int v)
{
    if(vis[v]) return;
    vis[v] = true, ans ++;
    for(int u: G[v])
        dfs(u);
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    while(m--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        G[--x].push_back(--y);
    }
    ans = 0;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
            vis[j] = false;
        dfs(i);
    }
    printf("%d\n", ans);
    return 0;
}

D - Cooking

Two people wash $N$ dishes. Dish $i$ takes $T_i$ minutes. Calculate the minimum time to wash all dishes when working in parallel.

$1\le N\le 100$
$1\le T_i\le 10^3$

Input Format

$N$
$T_1~T_2~\dots~T_N$

Output Format

Output the minimal total time.

Samples

Sample Input 1

Sample Output 1

1

13

Optimal split: 13 (8+5) vs 10 (3+7+2)

Sample Input 2

Sample Output 2

1

1000

Sample Input 3

1
2


9
3 14 15 9 26 5 35 89 79

Sample Output 3

1

138

Analysis

Classic 0-1 knapsack problem. Find the maximum subset sum not exceeding half of total time. Answer is total minus this subset sum.

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 105
#define maxv 100005
using namespace std;

int dp[maxv], w[maxn];

inline void setmax(int& x, int y)
{
    if(y > x) x = y;
}

int main()
{
    int n, v = 0;
    scanf("%d", &n);
    for(int i=0; i<n; i++)
    {
        scanf("%d", w + i);
        v += w[i];
    }
    int t = v;
    v >>= 1;
    for(int i=0; i<n; i++)
        for(int j=v; j>=w[i]; j--)
            setmax(dp[j], dp[j - w[i]] + w[i]);
    printf("%d\n", t - dp[v]);
    return 0;
}

E - Rush Hour 2

A country has $N$ cities and $M$ bidirectional roads. The travel time through road $i$ at time $t$ is $C_i+\lfloor\frac{D_i}{t+1}\rfloor$. Find the earliest time to reach city $N$ from city $1$, or output -1.

$2\le N\le 10^5$
$2\le M\le 10^5$
$0\le C_i,D_i\le 10^9$

Input Format

$N~M$
$A_1~B_1~C_1~D_1$
$\vdots$
$A_M~B_M~C_M~D_M$

Output Format

Output the minimal time or -1.

Samples

Sample Input 1

Sample Output 1

1

4

Depart at t=1: 1+2+⌊3/2⌋=4

Sample Input 2

Sample Output 2

1

3

Multiple roads and self-loops allowed.

Sample Input 3

Sample Output 3

1

-1

No valid path exists.

Analysis

Model as graph and use Dijkstra’s algorithm. For each edge, optimal departure time is around $\lfloor\sqrt{D}\rfloor-1$. Time complexity: $\mathcal O(M\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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49


#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <tuple>
#define maxn 100005
#define INF 9223372036854775807LL
using namespace std;

using Road = tuple<int, int, int>;
using LL = long long;
using pli = pair<LL, int>;

vector<Road> G[maxn];
LL dist[maxn];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    while(m--)
    {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        if(--a == --b) continue;
        G[a].emplace_back(b, c, d);
        G[b].emplace_back(a, c, d);
    }
    dist[0] = 0LL;
    for(int i=1; i<n; i++) dist[i] = INF;
    priority_queue<pli, vector<pli>, greater<pli>> q;
    q.emplace(0LL, 0);
    while(!q.empty())
    {
        auto [t, u] = q.top(); q.pop();
        if(dist[u] != t) continue;
        for(auto [v, c, d]: G[u])
        {
            LL t2 = sqrt((long double) d) - 0.5;
            if(t2 < t) t2 = t;
            t2 += LL(c) + LL(d) / (t2 + 1LL);
            if(t2 < dist[v])
                q.emplace(dist[v] = t2, v);
        }
    }
    if(dist[n - 1] == INF) puts("-1");
    else printf("%lld\n", dist[n - 1]);
    return 0;
}