2024 Summer Camp Coding Practice Record for Graduate Recommendations

Leetcode problem-solving can be a tad monotonous, so I plan to tackle one real problem set for a day (smile). I won't be tackling particularly difficult problems or extensive simulations to ensure a fast problem-solving pace.

I will follow a specific order in solving problems.

2023 Graduate Recommendation (5/14)

All Included

A: All Included

Total Time Limit: 1000ms Memory Limit: 65536kB Description You have designed a new encryption technique that encodes information by cleverly inserting random strings between the characters of the original message. Due to patent issues, we will not discuss how to generate and insert strings into the original information in detail. However, to verify your method, it is necessary to write a program to check if all the original information is included in the final string.

Given two strings s and t, you need to determine if s is a "subsequence" of t. That is, if you remove some characters from t, the remaining characters will concatenate to form s.

Input The input consists of multiple test cases. Each test case is a pair of specific strings s and t, composed of alphanumeric ASCII characters and separated by a space. The length of s and t does not exceed 100000.

Output For each test case, if s is a "subsequence" of t, print "Yes"; otherwise, print "No".

Warm-up problem. Use the two-pointer technique to scan once.

#include <iostream>
#include <string>

using namespace std;

int n;

bool isSub(string str, string sub) {
    int i = 0, l = 0;
    while (i < sub.size() && l < str.size()) {
        if (str[l] == sub[i]) i++, l++;
        else l++;
    }
    return i == sub.size();
}


int main() {
    string substr, str;
        
    while (cin >> substr >> str) {
        cout << (isSub(str, substr) ? "Yes" : "No" ) << endl;
    }
}

Closest Fraction

B: Closest Fraction Total Time Limit: 1000ms Memory Limit: 65536kB Description

What is the largest reduced fraction less than A/B for which the denominator does not exceed N?

Input

Three positive integers N, A, and B, separated by a single space. $1 \le A < B < N \le 1000$.

Output

Two positive integers, which are the numerator and the denominator of the desired fraction, separated by a single space.

Scan from 1 to N, and choose the numerator and denominator using this method. Since $N \le 1000$, $O(n^2)$ is acceptable.

Pay special attention to using multiplication to prevent division precision issues. The maximum value of 1000*1000 won't overflow an int.

#include <iostream>
using namespace std;

int n, a, b;


int main() {
    cin >> n >> a >> b;
    // The denominator must be less than or equal to n and less than a / b
    int mxi = -1, mxj = -1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            // j/i
            if (j*b < a *i) {
                if (mxi == -1 || mxj == -1 || j * mxi > mxj * i) mxj = j, mxi = i;
            }
        }
    }
    cout << mxj << " " << mxi << endl;
}

Stepping Squares

Stepping Squares

Total Time Limit: 1000ms Memory Limit: 65536kB Description

You are given a grid of squares. The grid's boundaries extend infinitely in all directions. We make the following assumptions: a. You can move only one step from the current square to an adjacent square; b. The square you step on collapses and cannot be stepped on again; c. You can only move north, east, and west;

The task: calculate how many different ways you can step on n squares given the above rules.

Input The number of steps n (n ≤ 20).

Output The number of different ways calculated.

One look and it's DP or DFS. Here it uses DFS and backtracking, which runs at most 20 * 3 times. An array of size 41 * 21 was used, starting from 20. This array is used to check if a position has been visited.

#include <iostream>

using namespace std;

int mat[42][21];
int res;
int n;

int dx[3] = {0, 1, 0};
int dy[3] = {-1, 0, 1};

void dfs(int x, int y, int u) {
    if (u == n) {
        res ++;
        return;
    }
    
    for (int i = 0; i < 3; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];

        if (mat[xx][yy]) continue;
        mat[xx][yy] = 1;
        dfs(xx, yy, u + 1);
        mat[xx][yy] = 0;
    }
}

int main() {
    cin >> n;
    mat[20][0] = 1;
    dfs(20, 0, 0);
    cout << res;
}

Nuclear Power Plant

D: Nuclear Power Plant

Total Time Limit: 5000ms Single Test Point Time Limit: 1000ms Memory Limit: 131072kB Description A nuclear power plant has N pits containing nuclear material, arranged in a straight line. If nuclear material is placed in M consecutive pits, an explosion will occur, so some pits might be left empty.

Task: For given N and M, find the total number of ways to place nuclear material without causing an explosion.

Input A single line with two positive integers N and M (1 < N < 50, $2 \le M \le 5$).

Output A single positive integer S, representing the total number of ways.

For $2 \le M \le 5$, the most difficult problem. Initially, it used a DFS with two states: placing or not placing at each position, ending up with $O(2^n)$ complexity, which is infeasible. However, it might still score a few points on a real test.

Instead, choose DP. Initially, a 2D DP was written, but the transition equation was unclear.

$f\[i]\[j]$ represents the number of valid ways up to position i, with j representing two states: placing at position i or not. For cases where i < m, simply add the ways; for i == m, subtract one invalid way of placing all m positions; for i > m, the invalid cases are clear: place nuclear materials in i-m+1 to i, leaving a free i-m position such that positions before i-m-1 can be placed in any manner. The number of invalid ways is 1 * f[i-m-1].

Also, take care of int overflow. Assuming no M constraint, there are 2^n possible ways. Since the constraint does not significantly reduce the number of ways, using long long is safest.

/* O(2^n) */

void dfs(int x, int u, int p) {
    // u current total placed
    // x current position
    // p current consecutive placed
    if (p >= m) return;

    if (x == n) {
        res ++;
        return;
    }

    dfs(x + 1, u, 0);  // do not place here
    dfs(x + 1, u + 1, p + 1);  // place here

    return;
}

long long f[55];

int main() {
    cin >> n >> m;

    // f[i][0/1] represents placing or not placing at position i (valid ways)
    // f[n][0] + f[n][1]
    // f[i][0] = f[i-1][0] + f[i-1][1]
    // f[i][1] = f[i-1][0] + f[i-1][1] - invalid ways
    
    // For i == m, simply subtract one way of placing all.
    // For i > m, we subtract ways placing in positions i-m+1 to i, leaving i-m with i-m-1 positions without constraints—handled by multiplication principle.

    f[0][0] = 1;
    for (int i = 1; i < m; i++) f[i][1] = f[i][0] = f[i-1][0] + f[i-1][1];
    for (int i = m; i <= n;) {
        f[i][0] = f[i-1][0] + f[i-1][1];
        f[i][1] = f[i-1][0] + f[i-1][1] - 1;
        break;
    }
    for (int i = m + 1; i <= n; i++) {
        f[i][0] = f[i-1][0] + f[i-1][1];
        f[i][1] = f[i-1][0] + f[i-1][1] - f[i-1-m][1] - f[i-1-m][0];
    }

    cout << f[n][0] + f[n][1];
}

Afterwards, it becomes clear that merging into a one-dimensional solution is more optimal.

long long f[55];

int main() {
    cin >> n >> m;	
	// Convert to a one-dimensional problem
    // f[i][1] + f[i][0] = 2*(f[i-1][0] + f[i-1][1]) - invalid ways

    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        f[i] = 2 * f[i-1];
        if (i == m) f[i] -= 1;
        if (i > m) f[i] -= f[i-1-m];
    }

    cout << f[n];
}

Highways

