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 - Full House

Problem Summary

~~Translation from a passionate card game enthusiast qwq~~

Given five card numbers $A,B,C,D,E$ from a poker deck, determine if they form a “three-of-a-kind plus a pair”. ~~(Baidu it if unclear~~

Constraints: $1\le A,B,C,D,E\le 13$, and not all $A,B,C,D,E$ are identical.

Input Format

$A~B~C~D~E$

Output Format

Print Yes if a full house, otherwise No.

Sample Cases

$A$	$B$	$C$	$D$	$E$	Output
$1$	$2$	$1$	$2$	$1$	`Yes`
$12$	$12$	$11$	$1$	$2$	`No`

Analysis

Hehe, ~~amused by~~ startled by my own translation—never seen such a ~~good~~ terrible one!
Straightforward problem. Count frequencies and check for exactly two and three counts. See code.

Code

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


#include <cstdio>
using namespace std;

int cnt[13];

int main()
{
    for(int i=0; i<5; i++)
    {
        int x;
        scanf("%d", &x);
        cnt[--x] ++;
    }
    bool has2 = false, has3 = false;
    for(int i=0; i<13; i++)
        if(cnt[i] == 2) has2 = true;
        else if(cnt[i] == 3) has3 = true;
    puts(has2 && has3? "Yes": "No");
    return 0;
}

B - Ancestor

Problem Summary

There are $N$ people. The parent of the $i$-th person is $P_i$, guaranteed $P_i < i$.
Find how many generations apart the $N$-th person is from the 1st person.

$2\le N\le 50$
$1\le P_i < i$

Input Format

$N$
$P_2~P_3~\dots~P_N$

Output Format

Print the answer.

Analysis

No DFS needed. Compute depth iteratively: $\text{depth}_i = \text{depth}_{P_i} + 1$.

Code

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


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

int dep[maxn];

int main()
{
    int n;
    scanf("%d", &n);
    for(int i=1; i<n; i++)
    {
        int f;
        scanf("%d", &f);
        dep[i] = dep[--f] + 1;
    }
    printf("%d\n", dep[n - 1]);
    return 0;
}

C - Monotonically Increasing

Problem Summary

Print all strictly increasing sequences of length $N$ with elements in $[1,M]$ in lex order. $1\le N\le M\le 10$.

Input Format

$N~M$

Output Format

Print each sequence in lex order, one per line, space-separated.

Analysis

Basic backtracking problem. See code.

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


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

int n, m, ans[maxn];

void dfs(int pos, int last)
{
    if(pos == n)
    {
        for(int i=0; i<n; i++)
            printf("%d ", ans[i]);
        putchar('\n');
        return;
    }
    while(++last <= m)
    {
        ans[pos] = last;
        dfs(pos + 1, last);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    dfs(0, 0);
    return 0;
}

D - Left Right Operation

Problem Summary

Given integer sequence $A=(A_1,A_2,\dots,A_N)$, perform at most one left operation (replace first $x$ elements with $L$) and one right operation (replace last $y$ elements with $R$). Find the minimal possible sum.

$1\le N\le 2\times 10^5$
$-10^9\le L,R,A_i\le 10^9$

Input Format

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

Output Format

Print the minimal sum.

Analysis

Precompute prefix $f_i$ (min sum for first $i$ elements using left operations) and suffix $g_i$ (min sum for last $i$ elements using right operations). Answer is $\min(f_i + g_{N-i})$.

Time complexity: $\mathcal O(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


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

using LL = long long;
inline LL min(const LL& x, const LL& y)
{
    return x < y? x: y;
}

int a[maxn];
LL f[maxn], g[maxn];

int main()
{
    int n, l, r;
    scanf("%d%d%d", &n, &l, &r);
    for(int i=0; i<n; i++)
        scanf("%d", a + i);
    f[0] = min(l, a[0]);
    for(int i=1; i<n; i++)
        f[i] = min(f[i - 1] + a[i], (i + 1LL) * l);
    for(int i=n-1; i>=0; i--)
        g[i] = min(g[i + 1] + a[i], LL(n - i) * r);
    LL ans = g[0];
    for(int i=0; i<n; i++)
        ans = min(ans, f[i] + g[i + 1]);
    printf("%lld\n", ans);
    return 0;
}

E - Sugoroku 3

Problem Summary

$N$ squares. On squares $1$ to $N-1$, a die outputs $0,1,\dots,A_i$ uniformly. Move forward by the die result. Find the expected steps to reach square $N$, modulo $998244353$.

$2\le N\le 2\times 10^5$
$1\le A_i\le N-i$ ($1\le i < N$)

Rational Number Modulo
For division, compute $A \times B^{MOD-2} \bmod MOD$.

Input Format

$N$
$A_1~A_2~\dots~A_{N-1}$

Output Format

Print the answer modulo $998244353$.

Analysis

$$ \text{dp}_i = \frac{\sum_{j=i}^{i+A_i} \text{dp}_j}{A_i+1} + 1 $$

Solve for $\text{dp}_i$ and use suffix sums for optimization. Time complexity: $\mathcal O(N \log P)$.

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>
#define maxn 200005
#define MOD 998244353
using namespace std;

using LL = long long;
int a[maxn], suf[maxn];

inline int inv(LL x)
{
    LL res = 1LL;
    int p = MOD - 2;
    while(p)
    {
        if(p & 1) (res *= x) %= MOD;
        (x *= x) %= MOD, p >>= 1;
    }
    return res;
}

int main()
{
    int n, cur;
    scanf("%d", &n);
    for(int i=0; i<n-1; i++)
        scanf("%d", a + i);
    for(int i=n-2; i>=0; i--)
    {
        int t = suf[i + 1] - suf[i + 1 + a[i]];
        if(t < 0) t += MOD;
        cur = (a[i] + t + 1LL) % MOD * inv(a[i]) % MOD;
        if((suf[i] = suf[i + 1] + cur) >= MOD)
            suf[i] -= MOD;
    }
    printf("%d\n", cur);
    return 0;
}