Learn programming with Lao Ma by “leveling up and fighting monsters”!
- Involves examination: Computer Society Programming Ability Level Certification (GESP)
- Activity 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 16: Openjudge1.3.02_Calculate the Value of an Expression
[Submit]
http://noi.openjudge.cn/ch0103/02/
[Description]
Given three integers,,, calculate the value of the expression.
[Input]
The input consists of a single line containing three integers,,, separated by a single space..
[Output]
Output a single line, which is the value of the expression.
[Sample Input]
2 3 5
[Sample Output]
25
[Reference Program]
C Language Version
/*
* 02: Calculate (a+b)*c
* http://noi.openjudge.cn/ch0103/02/
*/
# include<cstdio>
int main()
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
printf("%d", (a + b) * c);
return 0;
}
C++ Language Version
/*
* 02: Calculate (a+b)*c
* http://noi.openjudge.cn/ch0103/02/
*/
#include <iostream>
using namespace std;
int main()
{
int a, b, c;
cin >> a >> b >> c;
cout << (a + b) * c;
return 0;
}
Day 16: GESP Level 2 2024.12_Digit Sum
[Submit]
https://www.luogu.com.cn/problem/B4065
[Problem Description]
Little Yang has positive integers, and he wants to know the maximum digit sum among these positive integers.
“Digit sum” refers to the sum of all digits in a number.
For example:
For the number , its digits are ,,,,. Adding these digits gives:
Thus, the digit sum of is .
[Input Description]
The first line contains a positive integer , representing the number of positive integers.
Next lines, each containing a positive integer.
[Output Description]
Output the maximum digit sum of these positive integers.
[Sample Input 1]
3
16
81
10
[Sample Output 1]
9
[Data Range]
For all data, it is guaranteed that there are , and each positive integer does not exceed .
Reference Answer:
/*
* [GESP202412 Level 2] Digit Sum
* https://www.luogu.com.cn/problem/B4065
*/
#include <iostream>
using namespace std;
int main()
{
int n, max_ = 0;
cin >> n;
for (int i = 0;i < n;i++)
{
long long x;
cin >> x;
int sum = 0;
while (x > 0)
{
sum += x % 10;
x = x / 10;
}
if (sum > max_)
{
max_ = sum;
}
}
cout << max_;
return 0;
}
Day 16: GESP Level 3 2024.09_Balanced Sequence
[Submit]
https://www.luogu.com.cn/problem/B4038
[Problem Description]
Little Yang has a sequence of positive integers, and he believes a sequence is balanced if there exists a positive integer () such that the sum of the numbers from the th to the th number equals the sum of the numbers from the th to the th number.
Little Yang wants you to determine whether the sequence is balanced.
[Input Description]
The first line contains a positive integer , representing the number of test cases.
Next are groups of test cases. For each group, there are two lines.
The first line contains a positive integer , representing the length of the sequence.
The second line contains positive integers, representing the sequence.
[Output Description]
For each group of test cases, if the sequence is balanced, output Yes; otherwise, output No.
[Sample Input 1]
3
3
1 2 3
4
2 3 1 4
5
1 2 3 4 5
[Sample Output 1]
Yes
Yes
No
[Hint]
- For the first test case, let , then , so the sequence is balanced;
- For the second test case, let , then , so the sequence is balanced;
- For the third test case, there is no that satisfies the requirement.
For all data, it is guaranteed that there are .
Reference Answer:
/*
* GESP Level 3: 2024.09 Balanced Sequence
* https://www.luogu.com.cn/problem/B4038
*/
#include <iostream>
using namespace std;
int main()
{
int arr[10005] = { 0 };
int t; // t represents the number of test cases
cin >> t;
for (int i = 0;i < t;i++)
{
int n; // n represents the length of the sequence
cin >> n;
int total = 0, k = 0;
for (int i = 0;i < n;i++)
{
cin >> arr[i];
total += arr[i];
}
for (int j = 0;j < n;j++)
{
k += arr[j];
if (k * 2 == total)
{
cout << "Yes" << endl;
break;
}
}
if (k == total)
{
cout << "No" << endl;
}
}
return 0;
}
Day 16: GESP Level 4 2024.06_Black and White Squares
[Submit]
https://www.luogu.com.cn/problem/B4005
[Problem Description]
Little Yang has a grid of rows and columns, where each cell is either white or black.
For a subrectangle in the grid, Little Yang considers it balanced if the number of black cells equals the number of white cells.
Little Yang wants to know the maximum number of cells in a balanced subrectangle.
[Input Description]
The first line contains two positive integers , as described in the problem statement.
Next lines, each containing a string of length , representing the color of the cells in the grid. If it is , the cell is white; otherwise, it is black.
[Output Description]
Output an integer representing the number of cells in the largest balanced subrectangle; if none exists, output .
[Sample Input 1]
4 5
00000
01111
00011
00011
[Sample Output 1]
16
[Sample Explanation]
For Sample 1, assuming () represents the cell at row and column , the four vertices of the largest balanced subrectangle are ,,,.
[Data Range]
For all data, it is guaranteed that there are .
Reference Answer:
/*
* [GESP202406 Level 4] Black and White Squares
* https://www.luogu.com.cn/problem/B4005
*/
#include <iostream>
using namespace std;
char arr[11][11] = { 0 };
int check(int x1, int y1, int x2, int y2)
{
int a = 0, b = 0, cnt = 0;
for (int i = x1;i <= x2;i++)
{
for (int j = y1;j <= y2;j++)
{
if (arr[i][j] == '0')
{
a += 1;
}
else
{
b += 1;
}
cnt += 1;
}
}
return a == b ? cnt : -1;
}
int main()
{
int n, m, max_ = 0;
cin >> n >> m;
// Read data
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= m;j++)
{
cin >> arr[i][j];
}
}
// Process data
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= m;j++)
{
// Top left corner at (i,j)
for (int p = i;p <= n;p++)
{
for (int q = j;q <= m;q++)
{
// Bottom right corner (p,q)
int k = check(i, j, p, q);
if (k > max_)
{
max_ = k;
}
}
}
}
}
cout << max_;
return 0;
}
Day 16: Openjudge1.11.10_Hopping on Stones in the River
[Submit]
http://noi.openjudge.cn/ch0111/10/
[Description]
Every year, cows hold various special versions of hopping competitions, including jumping from one stone to another in the river. This exciting activity takes place in a long straight river, with a stone at both the starting point and the endpoint, which is a distance of away from the starting point.
Between the starting point and the endpoint, there are stones, each at a distance of from the starting point.
During the competition, cows take turns starting from the starting point, trying to reach the endpoint, with each step only being able to jump from one stone 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 bored watching other farmers’ timid cows slowly moving between closely spaced stones. He plans to remove some stones so that the longest possible shortest jump distance from the starting point to the endpoint is maximized. He can remove at most stones, excluding the starting and ending stones.
Please help John determine the longest possible shortest jump distance after removing these stones.
[Input]
The first line contains three integers , with a single space between each two integers.
The next lines each contain an integer representing the distance of each stone from the starting point. The stones are given in order of increasing distance from the starting point, and no two stones 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 stones at positions 2 and 14, the shortest jump distance is 4 (from 17 to 21 or from 21 to 25).
[Reference Program]
Problem: In a line segment of length , there are points, removing points, leaving points, dividing the entire line segment into segments. Find the maximum length of the shortest segment among all possible partition schemes.
If the minimum distance between points is , then the distance between points must be .
To determine whether the condition is satisfied, it is still difficult. We can think in reverse: let every segment length be , and see how many points need to be removed.
- If the number of points removed is less than or equal to , then there exists a scheme where the shortest segment length is satisfied.
- If the number of points removed is greater than , then there is no such scheme, and the condition is not satisfied.
Once the condition to be checked is clear, this is a binary search problem to find the maximum value that satisfies a certain condition.
Find the midpoint: mid = (l + r)/2;
- If satisfies the condition, the next time it should be larger, take the right half, l = mid + 1;
- If does not satisfy the condition, the next time it should be smaller, take the left half, r = mid – 1;
The final result is the maximum value of the shortest segment among all possible schemes.
/*
* 10: Hopping on 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 position
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, then the position of i is the current observation point
t = arr[i];
}
}
if (l - t < x)
{
// If the distance from the endpoint to the observation point is less than x, then 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 16: GESP Level 6 2023.09_Little Yang Buys Drinks
[Submit]
https://www.luogu.com.cn/problem/B3873
[Problem Description]
Little Yang came to a store to buy some drinks. The store sells types of drinks, numbered from to , where drink number costs yuan and has a capacity of milliliters.
Little Yang has the following requirements:
-
Little Yang wants to try as many different types of drinks as possible, so he hopes to buy at most bottles of each type;
-
Little Yang is very thirsty, so he wants to buy drinks with a total capacity of at least ;
-
Little Yang is frugal, so under the premise of and , he hopes to spend as little money as possible.
For convenience, you only need to output the minimum cost. In particular, if it is not possible to meet Little Yang’s requirements, output <span>no solution</span>.
[Input Description]
The first line contains two integers .
The next lines describe each type of drink: each line contains two integers.
[Output Description]
Output a single integer representing the minimum cost required to meet Little Yang’s requirements. In particular, if the requirements cannot be met, output <span>no solution</span>.
[Sample Input 1]
5 100
100 2000
2 50
4 40
5 30
3 20
[Sample Output 1]
9
[Sample 1 Explanation]
Little Yang can buy drink number , obtaining a total of milliliters of drink, costing yuan.
If only considering the first two requirements, Little Yang could also buy drink number , which has a total capacity of milliliters, just enough to meet the requirement. However, this scheme costs yuan.
[Sample Input 2]
5 141
100 2000
2 50
4 40
5 30
3 20
[Sample Output 2]
100
[Sample 2 Explanation]
Drink number has a total of milliliters, and if each type of drink is bought at most bottles, it is just not enough to meet the requirement, so the only option is to spend yuan to buy drink number .
[Sample Input 3]
4 141
2 50
4 40
5 30
3 20
[Sample Output 3]
no solution
[Data Scale]
For test points, it is guaranteed that .
For test points, it is guaranteed that .
For test points, it is guaranteed that .
Reference Answer:
/*
* [GESP202309 Level 6] Little Yang Buys Drinks
* https://www.luogu.com.cn/problem/B3873
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int main()
{
// Input number of drink types N and required minimum capacity L
int N, L;
cin >> N >> L;
// Store the price and capacity of each drink, starting from index 1
vector<int> c(N + 1), l(N + 1);
for (int i = 1; i <= N; ++i)
{
cin >> c[i] >> l[i];
}
// Initialize the 2D dynamic programming array
// dp[i][j] represents the minimum cost for at least j total capacity from the first i types of drinks
const int INF = INT_MAX / 2;
vector<vector<int>> dp(N + 1, vector<int>(L + 1, INF));
// Fill the dynamic programming table
for (int i = 1; i <= N; ++i)
{
for (int j = 1; j <= L; ++j)
{
// Do not choose the i-th drink
dp[i][j] = dp[i - 1][j];
// Choose the i-th drink
if (j - l[i] <= 0)
{
// Current drink capacity already meets the remaining requirement
dp[i][j] = min(dp[i][j], c[i]);
}
else
{
dp[i][j] = min(dp[i][j], dp[i - 1][j - l[i]] + c[i]);
}
}
}
// Output result
if (dp[N][L] == INF)
{
cout << "no solution" << endl;
}
else
{
cout << dp[N][L] << endl;
}
return 0;
}
Youth Programming Competition Communication
The “Youth Programming Competition Communication Group” has been established (suitable for young people aged 6 to 18). Add the assistant’s WeChat to invite everyone to join 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.