G: Highways Total Time Limit: 1000ms Memory Limit: 65536kB Description The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. As a result, traffic is difficult in Flatopia. The Flatopian government is planning to build some highways so that it will be possible to drive between any pair of towns without leaving the highway system.

Flatopian towns are numbered from 1 to N. Each highway connects exactly two towns and follows straight lines, usable in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town.

The government wants to minimize the length of the longest highway to be built, guaranteeing that every town is reachable from every other town.

Input The first line of input is an integer T, representing the number of test cases. For each test case, the first line is an integer N ($3 \le N \le 500$), representing the number of towns. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (an integer within [1, 65536]) between village i and village j. An empty line follows each test case.

Output For each test case, output an integer, representing the length of the longest road to be built such that all towns are connected, and this value is minimized.

Summarize the problem: find the minimum spanning tree such that the weight of its longest edge is minimized. This is effectively a minimum spanning tree problem with a greedy nature, which can be proven.

The understanding translates to a shortest-path minimum spanning tree problem. Use Prim or Kruskal algorithm.

Note: When reading input, change its self-weight to infinity (0x3f3f3f3f).

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int n;

void prim(vector<vector<int>>& mat) {
    vector<int> dist(mat.size(), 0x3f3f3f3f);
    vector<bool> st(mat.size(), false);

    dist[1] = 0;
    int res = INT_MIN;
    for (int i = 1; i < mat.size(); i++) {
        int v = -1;
        for (int j = 1; j < mat.size(); j++) if (!st[j] && (v == -1 || dist[j] < dist[v] )) v = j;

        st[v] = true;

        res = max(res, dist[v]);

        for (int j = 1; j < mat.size(); j++) {
            if (!st[j] && dist[j] > mat[v][j]) dist[j] = mat[v][j];
        }
    }

    cout << res << endl;
}

int main() {
    scanf("%d", &n);
    
    while (n--) {
        string tmp;
        getline(cin, tmp);
        int m;
        scanf("%d", &m);
        vector<vector<int>> mat(m + 1, vector<int>(m + 1));

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= m; j ++) {
                scanf("%d", &mat[i][j]);
                if (i == j) mat[i][j] = 0x3f3f3f3f;
            }
        }
        prim(mat);
    }
}

2023 Graduate On-site Test (5/15)

Finding Special Years

A: Finding Special Years

Checking submission statistics

Total Time Limit: 1000ms Memory Limit: 65535kB

Description

A year is a "special year" if the sum of its digits equals 20. For example, 2099, 1991, and 1892 are special years, whereas 2021 is not. Given a year, find the smallest special year strictly greater than the given year.

Input

Year: An integer y (1000≤y≤9000).

Output

Special year: The smallest special year strictly greater than y, such that the sum of its digits equals 20.

Unsure if there's a more sophisticated method. Initially done by incrementally searching, fearing TLE, so stored special years first and used binary search to find the first one greater.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> spe;

int getSum(int i) {
    int sum = 0;
    while (i) {
        sum += i % 10;
        i /= 10;
    }
    return sum;
}

void gen() {
    for (int i = 1000; i < 10000; i++) {
        if (getSum(i) == 20) spe.push_back(i);
    }
    sort(spe.begin(), spe.end());
}

int main() {
    gen();
    int n;
    while (cin >> n) {
        auto nxt = upper_bound(spe.begin(), spe.end(), n);
        cout << *nxt << endl;
    }
}

Image Blurring

B: Image Blurring

Checking submission statistics

Total Time Limit: 1000ms Memory Limit: 65536kB

Description

Given an image with n rows and m columns of pixel gray values, blur the image using the following method:

1. The gray values of the outermost pixels remain unchanged;
2. The new gray value of each internal pixel should be the average of its original value and the original values of the four adjacent pixels (rounded to the nearest integer).

Input

The first line contains two integers n and m, representing the number of rows and columns of the image. 1 ≤ n ≤ 100, 1 ≤ m ≤ 100.

The next n lines each contain m integers, representing the gray values of the pixels. Adjacent integers are separated by a single space. Each element is in the range 0 to 255.

Output

n lines, each containing m integers with the blurred image. Adjacent integers are separated by a single space.

Not complicated, directly implemented.

#include <iostream>
#include <vector>
using namespace std;


int n, m;
int mat[110][110];


int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &mat[i][j]);
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1 || i == n || j == 1 || j == m) {
                cout << mat[i][j];
                if (i == n && j == m) continue;
                if (j == m) cout << endl;
                else cout << " ";
                continue;
            }
            int sum = mat[i-1][j] + mat[i][j] + mat[i+1][j] + mat[i][j-1] + mat[i][j+1];
            cout << sum / 5 << " ";
        }
    }
}

Parentheses Generation

C: Parentheses Generation

Checking submission statistics

Total Time Limit: 1000ms Memory Limit: 65536kB

Description

Paul is a mathematics student who has taken a C++ programming course in his spare time. Now he can write programs to determine if a given string composed of '(' and ')' is correctly matched. However, he is not satisfied with this and wants to generate all possible valid parentheses combinations. Please help him solve this problem.

Input

A single integer N, representing the number of pairs of parentheses (1 ≤ N ≤ 10).

Output

Output all possible valid parentheses combinations in lexicographical order, with each combination on a new line.

DFS, ensure the number of left parentheses is greater than the number of right parentheses.

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<char> res;

