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

Problem Statement

If paying with a ¥1000 banknote (assuming available), how much change will the clerk return when paying for an item costing ¥N?

$1\le N\le 10000$

Input Format

$N$

Output Format

Single line with the change amount.

Samples

Input	Output
1900	100
3000	0

Analysis

Special cases:

If $N$ is divisible by 1000, output 0.
Otherwise, output $1000 - (n\mod1000)$.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


#include <cstdio>
using namespace std;

int main(int argc, char** argv)
{
    int n;
    scanf("%d", &n);
    if(n % 1000 == 0) puts("0");
    else printf("%d\n", 1000 - n % 1000);
    return 0;
}

B - Judge Status Summary

Problem Statement

A user solved a programming problem, receiving test results in four statuses: AC, WA, TLE, RE. Given $N$ test cases with results $S_1, S_2, \dots, S_N$, count and output the occurrences of each status.

$1\le N\le 10^5$
Each $S_i$ is AC, WA, TLE, or RE.

Input Format

$N$
$S_1$
$S_2$
$:$
$S_N$

Output Format

1
2
3
4


AC x [AC count]
WA x [WA count]
TLE x [TLE count]
RE x [RE count]

Note: Use lowercase ‘x’ instead of ‘×’!

Samples

Sample Input 1

1
2
3
4
5
6
7


6
AC
TLE
AC
AC
WA
TLE

Sample Output 1

1
2
3
4


AC x 3
WA x 1
TLE x 2
RE x 0

Counts: 3, 1, 2, 0 respectively.

Sample Input 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


10
AC
AC
AC
AC
AC
AC
AC
AC
AC
AC

Sample Output 2

1
2
3
4


AC x 10
WA x 0
TLE x 0
RE x 0

All test cases passed.

Analysis

Though other methods exist, we use map for simplicity (may be overkill).

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 <string>
#include <map>
using namespace std;

map<string, int> cnt;

int main(int argc, char** argv)
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        string s;
        cin>>s;
        cnt[s] ++;
    }
    cout<<"AC x "<<cnt["AC"]<<endl;
    cout<<"WA x "<<cnt["WA"]<<endl;
    cout<<"TLE x "<<cnt["TLE"]<<endl;
    cout<<"RE x "<<cnt["RE"]<<endl;
    return 0;
}

C - H and V

Problem Statement

Given a grid with $H$ rows and $W$ columns. Cell $(i,j)$ ($1\le i\le H$, $1\le j\le W$) is either # (black) or . (white). Select any rows and columns to paint red. How many selection methods leave exactly $K$ black cells?

$1\le H, W\le 6$
$1\le K\le HW$

Input Format

$H~W~K$
$c_{1,1}~c_{1,2}~\dots~c_{1,W}$
$c_{2,1}~c_{2,2}~\dots~c_{2,W}$
$\vdots$
$c_{H,1}~c_{H,2}~\dots~c_{H,W}$

Output Format

Single line with the valid method count.

Samples

Sample Input 1

1
2
3


2 3 2
..#
###

Sample Output 1

1

5

Five methods involving row 1 and/or columns 1-3.

Sample Input 2

1
2
3


2 3 4
..#
###

Sample Output 2

1

1

Only possible by selecting nothing.

Sample Input 3

1
2
3


2 2 3
##
##

Sample Output 3

1

0

Impossible.

Sample Input 4

1
2
3
4
5
6
7


6 6 8
..##..
.#..#.
#....#
######
#....#
#....#

Blogger’s note: This is the largest test case. Local runtime check ensures no TLE.

Sample Output 4

1

208

Analysis

Brute-force enumeration using bitmasking. Paint selected rows/columns to white (.), then count remaining black cells.

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


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

char c[maxn][maxn];
int h, w, k;
int cnt = 0;

int main(int argc, char** argv)
{
    scanf("%d%d%d", &h, &w, &k);
    for(int i=0; i<h; i++)
        scanf("%s", c[i]);
    int m1 = 1 << h, m2 = 1 << w, ans = 0;
    for(int hs=0; hs<m1; hs++)
        for(int ws=0; ws<m2; ws++)
        {
            char tmp[maxn][maxn]; // Cannot modify original, make copy
            memcpy(tmp, c, sizeof(c));
            for(int i=0; i<h; i++) // Rows
                if(hs & (1 << i)) for(int j=0; j<w; j++)
                    tmp[i][j] = '.';
            for(int i=0; i<w; i++) // Columns
                if(ws & (1 << i)) for(int j=0; j<h; j++)
                    tmp[j][i] = '.'; // NOT tmp[i][j]!
            int cnt = 0;
            for(int i=0; i<h; i++)
                for(int j=0; j<w; j++) if(tmp[i][j] == '#')
                    cnt ++;
            if(cnt == k) ans ++;
        }
    printf("%d\n", ans);
    return 0;
}

D - Chat in a Circle

Problem Statement

$N$ people arrive sequentially to form a circle. Each person’s comfort equals the smaller friendliness value of their immediate neighbors (first person gets 0). Maximize total comfort.

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

Input Format

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

Output Format

Single line with maximum total comfort.

Samples

Sample Input 1

Sample Output 1

1

7

Comfort sum: 0+3+2+2=7.

Sample Input 2

1
2


7
1 1 1 1 1 1 1

Sample Output 2

1

6

Analysis

Greedy approach: Sort descending, insert each person into position yielding maximum current comfort. Use priority queue.

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


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

int a[maxn], n;

struct Position
{
    int lf, rf, comfort;
    inline Position(int l, int r)
    {
        lf = l, rf = r;
        comfort = min(l, r);
    }
    inline bool operator<(const Position& p) const
    {
        return comfort < p.comfort;
    }
};

priority_queue<Position> q;

inline bool cmp(int x, int y) {return x > y;}

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        scanf("%d", a + i);
    sort(a, a + n, cmp);
    q.push(Position(a[0], a[1]));
    long long res = a[0];
    for(int i=2; i<n; i++)
    {
        Position p = q.top();
        if(q.size() > 1) q.pop();
        res += p.comfort;
        q.push(Position(a[i], p.lf));
        q.push(Position(a[i], p.rf));
    }
    printf("%lld\n", res);
    return 0;
}