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

Problem Statement

In which century does the year $N$ fall?

A century consists of 100 consecutive years. For example, the 1st century is years [1,100], the 2nd century is years [101,200], etc.

$1\le N\le 3000$

Input Format

$N$

Output Format

Print the answer as an integer.

Sample Cases

$N$	Output
$2021$	$21$
$200$	$2$

Analysis

We can derive that year $N$ belongs to the $\lceil \frac N {100}\rceil$ century.

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 % 100 == 0? n / 100: n / 100 + 1);
    return 0;
}

B - 200th ABC-200

Problem Statement

Perform the following operations $K$ times on integer $N$:

If $N$ is a multiple of 200, divide it by 200.
Otherwise, append 200 to $N$ (e.g., 123 becomes 123200).

$1\le N\le 10^5$
$1\le K\le 20$

Input Format

$N~K$

Output Format

Print the final $N$.

Sample Cases

$N$	$K$	Output
$2021$	$4$	$50531$
$40000$	$2$	$1$
$8691$	$20$	$84875488281$

Analysis

We simulate the process while proving the result fits in long long:

Appending 200 to any $N$ makes it divisible by 200 (ends with two zeros).
After appending, dividing by 200 reduces digit count. Thus, $N$ remains strictly below $2^{63}$.

Code

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


#include <cstdio>
using namespace std;

int main()
{
    long long n;
    int k;
    scanf("%lld%d", &n, &k);
    while(k--)
        n = n % 200LL == 0LL? n / 200LL: n * 1000LL + 200LL;
    printf("%lld\n", n);
    return 0;
}

C - Ringo’s Favorite Numbers 2

Problem Statement

Given sequence $A=(A_1,A_2,\dots,A_N)$, find all pairs $(i,j)$ satisfying:

$1\le i < j\le N$
$|A_i-A_j|$ is a multiple of 200.

$2\le N\le 2\times 10^5$
$1\le A_i\le 10^9$

Output Format

$N$
$A_1~A_2~\dots~A_N$

Sample Cases

$A$	Output
$(123,223,123,523,200,2000)$	$4$
$(1,2,3,4,5)$	$0$
$(199,100,200,400,300,500,600,200)$	$9$

Analysis

We use modulo 200 buckets to count pairs in $\mathcal O(n)$ time:

Elements in the same remainder bucket form valid pairs.
For each element, add current bucket count to the answer before updating the bucket.

Note: The answer must be of type long long!

Code

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


#include <cstdio>
#define MOD 200
using namespace std;

int cnt[MOD];

int main()
{
    int n;
    scanf("%d", &n);
    long long ans = 0LL;
    while(n--)
    {
        int x;
        scanf("%d", &x);
        ans += cnt[x %= MOD] ++;
    }
    printf("%lld\n", ans);
    return 0;
}

D - Happy Birthday! 2

Problem Statement

Given sequence $A=(A_1,A_2,\dots,A_N)$, find two distinct subsequences $B$ and $C$ (different indices, not necessarily contiguous) such that $\sum B\equiv \sum C\pmod{200}$.

$2\le N\le 200$
$1\le A_i\le 10^9$

Input Format

$N$
$A_1~A_2~\dots~A_N$

Output

If no solution exists, print No.
Otherwise, output:
$\text{Yes}$
$x~B'_1~B'_2~\dots~B'_x$
$y~C'_1~C'_2~\dots~C'_y$

Sample Cases

See AtCoder for details.

Analysis

When $N\ge 8$, pigeonhole principle guarantees a solution (255 subsets mod 200). For $N<8$, brute-force all subsets.

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


#include <cstdio>
#include <vector>
#define maxn 10
#define MOD 200
using namespace std;

int a[maxn];
vector<int> bkt[MOD];

inline void print(const vector<int>& v)
{
    printf("%llu", v.size());
    for(int x: v)
        printf(" %d", x + 1);
    putchar('\n');
}

int main()
{
    int n;
    scanf("%d", &n);
    if(n > 8) n = 8;
    for(int i=0; i<n; i++)
        scanf("%d", a + i);
    int lim = 1 << n;
    for(int st=0; st<lim; st++)
    {
        int s = 0;
        vector<int> pos;
        for(int i=0; i<n; i++)
            if(st >> i & 1)
                s = (s + a[i]) % MOD, pos.push_back(i);
        if(!bkt[s].empty())
        {
            puts("Yes");
            print(bkt[s]);
            print(pos);
            return 0;
        }
        else bkt[s] = pos;
    }
    puts("No");
    return 0;
}

E - Patisserie ABC 2

Problem Statement

There are $N^3$ triples $(i,j,k)$ ($1\le i,j,k\le N$), ordered by:

Ascending $i+j+k$
For equal sums, ascending $i$, then $j$

Find the $K$-th triple.

$1\le N\le 10^6$
$1\le K\le N^3$

Input Format

$N~K$

Output Format

Print the $K$-th triple separated by spaces.

Sample Cases

$N$	$K$	Output
$2$	$5$	$1 2 2$
$1000000$	$1000000000000000000$	$1000000 1000000 1000000$
$9$	$47$	$3 1 4$

Analysis

Iterate possible sums $s$ and compute valid triples count using inclusion-exclusion:

Number of solutions to $i+j+k=s$ in $[1,N]$ is $f(s) - 3f(s-N) + 3f(s-2N)$ where $f(n) = \binom{n-1}{2}$ for $n\ge3$.

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


#include <cstdio>
using namespace std;

using LL = long long;
int n;

inline int max(int x, int y) { return x > y? x: y; }
inline int min(int x, int y) { return x < y? x: y; }

inline LL f(LL n) { return n-- > 2? n * (n - 1LL) >> 1LL: 0LL; }
inline LL count(int s) { return f(s) - 3 * (f(s - n) - f(s - (n << 1))); }

int main()
{
    LL k;
    scanf("%d%lld", &n, &k);
    int lim = n * 3;
    for(int sum=3; sum<=lim; sum++)
    {
        LL cnt = count(sum);
        if(k > cnt) { k -= cnt; continue; }
        for(int a=1; a<=n; a++)
        {
            int minb = max(1, sum - a - n), maxb = min(n, sum - a - 1);
            if(minb > maxb) continue;
            int num = maxb - minb + 1;
            if(k <= num)
            {
                int b = minb + k - 1;
                int c = sum - a - b;
                printf("%d %d %d\n", a, b, c);
                return 0;
            }
            k -= num;
        }
    }
    return 0;
}