void dfs(int l, int r,```cpp
            if (pos == m) {
                bsts = path;
                cout << steps << endl;
                cout << path << endl;
                break;
            }

            if (visited.count(pos)) continue;
            visited.insert(pos);

            // Jump to house 3*pos
            if (pos * 3 <= 1000) {
                q.push({pos * 3, steps + 1, path + "H"});
            }
            // Jump to house pos/2
            if (pos / 2 > 0) {
                q.push({pos / 2, steps + 1, path + "O"});
            }
        }
    }
    return 0;
}

D:公交旅行

D:公交旅行 总时间限制: 1000ms 内存限制: 65536kB 描述 There are n buses, bus i travels between city a_i and city b_i bi-directionally, you can take bus i no matter you are in city a_i or city b_i, and you will be transferred to city b_i or city ai (other passengers may be on the bus, in other words, bus is always accessible). Given an initial city starting point and target city ending point, determine whether you can reach the destination by taking the buses.

You may take as many buses as you like.

输入 The first line contains 3 integers n, starting_point, ending_point, 2≤n≤1000, 1≤starting_point, ending_point≤1000. Each of the next n lines contains 2 integers ai and bi (1≤ai, bi≤1000).

输出 Output YES if you can get to your destination, otherwise print NO.

同样的 BFS 思路，判断起点和终点是否连通。

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_set>

using namespace std;

int n, start, end;
vector<int> a, b;

int main() {
    cin >> n >> start >> end;
    a.resize(n);
    b.resize(n);

    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }

    queue<int> q;
    q.push(start);

    unordered_set<int> visited;

    while (!q.empty()) {
        int now = q.front();
        q.pop();

        if (visited.count(now)) continue;
        visited.insert(now);

        if (now == end) {
            cout << "YES" << endl;
            return 0;
        }

        for (int i = 0; i < n; i++) {
            if (a[i] == now && !visited.count(b[i])) {
                q.push(b[i]);
            }
            if (b[i] == now && !visited.count(a[i])) {
                q.push(a[i]);
            }
        }
    }

    cout << "NO" << endl;
    return 0;
}

E:Permutation Problem

E:Permutation Problem 总时间限制: 1000ms 内存限制: 65536kB 描述 In combinatorial mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order. For example, the permutations of {1,2,3} are listed as follows:

{1,2,3}
{1,3,2}
{2,1,3}
{2,3,1}
{3,1,2}
{3,2,1}

Given a permutation P of the first N natural numbers. Each permutation of these N numbers can be uniquely mapped to a number in the range [1, N!]. The task is to determine the number corresponding to this particular permutation.

输入 The first line contains an integer T representing the number of test cases.

Each of the T test cases consists of a single integer N followed by a permutation P of the first N natural numbers.

输出 For each case, print the corresponding number of the permutation P in the output.

Constraints 1 ≤ T ≤ 10^6 1 ≤ N ≤ 60 The numbers in the permutation will be distinct and in the range [1, N].

这个题目需要找出每个排列在字典顺序下的排名，可以用阶乘表示法处理。逐步计算每一位的排名，并利用剩余未使用的数更新排列。

#include <iostream>
#include <vector>

using namespace std;

long long factorial(int n) {
    if (n == 0) return 1;
    long long res = 1;
    for (int i = 1; i <= n; ++i) {
        res *= i;
    }
    return res;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        vector<int> P(N);
        vector<bool> used(N + 1, false);
        for (int i = 0; i < N; i++) {
            cin >> P[i];
        }

        long long rank = 1;
        long long fact = factorial(N - 1);
        for (int i = 0; i < N; ++i) {
            int count = 0;
            for (int j = 1; j < P[i]; ++j) {
                if (!used[j]) {
                    ++count;
                }
            }
            rank += count * fact;
            used[P[i]] = true;
            if (i < N - 1)
                fact /= (N - 1 - i);
        }
        cout << rank << endl;
    }
    return 0;
}

总结

这次题目虽然算法都比较简单，但每道题都涉及一定的模拟过程，要求对问题的建模和操作十分熟练。反复练习类似问题有助于提升相关能力。```cpp

查看提交统计提问

总时间限制: 1000ms 内存限制: 65536kB

描述

动物王国中，豺狼、老虎和狮子位于食物链的顶部，互为天敌。

现在我们用自然数1~N代表王国中的N种动物。

豺狼、老虎和狮子这三类顶级动物的关系如下：

1. 豺狼（我们用S1表示）吃老虎；
2. 老虎（我们用S2表示）吃狮子；
3. 狮子（我们用S3表示）吃豺狼。

现有两种关系 R1<=两者相同 R1<=两者相同 R2<=一个吃另一个 R2<=一个吃另一个

具体描述如下：

1. R1 (x y)， 表示种类x和y属于同一个食物链类别，相同表述的操作只有一个。
2. R2 (x y)， 表示种类x和种类y是天敌关系。 规定种类x y的大小关系时 T表情也是对应 T表情也是对应的。

问：在动物王国中，有多少个操作是正确的。

输入

第一行输入两个数 N K，分别代表动物的种类和关系的总数。

对于接下来的K行： 每行输入三个数 DK (d x y)，分别表示关系的类型，和相关的两个种类。

其中0 <= d <= 2, 1 <= x, y <= N

输出

输出一个数，表示题意里所求的正确操作数量。

样例输入

5 3 1 1 2 1 2 3 2 1 3

样例输出

2

重点在于使用并查集（Disjoint Set）来快速合并和查找集合关系，并通过对比大小关系和战胜关系两层并查集来记录食物链的特性。

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 50000 + 10;

int parent[MAXN * 3], rank[MAXN * 3];

void init(int n) {
    for (int i = 0; i < n * 3; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
}

int find(int x) {
    if (x != parent[x]) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            if (rank[rootX] == rank[rootY]) {
                rank[rootX]++;
            }
        }
    }
}

bool same(int x, int y) {
    return find(x) == find(y);
}

int main() {
    int N, K;
    cin >> N >> K;
    init(N);
    int cnt = 0;

    for (int i = 0; i < K; ++i) {
        int d, x, y;
        cin >> d >> x >> y;

        if (x < 1 || y < 1 || x > N || y > N || (d == 2 && x == y)) {
            cnt++;
            continue;
        }

        if (d == 1) {
            if (same(x, y + N) || same(x, y + 2 * N)) {
                cnt++;
            } else {
                unite(x, y);
                unite(x + N, y + N);
                unite(x + 2 * N, y + 2 * N);
            }
        } else {
            if (same(x, y) || same(x, y + 2 * N)) {
                cnt++;
            } else {
                unite(x, y + N);
                unite(x + N, y + 2 * N);
                unite(x + 2 * N, y);
            }
        }
    }

    cout << K - cnt << endl;
    return 0;
}

为了描述食物链中的敌对关系，我们将并查集视为三份并行集合：parent, parent + N, 和 parent + 2 * N，分别表示相同类别、被吃和吃的关系。根据输入来合并这些关系，最后计算正确的操作数量。> View Submission Stats & Questions

Total Time Limit: 1000ms Memory Limit: 65536kB

Description

In the animal kingdom, there are three types of animals A, B, and C. These three types of animals form an interesting circular food chain. A eats B, B eats C, and C eats A.

There are N animals, numbered from 1 to N. Each animal is one of A, B, or C, but we don't know exactly which type it is.

Someone describes the food chain relationships among these N animals using two types of statements:

The first type of statement is "1 X Y", indicating that X and Y are of the same kind.

The second type of statement is "2 X Y", indicating that X eats Y.

This person makes K statements about the N animals in the aforementioned manner. Among these K statements, some are true, and some are false. A statement is false if it meets any of the following three criteria:

1. The current statement contradicts some of the previous true statements.
2. The current statement involves X or Y greater than N.
3. The current statement indicates that X eats X.

Your task is to output the total number of false statements given N (1 ≤ N ≤ 50,000) and K statements (0 ≤ K ≤ 100,000).

Input

The first line contains two integers N and K, separated by a space.

The following K lines each contain three positive integers D, X, Y, separated by a space, where D indicates the type of statement.

If D=1, it indicates that X and Y are of the same kind.

If D=2, it indicates that X eats Y.

Output

A single integer indicating the number of false statements.

Solution: Use extended union-find data structure.

Summary

Today's problem set was challenging. Only solved one problem. The others required some form of search assistance :(

Spent around one and a half hours to solve 4 problems, then attended gym class.

2017 Summer Camp Programming Contest (5/23)

There were 10 problems in 2017, but the difficulty was relatively low. Solved 7 problems in 2.5 hours.

A: Count Prime Numbers

A: Count Prime Numbers

View Submission Stats & Questions

Total Time Limit: 1000ms Memory Limit: 65536kB

Description

Given two integers X and Y, output the count of prime numbers between them inclusive.

Input

Two integers X and Y (1 ≤ X,Y ≤ 105).

Output

Output an integer indicating the count of prime numbers between X and Y inclusive.

Prime checking up to the square root will suffice.

#include <iostream>
using namespace std;

int a, b;

bool isPrime(int i) {
    if (i == 1) return false;
    if (i == 2) return true;
    for (int k = 2; k <= i / k; k++) {
        if (i % k == 0) return false;
    }
    return true;
}

int main() {
    cin >> a >> b;
    int cnt = 0;
    for (int i = a; i <= b; i++) {
        cnt += isPrime(i);
    }

    cout << cnt << endl;
}

