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 choose for practice
- Preparation advice: Choose corresponding questions based on your preparation level
- Additional value: Can be used as preparation training for whitelist competitions
Day 14: GESP Level 1 2024.09_Xiao Yang Shopping
[Submit]
https://www.luogu.com.cn/problem/B4034
[Problem Description]
Xiao Yang has yuan for shopping. The unit price of product is yuan, and the unit price of product is yuan. Xiao Yang wants to buy the same quantity of product and product .
Please write a program to help Xiao Yang calculate how many products at most he can buy of product and product .
[Input Description]
The first line contains a positive integer , representing the amount of money Xiao Yang has for shopping.
The second line contains a positive integer , representing the unit price of product .
The third line contains a positive integer , representing the unit price of product .
[Output Description]
Output a line containing an integer, representing the maximum number of products that Xiao Yang can buy of product and product .
[Sample Input 1]
12
1
2
[Sample Output 1]
4
[Hint]
For sample 1, since he needs to buy the same quantity of both products, Xiao Yang can buy at most pieces of product and pieces of product , spending a total of yuan. Therefore, the answer for sample 1 is .
[Sample Input 2]
13
1
2
[Sample Output 2]
4
[Hint]
For sample 2, since he needs to buy the same quantity of both products, Xiao Yang can buy at most pieces of product and pieces of product , spending a total of yuan. If Xiao Yang wants to buy pieces of product and pieces of product , he would need to spend yuan, which exceeds Xiao Yang’s budget of yuan. Therefore, the answer for sample 2 is .
For all data, it is guaranteed that there is .
Reference Answer:
/*
* GESP Level 1 2024.09_Xiao Yang Shopping
* https://www.luogu.com.cn/problem/B4034
*/
#include <iostream>
using namespace std;
int main()
{
int n, a, b;
cin >> n >> a >> b;
cout << n / (a + b) << "\n";
return 0;
}
Day 14: GESP Level 2 2023.09_Xiao Yang’s X Matrix
[Submit]
https://www.luogu.com.cn/problem/B3865
[Problem Description]
Xiao Yang wants to construct an X matrix ( is odd), where both diagonals are half-width plus signs<span>+</span>, and the rest are half-width minus signs<span>-</span>. For example, an X matrix looks like this:
+---+
-+-+-
--+--
-+-+-
+---+
Please help Xiao Yang print the corresponding “ X matrix based on the given .
[Input Description]
A single integer ( guaranteed to be odd).
[Output Description]
Output the corresponding “ X matrix.
Please strictly follow the format requirements for output, do not add any extra spaces, punctuation, blank lines, or any other symbols. You should output exactly lines, each line should contain exactly characters, which are either<span>+</span> or<span>-</span>.
[Special Reminder]
In regular programs, providing prompts during input and output is a good habit. However, in this exam, due to system limitations, please do not include any prompt information in the input and output.
[Sample Input 1]
5
[Sample Output 1]
+---+
-+-+-
--+--
-+-+-
+---+
[Sample Input 2]
7
[Sample Output 2]
+-----+
-+---+-
--+-+--
---+---
--+-+--
-+---+-
+-----+
Reference Answer:
/*
* GESP Level 2 2023.09_Xiao Yang's X Matrix
* https://www.luogu.com.cn/problem/B3865
*/
#include <iostream>
using namespace std;
int main()
{
int N;
cin >> N;
for (int i = 0;i < N;i++)
{
for (int j = 0;j < N;j++)
{
if (j == i || j + i == N - 1)
cout << "+";
else
cout << "-";
}
cout << endl;
}
return 0;
}
Day 14: GESP Level 3 2025.03_2025
[Submit]
https://www.luogu.com.cn/problem/B4261
[Problem Description]
Xiao A has an integer , and he wants to find the smallest positive integer such that the following equation holds:
where represents the bitwise AND operation, represents the bitwise OR operation. If there is no satisfying , output .
[Input Description]
A single line, an integer .
[Output Description]
A single line, an integer. If a satisfying exists, output , otherwise output .
[Sample Input 1]
1025
[Sample Output 1]
1000
[Data Range]
For all test points, it is guaranteed that .
[Hint]
Where:
- represents bitwise AND operation, the operator is
<span>&</span>. - represents bitwise OR operation, the operator is
<span>|</span>.
Reference Answer:
For a certain bit, if <span>a</span> is 1 and <span>b</span> is 1, then <span>a & b</span> is 1, and <span>a | b</span> is 1, the sum of both is 2, while 1 + 1 = 2, which is equal. If <span>a</span>‘s bit is 1 and <span>b</span> is 0, then <span>a & b</span> is 0, and <span>a | b</span> is 1, so the total is 0 + 1 = 1, and 1 + 0 = 1, which is equal. Similarly, if both bits are 0, the sum is also 0. Therefore, the sum of each bit in both cases is exactly equal to the total sum of the binary bits of both numbers. Thus, the overall sum is indeed <span>x + y</span>.
Therefore, the original equation can be simplified to<span>x + y = 2025</span>. In other words, <span>y</span> equals<span>2025 - x</span>. So the problem reduces to finding the smallest positive integer<span>y</span>, which means if <span>2025 - x</span> is a positive integer and satisfies all conditions.
Method 1:
/*
* [GESP202503 Level 3] 2025
* https://www.luogu.com.cn/problem/B4261
*/
#include <iostream>
using namespace std;
int main()
{
int x;
cin >> x;
for (int y = 1;y <= 2025;y++)
{
if ((x && y) + (x | y) == 2025)
{
cout << y;
return 0;
}
}
cout << -1;
return 0;
}
Method 2:
/*
* [GESP202503 Level 3] 2025
* https://www.luogu.com.cn/problem/B4261
*/
#include <iostream>
using namespace std;
int main()
{
int x;
cin >> x;
cout << 2025 - x;
return 0;
}
Day 14: GESP Level 4 2024.12_Character Sorting
[Submit]
https://www.luogu.com.cn/problem/B4069
[Problem Description]
Xiao Yang has strings consisting only of lowercase letters, and he wants to arrange these strings in a certain order and concatenate them to form a string . Xiao Yang hopes that the final string meets:
- Assuming is the th character of the string, for all , it holds that . The size relationship between two characters is consistent with their order in the alphabet, for example, .
Xiao Yang wants to know if there exists a satisfying arrangement order of the strings.
[Input Description]
The first line contains a positive integer , representing the number of test data sets.
For each test data set, the first line contains a positive integer , meaning as described in the problem statement.
Then lines, each containing a string .
[Output Description]
For each test data set, if there exists a satisfying arrangement order, output 1, otherwise output 0.
[Sample Input 1]
3
3
aa
ac
de
2
aac
bc
1
gesp
[Sample Output 1]
1
0
0
[Sample Explanation]
For the first test data set, one possible arrangement order is aa+ac+de, resulting in the string aaacde, which satisfies the condition.
[Data Range]
For all data, it is guaranteed that , each string’s length does not exceed .
Reference Answer:
/*
* GESP Level 4 2024.12_Character Sorting
* https://www.luogu.com.cn/problem/B4069
*/
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<string> lst;// List to store strings
int T;// Number of test data sets
cin >> T;
for (int i = 0;i < T;i++)
{
lst.clear();// Clear the list
int n;// Number of lowercase letter strings
cin >> n;
for (int j = 0;j < n;j++)
{
string str;
cin >> str;
lst.push_back(str);
}
// Sort the strings
sort(lst.begin(), lst.end());
// Concatenate the strings
string result = "";
for (int j = 0;j < n;j++)
{
result += lst[j];
}
// Check if it meets the condition
int k = 1;
for (int j = 1;j < result.size();j++)
{
if (result[j] < result[j - 1])
{
k = 0;
break;
}
}
cout << k << endl;
}
return 0;
}
Day 14: Openjudge 1.11.05_Pie
[Submit]
http://noi.openjudge.cn/ch0111/05/
[Description]
My birthday is coming! According to tradition, I need to distribute some pies to everyone. I have pies of different flavors and sizes. friends will come to my party, and each person will receive a piece of pie (it must be a piece from one pie, not a combination of pieces from several pies; it can be a whole pie).
My friends are very stingy, and if someone gets a larger piece, they will start complaining. Therefore, everyone must receive pieces of the same size (but they do not need to be the same shape), although some pies may be wasted, it is better than ruining the whole party. Of course, I also need to keep a piece for myself, and that piece must also be the same size as the others.
What is the maximum size of the pie each person can get? Each pie is a cylinder with a height of 1 and varying radii.
[Input]
The first line contains two positive integers and , representing the number of pies and the number of friends.
The second line contains integers between 1 and 10000, representing the radius of each pie.
[Output]
Output the maximum volume of pie each person can receive, accurate to three decimal places.
[Sample Input]
3 3
4 3 3
[Sample Output]
25.133
[Reference Program]
Idea: First, create an array to store the volumes of each pie, then use the largest pie for binary search; then check each pie’s volume to see if it meets the requirements. If it meets, continue in the right interval; if not, continue in the left interval.
/*
* 05: Pie
* http://noi.openjudge.cn/ch0111/05/
*/
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
const int maxn = 10000 + 10;
const double PI = acos(-1.0); // Use PI
double arr[maxn];
int N, F;
bool func(double x)
{
int cnt = 0;
for (int i = 0;i < N;i++)
{
cnt += int(arr[i] / x); // Calculate how many pieces of mid volume can be cut from each pie;
}
return cnt >= F + 1; // F + 1 for myself
}
int main()
{
cin >> N >> F;
double L = 0, R = 0;
for (int i = 0;i < N;i++)
{
int x;
cin >> x;
arr[i] = PI * x * x;
R = max(arr[i], R); // Get the maximum volume pie;
}
double mid;
while (R - L > 1e-5) // Binary search precision
{
mid = (L + R) / 2; // Start binary search
if (func(mid) == true)
{
L = mid;
}
else
{
R = mid;
}
}
cout << fixed << setprecision(3) << mid;
return 0;
}
Day 14: 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 , for node , its left child’s number is , and its right child’s number is .
Xiao Yang will start moving from node in the binary tree, and each move can be any of the following three types:
- Type 1 Move: If the current node has a parent node, move up to the current node’s parent; otherwise, do not move;
- Type 2 Move: Move to the current node’s left child;
- Type 3 Move: Move to the current node’s right child.
Xiao Yang wants to know the node number he is at after moves.It is guaranteed that the final node number does not exceed .
[Input Description]
The first line contains two positive integers , representing the number of moves and the initial node number.
The second line contains a string of length containing only uppercase letters, representing the type of each move, where represents Type 1 Move, represents Type 2 Move, and 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 route is 2-1-3-7.
[Data Range]
| Subtask Number | Data Point Proportion |
|---|---|
| 1 | 20% |
| 2 | 20% |
| 3 | 60% |
For all data, it is guaranteed that .
Reference Answer:
/*
* [GESP Level 6 2024.12] 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, 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 odd layer node count, cnt2 even layer node count
queue<pair<int, int>> q;// Queue for breadth search
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
“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, Ministry of Education whitelist competition coaching, and youth programming team competitions.
