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 - Health M Death

Problem Statement

A magician is fighting a monster with HP $H$.
The magician can defeat the monster when its HP is a multiple of $M$.
Can the magician defeat the monster?

$1\le M,H\le 1000$

Input Format

$M~H$

Output Format

Print Yes if the magician can defeat the monster; otherwise, print No.

Sample Cases

Analysis

Check if $H$ is a multiple of $M$.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

#include <cstdio>
using namespace std;

int main()
{
    int m, h;
    scanf("%d%d", &m, &h);
    puts(h % m == 0? "Yes": "No");
    return 0;
}

B - Many Oranges

Problem Statement

We have many oranges. Each orange weighs between $A$ and $B$ grams (inclusive, possibly non-integer).
The total weight of these oranges is exactly $W$ kilograms.
Find the minimum and maximum possible number of oranges.

$1\le A\le B\le 1000$
$1\le W\le 1000$

Input Format

$A~B~W$

Output Format

Print the minimum and maximum number of oranges separated by a space. If the scenario is impossible, print UNSATISFIABLE.

Sample Cases

Analysis

For the minimum number, assume each orange has maximum weight $B$: $min = \lceil \frac{W \times 1000}{B} \rceil$.
For the maximum number, assume each orange has minimum weight $A$: $max = \lfloor \frac{W \times 1000}{A} \rfloor$.
If $min > max$, output UNSATISFIABLE; otherwise, output $min$ and $max$.

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, w;
    scanf("%d%d%d", &a, &b, &w);
    w *= 1000;
    int min = w % b == 0? w / b: w / b + 1;
    int max = w / a;
    if(min > max) puts("UNSATISFIABLE");
    else printf("%d %d\n", min, max);
    return 0;
}

C - Comma

Problem Statement

When writing an integer, we place a comma every three digits from the right. For example, $1234567$ becomes 1,234,567, and $777$ remains 777.
How many commas are needed when writing all integers from $1$ to $N$ inclusive?

$1\le N\le 10^{15}$

Input Format

$N$

Output Format

Print the total number of commas.

Sample Cases

Analysis

Count commas by digit positions. For each power of 1000 starting from $10^3$, add the count of numbers greater than or equal to that power.

Code

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

#include <cstdio>
using namespace std;

typedef long long LL;

int main()
{
    LL n, ans = 0LL;
    scanf("%lld", &n);
    for(LL p=1000LL; p<=n; p*=1000LL)
        ans += n - p + 1;
    printf("%lld\n", ans);
    return 0;
}

D - Shipping Center

Problem Statement

We have $N$ packages (1 to $N$) and $M$ boxes (1 to $M$).
Package $i$ has size $W_i$ and value $V_i$.
Box $i$ can hold exactly one package with size $\leq X_i$.
For $Q$ queries, each specifying $L$ and $R$, determine the maximum total value when boxes $L$ to $R$ are unavailable.

$1\le N,M,Q\le 50$
$1\le W_i,V_i,X_i\le 10^6$
$1\le L\le R\le M$

Input Format

$N~M~Q$
$W_1~V_1$
$\vdots$
$W_N~V_N$
$X_1~\dots~X_M$
$L_1~R_1$
$\vdots$
$L_Q~R_Q$

Output Format

Print $Q$ lines containing answers for each query.

Sample Input

1
2
3
4
5
6
7
8

3 4 3
1 9
5 3
7 8
1 8 6 9
4 4
1 4
1 3

Sample Output

1
2
3

20
0
9

Analysis

Sort boxes by size. For each query, greedily assign the most valuable package that fits each available box.

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

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

typedef pair<int, int> pii;

pii bags[maxn], boxes[maxn];
bool taken[maxn];

int main()
{
    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);
    for(int i=0; i<n; i++)
        scanf("%d%d", &bags[i].second, &bags[i].first);
    sort(bags, bags + n, greater<pii>());
    for(int i=0; i<m; i++)
        scanf("%d", &boxes[i].first), boxes[i].second = i;
    sort(boxes, boxes + m);
    while(q--)
    {
        int l, r, ans = 0;
        scanf("%d%d", &l, &r);
        l --, r --;
        fill(taken, taken + n, false);
        for(int i=0; i<m; i++)
        {
            auto [size, idx] = boxes[i];
            if(idx < l || idx > r)
            {
                int j = 0;
                for(; j<n; j++)
                    if(!taken[j] && bags[j].second <= size)
                        break;
                if(j < n)
                    ans += bags[j].first, taken[j] = true;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

E - Lucky 7 Battle

Problem Statement

Given a digit string $S$ of length $N$ and a string $X$ of A and T of length $N$, Takahashi and Aoki play a game:

• On turn $i$, if $X_i$ is A, Aoki chooses to append $S_i$ or 0 to string $T$; otherwise, Takahashi chooses.
• After $N$ turns, if $T$ represents a number divisible by 7, Takahashi wins; else, Aoki wins.

Determine the winner when both play optimally.

$1\le N\le 10^5$

Input Format

$N$
$S$
$X$

Output Format

Print Takahashi or Aoki.

Sample Cases

See AtCoder.

Analysis

Use memoization to track the winner for each (turn, current modulo 7). The current player wins if any choice leads to their victory.

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

#include <cstdio>
#include <cstring>
#define maxn 200005
using namespace std;

char s[maxn], x[maxn];
int n, dp[maxn][7];

int winner(int i, int r)
{
    if(dp[i][r] != -1) return dp[i][r];
    if(i >= n) return dp[i][r] = r == 0;
    if(winner(i + 1, 10 * r % 7) == TA)
    {
        if(x[i] == 'T')
            return dp[i][r] = TA;
    }
    else if(x[i] == 'A') return dp[i][r] = AO;
    if(winner(i + 1, (10 * r + s[i] - '0') % 7) == TA)
    {
        if(x[i] == 'T')
            return dp[i][r] = TA;
    }
    else if(x[i] == 'A') return dp[i][r] = AO;
    return dp[i][r] = x[i] == 'A';
}

int main()
{
    scanf("%d%s%s", &n, s, x);
    memset(dp, -1, sizeof(dp));
    puts(winner(0, 0) == TA? "Takahashi": "Aoki");
    return 0;
}