B: Encode String

B: Encode String (string)

View Submission Stats & Questions

Total Time Limit: 1000ms Memory Limit: 65536kB

Description

In data compression, a commonly used method is run-length encoding. For a given string to be compressed, we record each character and its repeated count in sequence. For example, given the string "aaabbbbcbb", the compressed result is (a,3)(b,4)(c,1)(b,2). This compression is effective when adjacent data has many repetitions; otherwise, efficiency is low.

You are required to encode the given string after converting all uppercase letters to lowercase.

Input

A string with a length greater than 0 and no more than 1000 characters, consisting of both uppercase and lowercase letters.

Output

Output the encoded string in the format: (a,3)(b,4)(c,1)(d,2), without any spaces.

Two pointers or sliding window

#include <iostream>
using namespace std;

int main() {
    string tmp;
    cin >> tmp;
    int l = 0, r = 0;
    char now = tmp[0];
    while (r < tmp.length()) {
        char ch = tmp[r] < 'a' ? tmp[r] - 'A' + 'a' : tmp[r];
        if (ch != now) {
            cout << "(" << now << "," << r - l << ")";
            now = ch;
            l = r;
        }
        else r++;
    }
    cout << "(" << now << "," << r - l << ")";
}

C: Island Perimeter

C: Island Perimeter (matrix)

View Submission Stats & Questions

Total Time Limit: 1000ms Memory Limit: 65536kB

Description

Use an nm 2D array to represent the map, where 1 represents land and 0 represents water. Each cell represents a 11 area. The grid can only be connected horizontally or vertically (not diagonally). The connected land forms an island, which is surrounded by water. There will be only one island in the given map, and there won't be any lakes (i.e., no water will be surrounded by land within the island). Calculate the perimeter of the island in the given 2D map.

Input

The first line contains n and m, indicating the size of the map (1≤n≤100, 1≤m≤100). The following n lines each contain m numbers, representing the value in each grid cell. Numbers are separated by spaces.

Output

Output a single line, the perimeter of the island (a positive integer).

BFS, default perimeter of an island is 4, reduce by 1 for each connected side

#include <iostream>
#include <vector>
using namespace std;

int n, m;
long long res;

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void bfs(vector<vector<int>>& mat, int x, int y) {
    mat[x][y] = 2;
    int o = 4;
    
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i], yy = y + dy[i];
        if (xx < 0 || xx >= n || yy < 0 || yy >= m) continue;

        if (mat[xx][yy] == 2 || mat[xx][yy] == 1) o--;
        if (mat[xx][yy] == 1) bfs(mat, xx, yy);
    }
    res += o;
}


int main() {
    cin >> n >> m;
    int x = -1, y = -1;
    vector<vector<int>> mat(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> mat[i][j];
            if (mat[i][j] == 1) x = i, y = j;
        }
    }
    if (x == -1 || y == -1) {
        cout << 0 << endl;
        return 0;
    }
    bfs(mat, x, y);
    cout << res << endl;
}

D: Safecracker

D: Safecracker

View Submission Stats & Questions

Total Time Limit: 1000ms Memory Limit: 65536kB

Description

"The item is locked in a Klein safe behind a painting in the second-floor library. Klein safes are extremely rare; most of them, along with Klein and his factory, were destroyed in World War II. Fortunately, old Brumbaugh from research knew Klein's secrets and wrote them down before he died. A Klein safe has two distinguishing features: a combination lock that uses letters instead of numbers, and an engraved quotation on the door. A Klein quotation always contains between five and twelve distinct uppercase letters, usually at the beginning of sentences, and mentions one or more numbers. Five of the uppercase letters form the combination that opens the safe. By combining the digits from all the numbers in the appropriate way, you get a numeric target. (The details of constructing the target number are classified.) To find the combination, you must select five letters v, w, x, y, and z that satisfy the following equation, where each letter is replaced by its ordinal position in the alphabet (A=1, B=2, ..., Z=26). The combination is then vwxyz. If there is more than one solution, the combination is the one that is lexicographically greatest, i.e., the one that would appear last in a dictionary."

v - w^2 + x^3 - y^4 + z^5 = target

"For example, given target 1 and letter set ABCDEFGHIJKL, one possible solution is FIECB, since 6 - 9^2 + 5^3 - 3^4 + 2^5 = 1. There are actually several solutions in this case, and the combination turns out to be LKEBA. Klein thought it was safe to encode the combination within the engraving because it could take months of effort to try all the possibilities even if you knew the secret. But of course, computers didn't exist then."

"Develop a program to find Klein combinations in preparation for field deployment. Use standard test methodology as per departmental regulations.

Input

Input consists of one or more lines containing a positive integer target less than twelve million, a space, then at least five and at most twelve distinct uppercase letters. The last line will contain a target of zero and the letters END; this signals the end of the input.

Output

For each line, output the unique Klein combination, or 'no solution' if there is no correct combination. Use the exact format shown below."

The idea is to brute force it, calculate every possible combination and sort once. Maximum 12^5, which should be acceptable.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> h(27);

int main() {
    for (int i = 1; i <= 26; i++) {
        int r = 1;
        for (int j = 0; j < 5; j++) {
            r *= i;
            h[i].push_back(r);
        }
    }

    int target;
    string str;

    while (true) {
        cin >> target >> str;
        if (target == 0 && str == "END") return 0;
        vector<int> nums;
        for (char c : str) {
            nums.push_back(c - 'A' + 1);
        }
        sort(nums.begin(), nums.end(), [](auto l, auto r) {
            return l > r;
        });

        int n = nums.size();
        for (int a = 0; a < n; a++) {
            for (int b = 0; b < n; b++) {
                if (a == b) continue;
                for (int c = 0; c < n; c++) {
                    if (a == c || b == c) continue;
                    for (int d = 0; d < n; d++) {
                        if (a == d || b == d || c == d) continue;
                        for (int e = 0; e < n; e++) {
                            if (a == e || b == e || c == e || d == e) continue;
                            if (h[nums[a]][0] - h[nums[b]][1] + h[nums[c]][2] - h[nums[d]][3] + h[nums[e]][4] == target) {
                                printf("%c%c%c%c%c\n", nums[a] + 'A' - 1, nums[b] + 'A' - 1, nums[c] + 'A' - 1, nums[d] + 'A' - 1, nums[e] + 'A' - 1);
                                goto find;
                            }
                        }
                    }
                }
            }
        }
        
        cout << "no solution" << endl;
        find:
        continue;
    }
}

E: Kaitou Kid's Glider

E: Kaitou Kid's Glider

View Submission Stats & Questions

Total Time Limit: 1000ms Memory Limit: 65536kB

Description

Kaitou Kid is a legendary thief who specializes in stealing jewels. His most outstanding feature is that he always manages to escape from Inspector Nakamori's tight surveillance, largely thanks to his handy glider.

One day, Kaitou Kid stole a precious diamond as usual, but Conan Edogawa saw through his disguise, and Conan's soccer ball destroyed the power unit of Kaitou Kid's glider. As a last resort, Kaitou Kid can only fly with a damaged glider to escape.

Suppose there are N buildings in a row in the city, and each building has a different height. Initially, Kaitou Kid can be on top of any building. He can choose to escape in one direction but cannot change direction midway (since Inspector Nakamori will be chasing from behind). Because the power unit of his glider is damaged, he can only glide downward (i.e., he can only glide from a higher building to a lower building). He hopes to pass over as many different buildings as possible to reduce the impact when descending and minimize injuries. What is the maximum number of different buildings he can fly over (including the initial building)?

