Learn programming with Lao Ma by “leveling up and fighting monsters”!
- Involves examination: Computer Society Programming Ability Level Certification (GESP)
- Event content: Provides real exam questions of different levels for students to practice
- Preparation advice: Choose corresponding questions based on your preparation level
- Additional value: Can be used as preparation training for whitelist competitions
Day 13: GESP Level 1 2024.12_Temperature Conversion
[Submit]
https://www.luogu.com.cn/problem/B4062
[Problem Description]
Recently, Xiao Yang learned about the conversion between Kelvin, Celsius, and Fahrenheit temperatures. Let the symbol K represent the Kelvin temperature, the symbol C represent the Celsius temperature, and the symbol F represent the Fahrenheit temperature. The conversion formulas among these three are as follows:
Now, Xiao Yang wants to write a program to calculate the Celsius and Fahrenheit temperatures corresponding to a given Kelvin temperature. Can you help him?
[Input Description]
A single line containing a real number K, representing the Kelvin temperature.
[Output Description]
A single line. If the corresponding Fahrenheit temperature for the input Kelvin temperature is greater than 212, output <span>Temperature is too high!</span>;
Otherwise, output two real numbers separated by a space: C and F, representing the Celsius and Fahrenheit temperatures, rounded to two decimal places.
[Sample Input 1]
412.00
[Sample Output 1]
Temperature is too high!
[Sample Input 2]
173.56
[Sample Output 2]
-99.59 -147.26
[Data Range]
Reference Answer:
/*
* [GESP202412 Level 1] Temperature Conversion
* https://www.luogu.com.cn/problem/B4062
*/
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
double K;
cin >> K;
double C = K - 273.15;//Celsius temperature
double F = C * 1.8 + 32;//Fahrenheit temperature
if (F > 212)
{
cout << "Temperature is too high!";
}
else
{
cout <<fixed<<setprecision(2)<< C << " " << F;
}
return 0;
}
Day 13: GESP Level 2 2023.06_Armstrong Number Check
[Submit]
https://www.luogu.com.cn/problem/B3841
[Problem Description]
An Armstrong number is a number of n digits that is equal to the sum of its own digits each raised to the power of n. For example, 153 is a 3-digit number, and the sum of its digits raised to the 3rd power is 153, so 153 is an Armstrong number; 1634 is a 4-digit number, and the sum of its digits raised to the 4th power is 1634, so 1634 is also an Armstrong number.
Now, given several positive integers, please determine whether they are Armstrong numbers.
[Input Description]
The first line contains a positive integer m, indicating the number of positive integers to check. It is guaranteed that m is less than or equal to 100.
From the second line onwards, each line contains one positive integer to check. It is guaranteed that these positive integers are all less than 10^9.
[Output Description]
For each positive integer checked, output a line. If the corresponding positive integer is an Armstrong number, output the uppercase letter ‘T’; otherwise, output the uppercase letter ‘F’.
Note: You do not need to wait until all inputs are finished to output; you can check one number and output it before moving on to the next number.
[Sample Input 1]
3
152
111
153
[Sample Output 1]
F
F
T
[Sample Input 2]
5
8208
548834
88593477
12345
5432
[Sample Output 2]
T
T
T
F
F
Reference Answer:
/*
* Armstrong Number Check
* https://www.luogu.com.cn/problem/B3841
*/
#include <iostream>
using namespace std;
int main()
{
int m = 0;
cin >> m;
for (int i = 0; i < m; i++)
{
int n = 0;
cin >> n;
// Count the number of digits in n, denoted as l
int t = n, l = 0;
while (t > 0)
{
t /= 10;
l++;
}
// Calculate the sum of each digit raised to the l-th power, denoted as sum
int sum = 0;
t = n;
while (t > 0)
{
int d = t % 10;
t /= 10;
int mul = 1;
for (int j = 0; j < l; j++)
mul *= d;
sum += mul;
}
// Check if sum equals n to determine if it is an Armstrong number
if (sum == n)
cout << "T" << endl;
else
cout << "F" << endl;
}
return 0;
}
Day 13: GESP Level 3 2024.06_Finding Multiples
[Submit]
https://www.luogu.com.cn/problem/B4004
[Problem Description]
Xiao Yang has a sequence of n positive integers, and he wants to know if there exists a number x such that x is a multiple of all numbers in the sequence.
[Input Description]
The first line contains a positive integer t, representing the number of test cases.
Each test case consists of two lines. The first line contains a positive integer n; the second line contains n positive integers representing the sequence.
[Output Description]
For each test case, if there exists a number x such that x is a multiple of all n numbers, output Yes; otherwise, output No.
[Sample Input 1]
2
3
1 2 4
5
1 2 3 4 5
[Sample Output 1]
Yes
No
[Sample Explanation]
For the first test case, there exists a number that is a multiple of both 1 and 2.
[Data Range]
Reference Answer:
/*
* GESP: 2024.06 Level 3 Finding Multiples
* https://www.luogu.com.cn/problem/B4004
*/
#include <iostream>
using namespace std;
int main()
{
int t, n, j;
cin >> t;
int A[100005] = { 0 };
for (int i = 0;i < t;i++)
{
int max_v = 0;
cin >> n;
for (j = 0;j < n;j++)
{
cin >> A[j];
if (A[j] > max_v)
{
max_v = A[j];
}
}
for (j = 0;j < n;j++)
{
if (max_v % A[j] != 0)
{
break;
}
}
if (j == n)
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
}
return 0;
}
Day 13: GESP Level 4 2025.03_Land Reclamation
[Submit]
https://www.luogu.com.cn/problem/B4263
[Problem Description]
Xiao Yang has a large piece of wasteland, which can be represented as a grid of n rows and m columns.
Xiao Yang wants to reclaim this wasteland, but some positions in the wasteland contain debris. A piece of wasteland can be reclaimed if and only if all four adjacent cells (up, down, left, right) do not contain debris.
Xiao Yang can choose to clear at most one position of debris, turning that position into wasteland. Xiao Yang wants to know the maximum number of pieces of wasteland that can be reclaimed by clearing at most one position of debris.
[Input Description]
The first line contains two positive integers n and m, as described in the problem statement.
The next n lines each contain a string of length m consisting only of characters <span>.</span> and <span>#</span>. A ‘.’ represents a piece of wasteland, while a ‘#’ represents a piece of debris.
[Output Description]
Output an integer representing the maximum number of pieces of wasteland that can be reclaimed by clearing at most one position of debris.
[Sample Input 1]
3 5
.....
.#..#
.....
[Sample Output 1]
11
[Sample Explanation]
After removing the debris from the second row, second column, the grid becomes:
.....
....#
.....
In the first row, there are 5 pieces of wasteland, in the second row, there are 4 pieces of wasteland, and in the third row, there are 5 pieces of wasteland, totaling 11 pieces of wasteland that can be reclaimed.
[Data Range]
Reference Answer:
/*
* [GESP202503 Level 4] Land Reclamation
* https://www.luogu.com.cn/problem/B4263
*/
# include <iostream>
using namespace std;
char arr[1005][1005];
int n, m;
int check(int i, int j)
{
if (i<1 || i>n || j<1 || j>m)
return 0;
if (arr[i][j] == '.')
{
if (arr[i - 1][j] != '#' && arr[i + 1][j] != '#' && arr[i][j - 1] != '#' && arr[i][j + 1] != '#')
{
return 1;
}
}
return 0;
}
int main()
{
cin >> n >> m;
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= m;j++)
{
cin >> arr[i][j];
}
}
int cnt = 0;// Count of reclaimable wasteland
int max_ = 0;// Maximum increase in reclaimable wasteland
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= m;j++)
{
if (arr[i][j] == '.')
{
cnt += check(i, j);
}
else
{
arr[i][j] = '.';
int temp = check(i, j);
temp += check(i - 1, j);
temp += check(i + 1, j);
temp += check(i, j - 1);
temp += check(i, j + 1);
if (temp > max_)
{
max_ = temp;
}
arr[i][j] = '#';
}
}
}
cout << cnt + max_;
return 0;
}
Day 13: Openjudge 1.11.10_Hopping Stones in the River
[Submit]
http://noi.openjudge.cn/ch0111/10/
[Description]
Every year, cows hold various special versions of hopping stone competitions, including jumping from one rock to another in the river. This exciting activity takes place in a long straight river, with a rock at the starting point and another rock at the endpoint, which is a distance l away from the starting point. Between the starting point and the endpoint, there are n rocks, each with a distance from the starting point of d_i.
During the competition, cows take turns starting from the starting point, trying to reach the endpoint, with each jump only allowed from one rock to another. Of course, cows that are not strong enough cannot achieve the goal.
Farmer John is proud of his cows and has watched this competition every year. However, over time, he has become very annoyed watching other farmers’ timid cows slowly moving between closely spaced rocks. He plans to remove some rocks so that the longest possible shortest jump distance is maximized during the journey from the starting point to the endpoint. He can remove at most m rocks, excluding the starting and ending points.
Please help John determine the longest possible shortest jump distance after removing these rocks.
[Input]
The first line contains three integers l, n, and m, separated by a single space.
The next n lines each contain an integer representing the distance of each rock from the starting point. The rocks are given in order of increasing distance from the starting point, and no two rocks are at the same position.
[Output]
An integer representing the longest possible shortest jump distance.
[Sample Input]
25 5 2
2
11
14
17
21
[Sample Output]
4
[Hint]
After removing the rocks at positions 2 and 14, the shortest jump distance is 4 (from 17 to 21 or from 21 to 25).
[Reference Program]
The problem is to find the longest possible shortest distance among all possible arrangements of rocks after removing up to m rocks, leaving n – m + 2 rocks, which will divide the entire segment into n – m + 1 segments. The minimum distance between points must be at least x.
To check if a certain distance is possible, we can use binary search:
Let mid = (l + r) / 2;
- If it satisfies the condition, we should look for a larger distance, so take the right half, l = mid + 1;
- If it does not satisfy the condition, we should look for a smaller distance, so take the left half, r = mid – 1;
The final result will be the maximum of the minimum distances among all arrangements.
/*
* 10: Hopping Stones in the River
* http://noi.openjudge.cn/ch0111/10/
*/
#include <iostream>
using namespace std;
const int N = 50005;
int arr[N];
int l, n, m;
bool check(int x)
{
int t = 0, num = 0;//t: current observation point
for (int i = 1; i <= n; i++)
{
if (arr[i] - t < x)
{
num++;
}
else
{
// If the distance from point i to the current observation point is greater than or equal to x, update the observation point
t = arr[i];
}
}
if (l - t < x)
{
// If the distance from the observation point to the endpoint is less than x, remove the observation point
num++;
}
// Check if the number of removed points is less than or equal to m
return num <= m;
}
int main()
{
cin >> l >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> arr[i];
}
int le = 0, ri = l, mid;
while (le + 1 < ri)
{
mid = (le + ri) / 2;
if (check(mid))
{
le = mid;
}
else
{
ri = mid;
}
}
cout << le;
return 0;
}
Day 13: GESP Level 6 2024.12_Walking on Trees
[Submit]
https://www.luogu.com.cn/problem/P11375
[Problem Description]
Xiao Yang has a binary tree with infinite nodes (i.e., each node has a left child and a right child; except for the root node, each node has a parent node), where the root node is numbered 1, and for node i, its left child’s number is 2*i and its right child’s number is 2*i + 1.
Xiao Yang will start moving from node k in the binary tree, and each move can be one of the following three types:
- Type 1 Move: If the current node has a parent node, move up to the parent node; otherwise, do not move;
- Type 2 Move: Move to the left child of the current node;
- Type 3 Move: Move to the right child of the current node.
Xiao Yang wants to know the node number he will be at after m moves.
[Input Description]
The first line contains two positive integers m and k, representing the number of moves and the initial node number.
The second line contains a string of length m consisting only of uppercase letters, representing the type of each move, where U represents Type 1 Move, L represents Type 2 Move, and R represents Type 3 Move.
[Output Description]
Output a positive integer representing the final node number.
[Sample Input 1]
3 2
URR
[Sample Output 1]
7
[Sample Explanation]
Xiao Yang’s movement path is 2-1-3-7.
[Data Range]
Reference Answer:
/*
* [GESP202412 Level 6] Walking on Trees
* https://www.luogu.com.cn/problem/P11375
*/
#include <iostream>
#include <utility>
#include <queue>
#include <vector>
using namespace std;
int main()
{
int n;
cin >> n;
// Store the tree as an adjacency list
vector<vector<int>> tree(n + 1);
for (int i = 1;i < n;i++)
{
int u, v;
cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u);
}
// Breadth-first search
vector<bool> visited(n + 1, false);// Indicates whether visited
vector<int> layer(n + 1);// Indicates the layer
int cnt1 = 0, cnt2 = 0;// cnt1: number of nodes in odd layers, cnt2: number of nodes in even layers
queue<pair<int, int>> q;// Queue for BFS
q.push({ 1,1 });
while (q.empty() == false)
{
int u = q.front().first;
int s = q.front().second;
q.pop();
visited[u] = true;
layer[u] = s;
if (s % 2 == 0)
cnt2++;
else
cnt1++;
vector<int> temp = tree[u];
for (int i = 0;i < temp.size();i++)
{
if (visited[temp[i]] == false)
{
q.push({ temp[i],s + 1 });
}
}
}
for (int i = 1;i <= n;i++)
{
if (layer[i] % 2 == 0)
{
cout << cnt2 << " ";
}
else
{
cout << cnt1 << " ";
}
}
return 0;
}
Youth Programming Competition Exchange
The “Youth Programming Competition Exchange Group” has been established (suitable for youth aged 6 to 18). Add the assistant’s WeChat to invite everyone into the learning group. After joining the group, everyone can participate in regularly organized 21-day problem-solving check-ins, level exam assessments, guidance for Ministry of Education whitelist competitions, and youth programming team competitions.
