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

Problem Statement

We have a beverage that contains $A$ kilocalories per 100 milliliters. How many kilocalories does $B$ milliliters of this beverage contain?

$0\le A, B\le 1000$

Input Format

$A~B$

Output Format

Output the number of kilocalories in $B$ milliliters. Maximum allowable floating-point precision error is $10^{-6}$.

Samples

Analysis

The answer is simply $\frac{AB}{100}$.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

#include <cstdio>
using namespace std;

int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    a *= b;
    printf("%d.%d\n", a / 100, a % 100);
    return 0;
}

B - Permutation Check

Problem Statement

Given a sequence $A=(A_1,A_2,\dots,A_N)$ of length $N$, determine whether $A$ is a permutation of $(1, 2, \dots, N)$.

$1\le A_i\le N\le 10^3$

Input Format

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

Output Format

Print Yes if $A$ is a permutation of $(1, 2, \dots, N)$, otherwise print No.

Samples

Sample Input 1

1
2

5
3 1 2 4 5

Sample Output 1

1

Yes

$(3,1,2,4,5)$ is a permutation of $(1,2,3,4,5)$, so output Yes.

Sample Input 2

1
2

6
3 1 4 1 5 2

Sample Output 2

1

No

$(3,1,4,1,5,2)$ is not a permutation of $(1,2,3,4,5,6)$, so output No.

Sample Input 3

1
2

3
1 2 3

Sample Output 3

1

Yes

Sample Input 4

1
2

1
1

Sample Output 4

1

Yes

Analysis

Since $1\le A_i\le N$, $A$ is a permutation if and only if all numbers from $1$ to $N$ appear exactly once. We can track occurrences using an array with $\mathcal O(n)$ time complexity.

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

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

bool used[maxn];

int main()
{
    int n;
    scanf("%d", &n);
    for(int i=0; i<n; i++)
    {
        int a;
        scanf("%d", &a);
        if(used[a])
        {
            puts("No");
            return 0;
        }
        used[a] = true;
    }
    puts("Yes");
    return 0;
}

C - POW

Problem Statement

Given integers $A$, $B$, and $C$, determine whether $A^C$ is less than, greater than, or equal to $B^C$.

$-10^9\le A,B\le 10^9$
$1\le C\le 10^9$

Input Format

$A~B~C$

Output Format

Output:

• < if $A^C < B^C$,
• > if $A^C > B^C$,
• = if $A^C = B^C$.

Samples

Analysis

For even $C$, compare absolute values. For odd $C$, compare original values. This simplifies to comparing $|A|$ vs $|B|$ (if $C$ is even) or $A$ vs $B$ (if $C$ is odd).

Code

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

#include <cstdio>
using namespace std;

int main()
{
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    if(!(c & 1))
    {
        if(a < 0) a = -a;
        if(b < 0) b = -b;
    }
    puts(a < b? "<": a > b? ">": "=");
    return 0;
}

D - Kth Excluded

Problem Statement

Given a sorted sequence $A=(A_1,A_2,\dots,A_N)$ of positive integers and $Q$ queries, find the $K_i$-th smallest positive integer not present in $A$.

$1\le N,Q\le 10^5$
$1\le A_1 < A_2 < \dots < A_N\le10^{18}$
$1\le K_i\le 10^{18}$

Input Format

$N~Q$
$A_1~A_2~\dots~A_N$
$K_1$
$K_2$
$\hspace{5pt}\vdots$
$K_Q$

Output Format

Output $Q$ lines, each containing the answer for the corresponding query.

Samples

Sample Input 1

1
2
3
4
5

4 3
3 5 6 7
2
5
3

Sample Output 1

1
2
3

2
9
4

The missing positive integers are $1,2,4,8,9,10,11,\dots$. The 2nd, 5th, and 3rd smallest are $2$, $9$, $4$.

Sample Input 2

1
2
3
4

5 2
1 2 3 4 5
1
10

Sample Output 2

1
2

6
15

Analysis

Precompute how many elements in $A$ are less than each possible $k$, then use binary search to find the position where $k$ falls. Time complexity: $\mathcal O(Q \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

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

using LL = long long;
LL a[maxn];

int main()
{
    int n, q;
    scanf("%d%d", &n, &q);
    for(int i=0; i<n; i++)
    {
        scanf("%lld", a + i);
        a[i] -= i;
    }
    while(q--)
    {
        LL k;
        scanf("%lld", &k);
        printf("%lld\n", k + (upper_bound(a, a + n, k) - a));
    }
    return 0;
}

E - White and Black Balls

Problem Statement

Count the number of valid arrangements of $N$ white and $M$ black balls such that for every prefix of length $i$, the number of white balls $w_i$ and black balls $b_i$ satisfy $w_i \le b_i + K$. Modulo $10^9+7$.

$0\le N,M\le10^6$
$1\le N+M$
$0\le K\le N$

Input Format

$N~M~K$

Output Format

Output the count modulo $10^9+7$.

Samples

Analysis

The valid count equals the Catalan-like number $\binom{N+M}{N} - \binom{N+M}{M+K+1}$ when $N \le M + K$, otherwise $0$. This uses combinatorial subtraction for paths crossing a boundary.

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

#include <iostream>
#include <atcoder/modint>
using namespace std;

using modint = atcoder::modint1000000007;

modint f(int n, int m)
{
    if(n < 0 || m < 0)
        return 0;
    modint ret = 1;
    for(int i=1; i<=m; i++)
        ret = ret * (n + i) / i;
    return ret;
}

int main()
{
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    if(n > m + k) puts("0");
    else printf("%d\n", (f(n, m) - f(n - k - 1, m + k + 1)).val());
    return 0;
}