Input

The first line of the input is an integer K (K < 100), representing the number of test cases.

Each test case contains two lines: the first line is an integer N (N < 100), representing the number of buildings. The second line contains N different integers, each representing the height h of a building (1 < h ≤ 10000), in the order of the buildings.

Output

For each test case, output a single line with an integer representing the maximum number of different buildings Kaitou Kid can fly over.

Longest decreasing subsequence (LDS). Note that he can fly both left to right and right to left.

#include <iostream>
#include <vector>
using namespace std;

int k;

int main() {
    cin >> k;
    while (k--) {
        int n;
        cin >> n;
        int res = 0;
        vector<int> height(n), f(n), ff(n);
        for (int i = 0; i < n; i++) {
            cin >> height[i];
        }
        for (int i = 0; i < n; i++) {
            f[i] = 1;
            for (int j = 0; j < i; j++) {
                if (height[j] > height[i]) f[i] = max(f[i], f[j] + 1);
            }
            res = max(res, f[i]);
        }
        for (int i = n - 1; i >= 0; i--) {
            ff[i] = 1;
            for (int j = n - 1; j > i; j--) {
                if (height[j] > height[i]) ff[i] = max(ff[i], ff[j] + 1);
            }
            res = max(res, ff[i]);
        }
        cout << res << endl;
    }
}

G: Implement Heap

G: Implement Heap

View Submission Stats & Questions

Total Time Limit: 3000ms Memory Limit: 65535kB

Description

Define an array initialized to be empty. Perform the following two operations on the array:

1. Add an element to the array.

2. Output and delete the smallest element in the array.

Implement an efficient algorithm to achieve the above functions using a heap structure.

Input

The first line contains an integer t, representing the number of test cases.

For each test case, the first line contains an integer n, representing the number of operations.

For each operation, first input an integer type.

When type=1, it represents the addition of an element, followed by an integer u, which is the element to be added.

When type=2, it represents the output and deletion of the smallest element in the array.

1≤n≤100000.

Output

Output the deleted number for each delete operation.

Implement a min-heap. Mainly the down and up functions will suffice. Use size to track the current number of elements.

#include <iostream>
#include <vector>

using namespace std;
int k;
int s;

void down(vector<int>& heap, int idx) {
    int t = idx;
    if (2 * idx <= s && heap[2 * idx] < heap[t]) t = 2 * idx;
    if (2 * idx + 1 <= s && heap[2 * idx + 1] < heap[t]) t = 2 * idx + 1;
    if (t != idx) {
        swap(heap[t], heap[idx]);
        down(heap, t);
    }
}

void up(vector<int>& heap, int idx) {
    while (idx / 2 > 0 && heap[idx / 2] > heap[idx]) {
        swap(heap[idx], heap[idx / 2]);
        idx /= 2;
    }
}

void insert(vector<int>& heap, int num) {
    s++;
    heap[s] = num;
    up(heap, s);
}

void printRemove(vector<int>& heap) {
    cout << heap[1] << endl;
    swap(heap[1], heap[s]);
    s--;
    down(heap, 1);
}

int main() {
    cin >> k;
    while (k--) {
        int n;
        s = 0;
        cin >> n;
        vector<int> heap(n + 1);
        int type;
        for (int i = 0; i < n; i++) {
            cin >> type;
            if (type == 1) {
                int num;
                cin >> num;
                insert(heap, num);
            }
            else if (type == 2) {
                printRemove(heap);
            }
        }
    }
}

H: Subway

H: Subway

View Submission Stats & Questions

Total Time Limit: 100```cpp ) { if (hash[i] == ans) { cout << i << endl; hash[i] = 0; } }

}

### C:垂直直方图

> C:Vertical Histogram
> View submission statistics ask question
> Total time limit: 1000ms Memory limit: 65536kB
> Description
> Input four lines of text all consisting of uppercase letters and output a vertical histogram showing the number of times each character appears in the text. Note: Only the number of occurrences of characters needs to be output, not those of whitespace, digits, or punctuation marks.
>
> Input
> The input comprises four lines of text composed of uppercase letters, with each line having no more than 80 characters.
> Output
> The output consists of several lines. The last line lists the 26 uppercase English letters, separated by a space. The preceding lines include spaces and asterisks, with each asterisk indicating the number of occurrences of the letter just above it. Note: The first line of the output cannot be blank.

Simple simulation

```cpp
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int n = 4;

int main() {
    vector<int> s(26, 0);
    int ans = 0;
    while (n --) {
        string tmp;
        getline(cin, tmp, '\n');
        for (auto c : tmp) {
            if (c >= 'A' && c <= 'Z') s[c-'A'] ++, ans = max(ans, s[c-'A']);
        }
    }

    do {
        for (auto c : s) {
            if (c >= ans) cout << "*";
            else cout << " ";
            cout << " ";
        }
        cout << endl;
    } while (--ans);

    for (int i = 0; i < 26; i++) {
        char ch = 'A' + i;
        cout << ch << (i == 25 ? "" : " ");
    }
}

D:Word-Search Wonder

D:Word-Search Wonder View submission statistics ask question Total time limit: 1000ms Memory limit: 65536kB Description The Pyrates Restaurant was starting to fill up as Valentine McKee walked in. She scanned the crowd for her sister, brother-in-law, and nephew. Seeing her sister waving from the far end of the restaurant, she made her way back to their booth. Hi, Valentine,'' her sister and brother-in-law, Niki and Dennis Chapman, greeted her. Hi, guys,'' she replied. ``What are you doing, Wade?'' she asked her nephew. He was busy working on one of the restaurant's activity sheets with a crayon.

I'm doing a word search game,'' Wade explained. I have to find all of these words in this big mess of letters. This is really hard.'' Wade looked intently at the paper in front of him.

``Can I help?'' asked Valentine, looking across the table at the activity sheet.

``Sure. These are the words we're looking for. They're the names of different kinds of Planes, Trains, and Automobiles.'' Input The first line of input will specify the length (in characters) of the sides of the letter matrix (the matrix of letters will be square). The length, l, will be in the range 1 ≤ l ≤ 100. The next l lines of input will be the matrix itself, each line will contain l uppercase letters.

A list of words will follow. Each word will be on a line by itself; there will be 100 or fewer words. Each word will be 100 or fewer characters long, and will only contain uppercase letters.

The final line of input will contain a single zero character. Output Your program should attempt to find each word from the word list in the puzzle. A word is found'' if all the characters in the word can be traced in a single (unidirectional) horizontal, vertical, or diagonal line in the letter matrix. Words may not wrap around'' rows or columns, but horizontal and diagonal words may proceed from right to left (``backwards''). For each word that is found, your program should print the coordinates of its first and last letters in the matrix on a single line, separated by a single space. Coordinates are pairs of comma-separated integers (indexed from 1), where the first integer specifies the row number and the second integer specifies the column number.

If a word is not found, the string ``Not found'' should be output instead of a pair of coordinates.

Each word from the input can be ``found'' at most once in the puzzle.

The task is to find how it appears, direction fixed, just traverse it. Here, I made it easier by storing the positions of all characters.

#include <iostream>
#include <vector>
using namespace std;

int n;
bool flag;

