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 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: Openjudge 1.3.03_Calculate the Value of an Expression
[Submission]
http://noi.openjudge.cn/ch0103/03/
[Description]
Given three integers, calculate the value of the expression which is integer division.
[Input]
Input consists of a single line containing three integers, separated by a space.
[Output]
Output a single line, which is the value of the expression.
[Sample Input]
1 1 3
[Sample Output]
0
[Reference Program]
C Language Version
/*
* 03: Calculate (a+b)/c
* http://noi.openjudge.cn/ch0103/03/
*/
# 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
/*
* 03: Calculate (a+b)/c
* http://noi.openjudge.cn/ch0103/03/
*/
#include <iostream>
using namespace std;
int main()
{
int a, b, c;
cin >> a >> b >> c;
cout << (a + b) / c;
return 0;
}
Day 14: GESP Level 2 2024.03_Multiplication Problem
[Submission]
https://www.luogu.com.cn/problem/B3954
[Problem Description]
Little A has just learned multiplication, and to help him practice, we give him several positive integers and ask him to multiply them together.
For most problems, Little A can accurately calculate the answer, but if the product of these numbers exceeds , Little A will not be able to solve it.
Please write a program to tell us how Little A would respond.
[Input Description]
The first line contains an integer , indicating the number of positive integers.
The next lines each contain one integer.
[Output Description]
Output a single line; if the product exceeds , output <span>>1000000</span>; otherwise, output the product of all numbers.
[Sample Input 1]
2
3
5
[Sample Output 1]
15
[Sample Input 2]
3
100
100
100
[Sample Output 2]
1000000
[Sample Input 3]
4
100
100
100
2
[Sample Output 3]
>1000000
Reference Answer:
/*
* [GESP202403 Level 2] Multiplication Problem
* https://www.luogu.com.cn/problem/B3954
*/
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
long long product = 1;
for (int i = 0; i < n; ++i)
{
int a;
cin >> a;
if (product * a > 1000000)
{
cout << ">1000000" << endl;
return 0;
}
product *= a;
}
cout << product << endl;
return 0;
}
Day 14: GESP Level 3 2023.12_Unit Conversion
[Submission]
https://www.luogu.com.cn/problem/B3926
[Problem Description]
Little Yang’s math homework this week is to do unit conversions. As he likes programming, he decided to write a program to help him solve these problems.
Little Yang has only learned length and weight units, specifically:
- Length units include kilometers (), meters (), and millimeters (), with the following relationships:.
- Weight units include kilograms (), grams (), and milligrams (), with the following relationships:.
Little Yang’s homework only involves converting larger units to smaller units, meaning his homework will only include the following types of problems: meters to millimeters, kilometers to millimeters, kilometers to meters, grams to milligrams, kilograms to milligrams, and kilograms to grams.
Now, please help him complete the unit conversion program.
[Input Description]
The first line of input is an integer , indicating the number of problems.
The next lines each contain a string representing the unit conversion problem in the format <span>x unit1 = ? unit2</span>, where <span>x</span> is a non-negative integer not exceeding 1000, and <span>unit1</span> and <span>unit2</span> are the English abbreviations of the two units, ensuring they are either both length units or both weight units, and that <span>unit1</span> is larger than <span>unit2</span>.
For example, if the problem requires you to convert <span>1km</span> to <span>mm</span>, the input would be <span>1 km = ? mm</span>.
[Output Description]
Output a line for each problem, sequentially outputting all the answers. When outputting, simply substitute the input into the answer, and the rest of the output must be exactly as specified.
Since Little Yang’s problems only involve converting larger units to smaller units, and the input <span>x</span> is an integer, the answer must also be an integer.
For example, if the problem requires you to convert <span>1km</span> to <span>mm</span>, the input would be <span>1 km = ? mm</span>, and you would need to output <span>1 km = 1000000 mm</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. The input format will strictly follow the problem requirements, and your output must match the standard answer exactly to score points, so please check carefully before submission.
[Sample Input 1]
2
1 km = ? mm
1 m = ? mm
[Sample Output 1]
1 km = 1000000 mm
1 m = 1000 mm
[Sample Input 2]
5
100 m = ? mm
1000 km = ? m
20 kg = ? g
200 g = ? mg
0 kg = ? mg
[Sample Output 2]
100 m = 100000 mm
1000 km = 1000000 m
20 kg = 20000 g
200 g = 200000 mg
0 kg = 0 mg
Reference Answer:
/*
* [GESP202312 Level 3] Unit Conversion
* https://www.luogu.com.cn/problem/B3926
*/
#include<iostream>
#include<string>
using namespace std;
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int x,k=1;
string s1, s2, s3, s4;
cin >> x >> s1 >> s2 >> s3 >> s4;
if (s4.size() == 1)
{
k = 1000;
}
else
{
k = s1.size() == 1 ? 1000 : 1000000;
}
cout << x << ' ' << s1 << ' ' << s2 << ' ';
cout << x * k << ' ' << s4;
}
return 0;
}
Day 14: GESP Level 4 2023.06_Image Compression
[Submission]
https://www.luogu.com.cn/problem/B3851
[Problem Description]
An image is composed of many pixels. If 0 represents black, 255 represents white, and values between 0 and 255 represent different shades of gray, then a pixel can be represented by one byte (value range from decimal 0-255, hexadecimal 00-FF). An image composed of such pixels is called a grayscale image with 256 levels of gray.
Now we want to compress the 256-level grayscale image to 16 levels of gray, meaning each pixel’s value range is from decimal 0-15, hexadecimal 0-F. The compression rule is: count the number of each gray level, take the top 16 gray levels with the highest counts (if two gray levels have the same count, order them by gray level value from smallest to largest), and assign them numbers 0-F (the most frequent gets 0, and so on). Other gray levels are converted to the nearest one of the 16 gray levels, where the absolute difference between a pixel’s gray level and one of the 16 gray levels is minimized; if the absolute differences are equal, the gray level with the smaller number is considered closer.
[Input Description]
The first line of input is a positive integer , indicating that the next lines of data form a 256-level grayscale image. It is guaranteed that .
The second line and onwards consist of equal-length strings of even length, where each two characters represent a pixel in hexadecimal. It is guaranteed that the input grayscale image has at least 16 gray levels. Each line contains at most 20 pixels.
[Output Description]
The first line outputs the hexadecimal encoding of the selected 16 gray levels, totaling 32 characters.
From the second line onwards, output the compressed image, with each pixel represented by one hexadecimal digit indicating the compressed gray level value.
[Sample Input 1]
10
00FFCFAB00FFAC09071B5CCFAB76
00AFCBAB11FFAB09981D34CFAF56
01BFCEAB00FFAC0907F25FCFBA65
10FBCBAB11FFAB09981DF4CFCA67
00FFCBFB00FFAC0907A25CCFFC76
00FFCBAB1CFFCB09FC1AC4CFCF67
01FCCBAB00FFAC0F071A54CFBA65
10EFCBAB11FFAB09981B34CFCF67
01FFCBAB00FFAC0F071054CFAC76
1000CBAB11FFAB0A981B84CFCF66
[Sample Output 1]
ABCFFF00CB09AC07101198011B6776FC
321032657CD10E
36409205ACC16D
B41032657FD16D
8F409205ACF14D
324F326570D1FE
3240C245FC411D
BF4032687CD16D
8F409205ACC11D
B240326878D16E
83409205ACE11D
[Sample Explanation 1]
Gray levels ‘AB’, ‘CF’, and ‘FF’ appeared 14 times, ’00’ appeared 10 times, ‘CB’ appeared 9 times, ’09’ appeared 7 times, ‘AC’ appeared 6 times, ’07’ appeared 5 times, ’10’, ’11’, and ’98’ appeared 4 times, ’01’, ‘1B’, ’67’, ’76’, and ‘FC’ appeared 3 times.
Reference Answer:
/*
* [GESP202306 Level 4] Image Compression
* https://www.luogu.com.cn/problem/B3851
*/
#include<iostream>
#include<string>
using namespace std;
int his[256] = { 0 };
int color[16] = { 0 };
int image[20][20];
int cpimg[20][20];
// Convert one hexadecimal character to a number
int trans(char a)
{
if (a <= '9')
{
return (a - '0');
}
return (a - 'A' + 10);
}
// Convert one hexadecimal number to a character
char itrans(int n)
{
if (n >= 10)
{
return (char)(n - 10 + 'A');
}
return (char)(n + '0');
}
// Find the closest gray level to c
int compress(int c)
{
int dis = 256, res = -1;
for (int i = 0; i < 16; i++)
{
int d = c - color[i];
if (d < 0)
d = -d;
if (d < dis)
{
dis = d;
res = i;
}
}
return res;
}
int main()
{
int N = 0, M = 0;
cin >> N;
// Input image and count gray levels
for (int i = 0; i < N; i++)
{
string line;
cin >> line;
M = line.size() / 2;
for (int j = 0; j < M; j++)
{
int c = trans(line[j * 2]) * 16 + trans(line[j * 2 + 1]);
image[i][j] = c;
his[c]++;
}
}
// Select the 16 gray levels that appear most frequently
for (int c = 0; c < 16; c++)
{
int max = -1, max_id = -1;
for (int i = 0; i < 256; i++)
{
if (his[i] > max)
{
max = his[i];
max_id = i;
}
}
color[c] = max_id;
his[max_id] = -1;
}
// Compress the gray levels of image to cpimg
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cpimg[i][j] = compress(image[i][j]);
}
}
// Output the selected 16 gray levels
for (int c = 0; c < 16; c++)
{
cout << itrans(color[c] / 16) << itrans(color[c] % 16);
}
cout << endl;
// Output the compressed image
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cout << itrans(cpimg[i][j]);
}
cout << endl;
}
return 0;
}
Day 14: Openjudge 1.11.07_Sum Equals Given Number
[Submission]
http://noi.openjudge.cn/ch0111/07/
[Description]
Given several integers, determine if there is a pair of numbers among them that sums to a given number.
[Input]
There are three lines:
The first line is an integer , indicating there are integers.
The second line contains integers, with values ranging from to .
The third line is an integer , indicating the desired sum.
[Output]
If there exists a pair of numbers that sum to , output the two integers, with the smaller one first, separated by a single space. If there are multiple pairs that satisfy the condition, choose the pair with the smaller first number. If no such pair exists, output a line with “No”.
[Sample Input]
4
2 5 1 4
6
[Sample Output]
1 5
[Reference Program]
/*
* 07: Sum Equals Given Number
* http://noi.openjudge.cn/ch0111/07/
*/
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100005;
int n, m;
int arr[N];
int find(int left, int right, int key)
{
while (left <= right)
{
int mid = (left + right) / 2;
if (arr[mid] == key)
{
return mid;
}
else if (arr[mid] < key)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
return -1;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
sort(arr, arr + n);
cin >> m;
for (int i = 0; i < n; i++)
{
int x = arr[i];
int y = m - x;
if (find(i + 1, n - 1, y) != -1)
{
cout << x << " " << y;
return 0;
}
}
cout << "No";
return 0;
}
Day 14: GESP Level 6 2023.09_Little Yang Buys Drinks
[Submission]
https://www.luogu.com.cn/problem/B3873
[Problem Description]
Little Yang went to a store intending to buy some drinks. The store sells a total of 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 conditions of and , he hopes to spend as little money as possible.
For convenience, you only need to output the minimum cost required. 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 indicating the minimum cost required to meet Little Yang’s requirements. In particular, if it is not possible to meet the requirements, 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 would total milliliters, just meeting the requirement. However, this option would cost 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 provides a total of milliliters, and if each type of drink is bought at most bottles, it cannot meet the requirement, so the only option is to spend yuan on 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 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 when using the first i types of drinks to achieve at least j total capacity
const int INF = INT_MAX / 2;
vector<vector> dp(N + 1, vector(L + 1, INF));
// Fill the dynamic programming table
for (int i = 1; i <= N; ++i)
{
for (int j = 1; j <= L; ++j)
{
// Do not select the i-th drink
dp[i][j] = dp[i - 1][j];
// Select the i-th drink
if (j - l[i] <= 0)
{
// Current drink's capacity 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;
}
</vectorYouth Programming Competition Exchange
The “Youth Programming Competition Exchange Group” has been established (suitable for young people 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.
