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 - I Scream

Problem Statement

In Japan, there are four types of ice cream products:

• Products with at least 15% milk solids and 8% milk fat are called “ice cream”;
• Products with at least 10% milk solids and 3% milk fat that are not ice cream are called “ice milk”;
• Products with at least 3% milk solids that are neither ice cream nor ice milk are called “lacto ice”;
• Products that do not fall into any of the above categories are called “flavored ice”.

Here, milk solids consist of milk fat and milk solids-not-fat.
Given an ice cream product containing A% milk solids-not-fat and B% milk fat, determine its category.

Constraints:

• $0\le A,B\le 100$
• $0\le A+B\le 100$

Input Format

A B

Output Format

Output the category number:

• 1 for ice cream
• 2 for ice milk
• 3 for lacto ice
• 4 for flavored ice

Sample Cases

Analysis

Calculate total milk solids by adding A and B, then check the conditions sequentially.

Code

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

#include <cstdio>
using namespace std;

int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    a += b;
    if(a >= 15 && b >= 8) puts("1");
    else if(a >= 10 && b >= 3) puts("2");
    else if(a >= 3) puts("3");
    else puts("4");
    return 0;
}

B - Job Assignment

Problem Statement

A company has N employees. Employee i can complete Job A in A_i minutes and Job B in B_i minutes. Assign each job to one employee (possibly the same). The completion time t is:

• A_i + B_i if both jobs go to employee i
• max(A_i, B_j) if different employees take the jobs

Find the minimum possible t.

Constraints:

• $2 \le N \le 1000$
• $1 \le A_i, B_i \le 10^5$

Input Format

1
2
3
4

N
A_1 B_1
...
A_N B_N

Output Format

Print the minimal t.

Sample Cases

Please refer to AtCoder.

Analysis

Brute-force all possible (i,j) pairs with O(N²) complexity. Optimizations exist but are more complex.

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

int a[maxn], b[maxn];

inline void setmin(int& x, int y) { if(y < x) x = y; }
inline int max(int x, int y) { return x > y ? x : y; }

int main()
{
    int n;
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        scanf("%d%d", a + i, b + i);
    int ans = INF;
    for(int i=0; i<n; i++)
    {
        setmin(ans, a[i] + b[i]); // Same employee
        for(int j=i+1; j<n; j++)
        {
            setmin(ans, max(a[i], b[j]));
            setmin(ans, max(a[j], b[i]));
        }
    }
    printf("%d\n", ans);
    return 0;
}

C - Squared Error

Problem Statement

Constraints:

• $2 \le N \le 3 \times 10^5$
• $|A_i| \le 200$

Input Format

1
2

N
A_1 A_2 ... A_N

Output Format

Print the computed sum.

Sample Cases

Sample Input 1

1
2

3
2 8 4

Sample Output 1

1

56

Sample Input 2

1
2

5
-5 8 9 -4 -3

Sample Output 2

1

950

Analysis

where S_i is the sum of previous elements.

Code

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

#include <cstdio>
#define maxn 300005
using namespace std;

using LL = long long;

int main()
{
    int n, s1 = 0;
    scanf("%d", &n);
    LL s2 = 0, m = 0LL;
    for(int i=0; i<n; i++)
    {
        LL x;
        scanf("%lld", &x);
        m += x * s1;
        s1 += x, s2 += x * x;
    }
    m <<= 1LL, s2 *= n - 1LL;
    printf("%lld\n", s2 - m);
    return 0;
}

D - Journey

Problem Statement

On a graph with N nodes and no edges initially, perform operations until the graph becomes connected:

1. Randomly select a vertex (uniform probability).
2. Add an edge between current and selected vertex, then move to it.

Compute the expected number of operations.

Constraints:

• $2 \le N \le 10^5$

Input Format

1

N

Output Format

Print the answer with absolute error ≤1e-6.

Sample Cases

Analysis

Code

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

#include <cstdio>
using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    double res = 0;
    for(int i=1; i<n; i++)
        res += double(n) / i;
    printf("%.8lf\n", res);
    return 0;
}

E - Mex Min

Problem Statement

Given sequence A of length N, compute the minimum mex over all length-M contiguous subarrays.

Constraints:

• $1 \le M \le N \le 1.5 \times 10^6$
• $0 \le A_i \le N$

Input Format

1
2

N M
A_1 A_2 ... A_N

Output Format

Print the minimal mex.

Sample Cases

Please refer to AtCoder.

Analysis

Maintain a sliding window count and track zeros using a set for efficient mex calculation.

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

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

int cnt[maxn], a[maxn];

set<int> s;

inline void setmin(int& x, int y)
{
    if(y < x) x = y;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i=0; i<n; i++)
        scanf("%d", a + i);
    for(int i=0; i<m; i++)
        cnt[a[i]] ++;
    for(int i=0; i<n; i++)
        if(cnt[i] == 0)
            s.insert(i);
    s.insert(n);
    int ans = *s.begin();
    n -= m;
    for(int i=0; i<n; i++)
    {
        if(cnt[a[i + m]]++ == 0) s.erase(a[i + m]);
        if(--cnt[a[i]] == 0) s.insert(a[i]);
        setmin(ans, *s.begin());
    }
    printf("%d\n", ans);
    return 0;
}