int dx[8] = {1, 1, 1, 0, 0, -1, -1, -1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

int main() {
    cin >> n;
    vector<vector<char>> mat(n + 1, vector<char>(n + 1));
    vector<vector<pair<int, int>>> hash(26);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> mat[i][j];
            hash[mat[i][j] - 'A'].push_back({i, j});
        }
    }
    string str;
    while (cin >> str) {
        if (str == "0") return 0;
        flag = false;

        for (auto &[x, y] : hash[str[0]-'A']) {
            if (flag) break;
            for (int i = 0; i < 8; i++) {
                if (flag) break;
                int xx = x, yy = y;
                for (int j = 1; j < str.size(); j++) {
                    xx = xx + dx[i], yy = yy + dy[i];
                    if (xx < 0 || xx >= n || yy < 0 || yy >= n) break;
                    if (mat[xx][yy] != str[j]) break;

                    if (j == str.size() - 1) {
                        cout << x+1 << "," << y+1 << " " << xx+1 << "," << yy+1 << endl;
                        flag = true;
                    }
                }
            }
        }
        if (!flag) cout << "Not found" << endl;

    }
}

E:A Mini Locomotive

E:A Mini Locomotive View submission statistics ask question Total time limit: 1000ms Memory limit: 65536kB Description A train has a locomotive that pulls the train with its many passenger coaches. If the locomotive breaks down, there is no way to pull the train. Therefore, the office of railroads decided to distribute three mini locomotives to each station. A mini locomotive can pull only a few passenger coaches. If a locomotive breaks down, three mini locomotives cannot pull all passenger coaches. So, the office of railroads made a decision as follows:

1. Set the number of maximum passenger coaches a mini locomotive can pull, and a mini locomotive will not pull over the number. The number is same for all three locomotives.
2. With three mini locomotives, let them transport the maximum number of passengers to destination. The office already knew the number of passengers in each passenger coach, and no passengers are allowed to move between coaches.
3. Each mini locomotive pulls consecutive passenger coaches. Right after the locomotive, passenger coaches have numbers starting from 1.

For example, assume there are 7 passenger coaches, and one mini locomotive can pull a maximum of 2 passenger coaches. The number of passengers in the passenger coaches, in order from 1 to 7, is 35, 40, 50, 10, 30, 45, and 60.

If three mini locomotives pull passenger coaches 1-2, 3-4, and 6-7, they can transport 240 passengers. In this example, three mini locomotives cannot transport more than 240 passengers.

Given the number of passenger coaches, the number of passengers in each passenger coach, and the maximum number of passenger coaches which can be pulled by a mini locomotive, write a program to find the maximum number of passengers which can be transported by the three mini locomotives. Input The first line of the input contains a single integer t (1 ≤ t ≤ 11), the number of test cases, followed by the input data for each test case. The input for each test case will be as follows: The first line of the input file contains the number of passenger coaches, which will not exceed 50,000. The second line contains a list of space separated integers giving the number of passengers in each coach, such that the ith number of in this line is the number of passengers in coach i. No coach holds more than 100 passengers. The third line contains the maximum number of passenger coaches which can be pulled by a single mini locomotive. This number will not exceed 1/3 of the number of passenger coaches. Output There should be one line per test case, containing the maximum number of passengers which can be transported by the three mini locomotives.

Dynamic programming concept. Initially, struggled to approach, later referring to GPT for simplifying.

#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;
    while (N--) {
        int n;
        cin >> n;
        vector<int> trains(n);
        vector<int> sums(n);
        int sum = 0;
        for (int i = 0; i < n; i++) {
            cin >> trains[i];
            sum += trains[i];
            sums[i] = sum;
        }
        int lim;
        cin >> lim;

        vector<int> ff(n, 0), fs(n, 0), ft(n, 0);
        // ff[i]: the maximum passengers first mini locomotive can pull till i
        for (int i = lim - 1; i < n; i++) {
            ff[i] = max(ff[i-1], sums[i] - sums[i-lim]);
        }

        for (int i = lim*2 - 1; i < n; i++) {
            fs[i] = max(fs[i-1], ff[i-lim] + sums[i] - sums[i-lim]);
        }

        for (int i = lim*3 - 1; i < n; i++) {
            ft[i] = max(ft[i-1], fs[i-lim] + sums[i] - sums[i-lim]);
        }

        cout << ft[n-1] << endl;
    }
}

2017 推免 (6/15)

A:因子分解

A:Prime Factorization View submission statistics ask question Total time limit: 1000ms Memory limit: 65536kB Description Input a number and output its prime factor decomposition expression.

Input Enter an integer n (2 ≤ n < 100). Output Output the factorization expression of the integer. The prime factors should be listed in ascending order. If the integer can be decomposed into the factor a to the power of b, if b is greater than 1, it is written as a^b; If b equals 1, just write a.

Simple problem. The tricky part is how to handle the first and last "*" symbol correctly.

10min

#include <iostream>
using namespace std;

int n;

int main() {
    cin >> n;
    bool flag = false;
    for (int i = 2; i <= n/i; i++) {
        if (n%i) continue;

        int s = 0;
        if (flag) cout << "*";
        cout << i;
        if (!flag) flag = true;
        while (!(n%i)) n/= i, s++;
        if (s != 1) cout << "^" << s;
    }
    if (n > 1) {
        if (flag) cout << "*";
        cout << n << endl;
    }
}

B:ISBN号码

B:ISBN Numbers View submission statistics ask question Total time limit: 1000ms Memory limit: 65536kB Description Every officially published book has an ISBN number corresponding to it. The ISBN code comprises 9 digits, a check digit, and 3 separators, and its standard format is like “x-xxx-xxxxx-x”, where the “-“ symbols are separators (hyphens), and the last digit is a check digit. For example, "0-670-82162-4" is a standard ISBN number. The first digit of the ISBN code represents the language of the book, e.g., 0 indicates English; the three digits following the first separator represent the publisher, e.g., 670 represents Viking Press; the five digits following the second separator represent the book's serial number assigned by the publisher; the last digit is the check digit.

The check digit is calculated as follows:

Multiply the first digit by 1, the second digit by 2, and so on, adding the result. Compute the result’s modulus 11; the remainder is taken as the check digit. If the remainder is 10, then the check digit is represented as the uppercase letter X. For example, the check digit 4 in the ISBN number "0-670-82162-4" is derived as follows: for the digits 067082162, multiply each digit respectively by 1, 2, ..., 9, sum the results, i.e., 0×1+6×2+...+2×9=158, then apply modulo 11 operation to the result, yielding 4 which becomes the check digit.

Your task is to implement a program to determine if the check digit in the input ISBN number is correct. If it is correct, output “Right”; otherwise, output the correct ISBN number with the proper check digit according to the given format.

Input The input consists of only one line, which is a character sequence representing an ISBN number (Guaranteed to conform to the format requirements of the ISBN number). Output Output one line, if the input ISBN number check digit is correct, then output "Right", otherwise output the correct ISBN number (including separators "-") according to the specified format.

Another straightforward task; the troublesome part is parsing the input.

10min

#include <cstdio>
#include <vector>
#include <iostream>
#include <string>
using namespace std;

