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

D - Trophy

Problem Statement

A game consists of $N$ stages. The $i$-th stage is represented by a pair $(A_i, B_i)$.

To clear a stage, you must first spend $A_i$ time watching an introduction. Then, it takes $B_i$ time to clear the stage. For subsequent clears of the same stage, the introduction is skipped (i.e., clearing the $i$-th stage $M$ times in total requires $A_i + M \times B_i$ time).

Initially, only the first stage is unlocked. After clearing any stage, the next stage is automatically unlocked (except the last stage). Find the minimum time required to clear exactly $X$ stages (repeats count).

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

Input Format

$N~X$
$A_1~B_1$
$\vdots$
$A_N~B_N$

Output Format

Print the answer.

Sample

Refer to AtCoder.

Analysis

The optimal strategy involves clearing some initial stages once, then repeatedly clearing a particular stage. Using prefix sums and enumerating each stage, we achieve $\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


#include <cstdio>
#define INF 0x7FFFFFFFFFFFFFFFLL
using namespace std;

int main()
{
    int n, x;
    scanf("%d%d", &n, &x);
    if(x < n) n = x;
    long long s = 0LL, ans = INF, cur;
    for(int i=1; i<=n; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if((cur = (s += a + b) + (long long)(x - i) * b) < ans)
            ans = cur;
    }
    printf("%lld\n", ans);
    return 0;
}

E - Packing Potatoes

Problem Statement

There are $10^{100}$ potatoes arranged in a sequence. The weight of the $i$-th potato is $W_{i \bmod N}$ (weights cycle every $N$ elements).

Takahashi packs potatoes into boxes sequentially. When the total weight in a box reaches at least $X$, he starts a new box.

Given $Q$ queries, each asking for the number of potatoes in the $K_i$-th box.

$1\le N,Q\le 2\times 10^5$
$1\le X,W_i\le 10^9$
$1\le K_i\le 10^{12}$

Input Format

$N~Q~X$
$W_0~\dots~W_{N-1}$
$K_1$
$\vdots$
$K_Q$

Output Format

Print $Q$ lines, each containing the answer.

Sample

Refer to AtCoder.

Analysis

Cyclic pattern problem.

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74


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

using LL = long long;
int cnt[maxn], ord[maxn], w[maxn << 1];

template <typename T>
inline T read()
{
    char c;
    while((c = getchar()) < '0' || c > '9');
    T res = c ^ 48;
    while((c = getchar()) >= '0' && c <= '9')
        res = (res << T(3)) + (res << T(1)) + (c ^ 48);
    return res;
}

inline void print(int x)
{
    if(x > 9) print(x / 10);
    putchar(x % 10 ^ 48);
}

inline void println(int x)
{
    print(x);
    putchar('\n');
}

int main()
{
    int n = read<int>(), q = read<int>(), x = read<int>();
    LL sum = 0LL;
    for(int i=0; i<n; i++)
        sum += w[i + n] = w[i] = read<int>();
    int fill = x / sum * n;
    for(int i=0; i<n; i++)
        cnt[i] = fill, ord[i] = -1;
    x %= sum;
    for(int i=0, j=0, s=0; i<n; i++)
    {
        if(j < i) j = i, s = 0;
        while(s < x)
        {
            s += w[j];
            j += 1;
        }
        cnt[i] += j - i;
        s -= w[i];
    }
    vector<int> path;
    int loop = -1;
    for(int u=0, k=0; ; k++)
    {
        if(ord[u] != -1)
        {
            loop = k - ord[u];
            break;
        }
        ord[u] = k;
        path.push_back(u);
        (u += cnt[u]) %= n;
    }
    int non_loop = path.size() - loop;
    while(q--)
    {
        LL k = read<LL>();
        println(cnt[path[--k < non_loop? k:
                non_loop + (k - non_loop) % loop]]);
    }
    return 0;
}

F - Main Street

WJ...

G - Triangle

Problem Statement

Given a simple undirected graph $G$ with $N$ vertices and its adjacency matrix $A$:

$A_{i,j}=1$ indicates an edge between vertices $i$ and $j$
$A_{i,j}=0$ otherwise (with $A_{i,i}=0$ for all $i$)

Count the number of triples $(i,j,k)$ satisfying:

$1\le i < j < k \le N$
$A_{i,j}=A_{i,k}=A_{j,k}=1$

$3\le N\le 3000$

Input Format

$N$
$A_{1,1}A_{1,2}\dots A_{1,N}$
$A_{2,1}A_{2,2}\dots A_{2,N}$
$\vdots$
$A_{N,1}A_{N,2}\dots A_{N,N}$ (e.g., 10110)

Output Format

Print the count.

Sample

Refer to AtCoder.

Analysis

The naive $\mathcal O(N^3)$ approach can be optimized using bitset operations. For each edge $(i,j)$, compute the intersection of $i$’s and $j$’s adjacency lists, then sum all intersections and divide by 3. Time complexity: $\mathcal O(N^3 / w)$ where $w$ is bitset width (64).

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>
#include <bitset>
#define maxn 3000
using namespace std;

bitset<maxn> a[maxn];

int main()
{
    int n = 0; char c;
    while((c = getchar()) != '\n')
        n = (n << 3) + (n << 1) + (c ^ 48);
    for(int i=0; i<n; i++, getchar())
        for(int j=0; j<n; j++)
            if(getchar() == '1')
                a[i].set(j);
    long long ans = 0LL;
    for(int i=0; i+1<n; i++)
        for(int j=i+1; j<n; j++)
            if(a[i][j])
                ans += (a[i] & a[j]).count();
    printf("%lld\n", ans / 3LL);
    return 0;
}