int main() {
    string chs;
    string tmp;
    getline(cin, tmp, '\n');

    int idx = 0;
    for (char c : tmp) {
        if (c == '-') continue;
        chs[idx++] = c;
    }

     int sum = 0;
     for (int i = 0; i < 9; i++) {
        if (chs[i] == 'X' || chs[i] == 'x') sum += 10*(i+1);
        else sum += (chs[i] - '0')*(i+1);
        sum %= 11;
     }
     
     if (sum == chs[9] - '0' || (sum == 10 && (chs[9] == 'X' || chs[9] == 'x'))) cout << "Right" << endl;
     else {
        for (int i = 0; i < 9; i++) {
            cout << chs[i];
            if (i == 0 || i == 3 || i == 8) cout << '-';
        }
        char ch = (sum == 10 ? 'X' : sum+'0');
        cout << ch;
     }
}

C:肿瘤检测

C:Tumor Detection View submission statistics ask question Total time limit: 1000ms Memory limit: 65536kB Description A grayscale image of a CT scan can be described with an N*N (0 < N ≤ 100) matrix, with each cell in the matrix representing a grayscale value (integer) between 0 and 255. Assume the given image contains only one tumor. The tumor can be located on the image using the following method: if a point in the matrix has a grayscale value less than or equal to 50, then this point is considered to be on the tumor, otherwise it is not. By summing up the number of points on the tumor, we obtain the area of the tumor. Any point on the tumor is considered a boundary point of the tumor if it is a boundary point of the image or if at least one of its four adjacent points is not on the tumor. The number of boundary points of the tumor is defined as the perimeter of the tumor. Now, given an image, calculate the area and perimeter of the tumor in it.

Input The first line of the input contains a positive integer N (0 < N ≤ 100), representing the size of the image; the next N lines each contain one row of the image. Each row of the image is represented by N integers separated by a space. Output The output comprises one line containing two positive integers, representing the area and perimeter of the tumor, separated by a space.

A medium-difficulty task. Initially noted that the perimeter needs attention to edge cases.

Wrote it within 10 minutes, finalized and AC in a total of 40 minutes.

#include <iostream>
#include <vector>
using namespace std;

int n;
int cnt;
int total;

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1,  1};

bool checkBoard(vector<vector<int>> mat, int x, int y) {
    if (x < 0 || y < 0 || x >= n || y >= n || mat[x][y] > 50) return false;
    if (!x || x == n - 1 || !y || y == n - 1) return true;
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i], yy = y + dy[i];
        if (x < 0 || y < 0 || x >= n || y >= n) continue;
        if (mat[xx][yy] > 50) return true;
    }
    return false;
}

int main() {
    cin >> n;
    bool flag = false;
    int ii = 0, jj = 0;
    vector<vector<int>> mat(n, vectorThe first station ("Ekaterinburg") on the railway line to others. These distances are given as different positive integers and are arranged in ascending order. The distance from "Ekaterinburg" to "Sverdlovsk" does not exceed 10^9. The distance between any neighboring stations does not exceed L3. The minimal travel cost between two given stations will not exceed 10^9.
> Output
> Program should print to the output file the only number, which is the minimal travel cost between two given stations.

Obviously a dynamic programming (dp) problem, similar to the complete knapsack problem. For the ith station, its value is the minimum value transferred from the departure station (if it can be transferred).

```cpp
#include <iostream>
#include <vector>
using namespace std;

int l1, l2, l3, c1, c2, c3, n, p, q;

int main() {
    cin >> l1 >> l2 >> l3 >> c1 >> c2 >> c3;
    cin >> n;
    cin >> p >> q;
    
    if (p > q) swap(p, q);

    vector<int> f(n + 1, 0x3f3f3f3f);
    vector<int> d(n + 1);

    for (int i = 2; i <= n; i++) {
        cin >> d[i];
    }

    f[p] = 0;

    for (int i = p + 1; i <= q; i++) {
        for (int j = p; j < i; j++) {
            // cout << d[i] << " " << d[j] << " " << f[i] << " " << f[j] << endl;
            if (d[i] - d[j] <= l1) {
                f[i] = min(f[i], f[j] + c1);
            }
            else if (d[i] - d[j] <= l2) {
                f[i] = min(f[i], f[j] + c2);
            }
            else if (d[i] - d[j] <= l3) {
                f[i] = min(f[i], f[j] + c3);
            }
        }
    }
    cout << f[q];
}

F:Prime Path

F:Prime Path View Submission Statistics Total Time Limit: 1000ms Memory Limit: 65536kB Description

The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices. — It is a matter of security to change such things every now and then, to keep the enemy in the dark. — But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know! — I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door. — No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime! — I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds. — Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime.

Now, the minister of finance, who had been eavesdropping, intervened. — No unnecessary expenditure, please! I happen to know that the price of a digit is one pound. — Hmm, in that case I need a computer program to minimize the cost. You don't know some very cheap software gurus, do you? — In fact, I do. You see, there is this programming contest going on... Help the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above.

1033 1733 3733 3739 3779 8779 8179 The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.

Input One line with a positive number: the number of test cases (at most 100). Then for each test case, one line with two numbers separated by a blank. Both numbers are four-digit primes (without leading zeros). Output One line for each case, either with a number stating the minimal cost or containing the word Impossible.

BFS method, first create a list of prime numbers from 1000 to 9999, then use BFS to transfer, using a set to check if a number has been checked.

#include <string>
#include <vector>
#include <unordered_set>
#include <iostream>
#include <queue>
using namespace std;

int n;

int change(int num, int i, int j) {
    string s = to_string(num);
    s[i] = j + '0';
    return stoi(s);
}

bool isPrime(int x) {
    for (int i = 2; i*i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

void find_path(unordered_set<int>& primes, int p, int q) {
    queue<pair<int, int>> queue;
    unordered_set<int> st;
    queue.push({p, 0});
    st.insert(p);
    while (queue.size()) {
        auto& [num, cnt] = queue.front();
        queue.pop();
        if (num == q) {
            cout << cnt << endl;
            return;
        }
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 10; j++) {
                int new_num = change(num, i, j);
                if (!st.count(new_num) && primes.count(new_num)) {
                    queue.push({new_num, cnt+1});
                    st.insert(new_num);
                }
            }
        }
    }
}

int main() {
    unordered_set<int> primes;
    for (int i = 1000; i < 10000; i++) if (isPrime(i)) primes.insert(i);

    cin >> n;
    while (n--) {
        int p, q;
        cin >> p >> q;
        find_path(primes, p, q);
    }
}

A: Piecewise Function

A: Piecewise Function View Submission Statistics Total Time Limit: 1000ms Memory Limit: 65536kB Description Write a program to calculate the value of the following piecewise function y=f(x).

y=-x+2.5; 0 ≤ x < 5

y=2-1.5(x-3)(x-3); 5 ≤ x < 10

y=x/2-1.5; 10 ≤ x < 20

Input A floating point number N, 0 ≤ N < 20 Output Output the value of the piecewise function f(N). The result is printed to three decimal places.

I hope this year's sign-in question is also this simple.

#include <iomanip>
#include <iostream>
using namespace std;

/*
y=-x+2.5; 0 <= x < 5

y=2-1.5(x-3)(x-3); 5 <= x < 10

y=x/2-1.5; 10 <= x < 20
*/

int main() {
    double n, res;
    cin >> n;
    if (n < 5) res = -n + 2.5;
    else if (n < 10) res = 2 - 1.5 * (n - 3) * (n - 3);
    else res = n / 2 - 1.5;

    cout << fixed << setprecision(3) << res;
}

B: Word Reversal

B: Word Reversal View Submission Statistics Total Time Limit: 1000ms Memory Limit: 65536kB Description Input a sentence (one line), output the sentence with each word reversed.

Input One line, which is a string not exceeding 500 characters. Words are separated by spaces. Output Output the string with each word reversed. The spaces between words must be the same as in the original string.

Still a sign-in question, feel like it's quicker with Python.

a = str(input())

print(" ".join(i[::-1] for i in a.split(" ")))

C: Again and Again

C: Again and Again View Submission Statistics Total Time Limit: 1000ms Memory Limit: 65536kB Description Mo and Larry invented a way to encrypt information. They first decide on the number of columns, and then write the information (which only contains letters) vertically from top to bottom into these columns, and at the end they pad some random letters to make it a complete letter matrix. For example, if the information is "There's no place like home on a snowy night" and there are 5 columns, Mo would write:

t o i o y h p k n n e l e a i r a h s g e c o n h s e m o t n l e w x Note that Mo will only fill letters, and all will be in lowercase form. In this example, Mo filled the information with the letter "x" to make it a complete matrix, of course he can use any letter.

Mo rewrites the information based on this matrix: first writing the first row from left to right, then writing the second row from right to left, then writing the third row from left to right... and so on, alternating back and forth from top to bottom to form a new string. Thus, the information in the example is encrypted as: toioynnkpheleaigshareconhtomesnlewx.

Your task is to help Larry restore the original information from the encrypted information (including the padded letters).

Input The first line contains an integer (range 2 to 20), representing the number of columns used. The second line is a string not exceeding 200 characters. Output One line, which is the string representing the original information.

I feel like I wrote this in a very complicated way? Also used python

n = int(input())
s = str(input())

m = len(s) // n

res = [[0 for _ in range(n)] for _ in range(m)]

for i in range(len(s)):
    x = i // n
    y = i % n
    if x % 2 == 1:
        y = n - y - 1
    res[x][y] = s[i]

for i in range(n):
    for j in range(m):
        print(res[j][i], end='')

D: File Structure “Graph”

D: File Structure “Graph” View Submission Statistics Total Time Limit: 1000ms Memory Limit: 65536kB Description Displaying the structure of the file system on a computer is often useful. For example, the "explorer" program on Microsoft Windows shows this kind of information. But before graphical interfaces were available, there was no graphical representation. The best way to represent the directory and file structure was to display it in a "graph"-like format with indentation indicating the directory structure. For example:

ROOT | dir1 | file1 | file2 | file3 | dir2 | dir3 | file1 file1 file2 This graph indicates that the ROOT directory includes three subdirectories and two files. The first subdirectory includes 3 files, the second subdirectory is empty, and the third subdirectory includes one file.

Input Your task is to write a program to read some test data. Each set of test data represents the file structure of a computer. Each set of test data ends with a '*', and all reasonable input data ends with a line of three zeros. Each set of test data includes some file and directory names (although not given in the input, we always assume the ROOT directory is the outermost directory). In the input, the character ']' represents the end of a directory's content. Directory names start with 'd', file names start with 'f'. File names might have extensions or not (such as fmyfile.dat and fmyfile). File and directory names do not contain spaces, and the length does not exceed 30. The total number of subdirectories and files in a directory does not exceed 30. Output When displaying a directory's contents, first list its subdirectories (if any), and then list its files (if any). Files should be listed in alphabetical order by name (directories do not need to be listed in alphabetical order, just in the order they appear). Each set of test data should output "DATA SET x:", where x is the serial number of the test data (starting from 1). There should be an empty line between two sets of test data.

Note: We use one '|' and five spaces to indicate the indentation level.

Reminds me of compiler principles, haha.

At first I wanted to use a stack, but after thinking for a while and not figuring it out, I went back to recursion.

class Explorer:

    def __init__(self, name, l, father):
        self.father = father
        self.name = name
        self.level = l
        self.files = []
        self.dirs = []
    
    def add_file(self, file_name):
        self.files.append(file_name)
    
    def add_directory(self, direct_name):
        d = Explorer(direct_name, self.level + 1, self)
        self.dirs.append(d)
        return d
    
    def print(self):
        prefix = "|     " * self.level
        print(prefix + self.name)
        for d in self.dirs:
            d.print()
        self.files.sort()
        for f in self.files:
            print(prefix + f)

idx = 1
root = Explorer('ROOT', 0, None)
cur = root
while (tmp := input()) != '#':
    if tmp[0] == 'f': cur.add_file(tmp)
    if tmp[0] == 'd': cur = cur.add_directory(tmp)
    if tmp[0] == ']': cur = cur.father
    if tmp[0] == '*':
        print(f"DATA SET {idx}:")
        root.print()
        print()
        idx += 1
        root = Explorer('ROOT', 0, None)
        cur = root

F: Dungeon Master

F: Dungeon Master View Submission Statistics Total Time Limit: 1000ms Memory Limit: 65536kB Description You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It takes one minute to move one unit north, south, east, west, up or down. You cannot move diagonally and the maze is surrounded by solid rock on all sides.

Is an escape possible? If yes, how long will it take? Input The input consists of a number of dungeons. Each dungeon description starts with a line containing three integers L, R and C (all limited to 30 in size). L is the number of levels making up the dungeon. R and C are the number of rows and columns making up the plan of each level. Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a '#' and empty cells are represented by a '.'. Your starting position is indicated by 'S' and the exit by the letter 'E'. There's a single blank line after each level. Input is terminated by three zeroes for L, R and C. Output Each maze generates one line of output. If it is possible to reach the exit, print a line of the form Escaped in x minute(s).

where x is replaced by the shortest time it takes to escape. If it is not possible to escape, print the line Trapped!

Three-dimensional BFS, not difficult. The input is troublesome though.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int dk[6] = {0, 0, 0, 0, 1, -1};
int dx[6] = {-1, 1, 0, 0, 0, 0};
int dy[6] = {0, 0, -1, 1, 0, 0};

int main() {
    while (true) {
        int l, m, n;
        cin >> l >> m >> n; 
        if (!l && !m && !n) break;
        cin.ignore();

        vector<vector<vector<char>>> dungeons(l, vector<vector<char>>(m, vector<char>(n, '#')));
        vector<int> st = {-1, -1, -1, -1}, ed = {-2, -2, -2, -2};
        for (int k = 0; k < l; k++) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    char ch;
                    cin >> ch;
                    // cout << ch;
                    if (ch == 'S') st = {k, i, j, 0};
                    if (ch == 'E') ed = {k, i, j, 0}, dungeons[k][i][j] = '.';
                    if (ch == '.') dungeons[k][i][j] = ch;
                }
                cin.ignore();
            }
        }

        if (st[0] < 0 || ed[0] < 0) {
            cout << "Trapped" << endl;
            continue;
        }

        //  k, x, y, time;
        queue<vector<int>> q;
        // vector<vector<vector<bool>>> visited(l, vector<vector<bool>>(m, vector<bool>(n, false)));
        q.push(st);
        bool flag = false;
        while (!q.empty()) {
            auto node = q.front();
            q.pop();
            int k = node[0], x = node[1], y = node[2], t = node[3];
            if (k == ed[0] && x

:::info
This Content is generated by ChatGPT and might be wrong / incomplete, refer to Chinese version if you find something wrong.
:::

<!-- AI -->