Learn programming with Lao Ma by “leveling up and battling”!

• 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 15: Openjudge1.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]

The input consists of a single line containing three integers,,, separated by a space.

[Output]

The output is 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 15: GESP Level 2 2025.03_Time Leap

[Submission]

https://www.luogu.com.cn/problem/B4260

[Problem Description]

Assuming the current date is year month day hours later is year month day hours, for the given , Xiao Yang wants you to help him calculate the corresponding .

[Input Description]

The input consists of five lines, each containing a positive integer, representing .

[Output Description]

The output consists of four positive integers, representing .

[Sample Input 1]

2008
2
28
23
1

[Sample Output 1]

2008 2 29 0

[Data Range]

For all data, it is guaranteed that ,,,, are valid times.

[Hint]

Leap year judgment rules

• Ordinary leap year: A year divisible by 4 but not by 100.
• Century leap year: A year divisible by 400.

A year that satisfies any of the above rules is a leap year; otherwise, it is a common year.

Reference Answer:

Method 1:

/*
* [GESP202503 Level 2] Time Leap
* https://www.luogu.com.cn/problem/B4260
*/
#include <iostream>

using namespace std;

int main()
{
    int y, m, d, h, k;
    cin >> y >> m >> d >> h >> k;
    h = h + k;
    if (h >= 24)
    {
        d += 1;
        h = h - 24;
    }
    if (m == 2)
    {
        if ((y % 4 == 0 && y % 100 != 0) || (y % 400 == 0))
        {
            if (d > 29)
            {
                m += 1;
                d = d - 29;
            }
        }
        else
        {
            if (d > 28)
            {
                m += 1;
                d = d - 28;
            }
        }
    }
    else
    {
        if (m == 1 || m == 3 || m == 5 || m == 7 || m == 8 || m == 10 || m == 12)
        {
            if (d > 31)
            {
                m += 1;
                d = d - 31;
            }
        }
        else
        {
            if (d > 30)
            {
                m += 1;
                d = d - 30;
            }
        }
    }
    if (m > 12)
    {
        y += 1;
        m = m - 12;
    }
    cout << y << " " << m << " " << d << " " << h << endl;
    return 0;
}

Method 2:

/*
* [GESP202503 Level 2] Time Leap
* https://www.luogu.com.cn/problem/B4260
*/
#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int days[] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
    int y, m, d, h, k;
    cin >> y >> m >> d >> h >> k;
    if ((y % 4 == 0 && y % 100 != 0) || (y % 400 == 0))
    {
        days[2] = 29;
    }
    h += k;
    if (h > 23)
    {
        h = h - 24;
        d += 1;
    }  
    if (d > days[m])
    {
        d = d- days[m];
        m += 1;
    }
    if (m > 12)
    {
        m = m - 12;
        y += 1;
    }
    cout << y << " " << m << " " << d << " " << h;
    return 0;
}

Day 15: GESP Level 3 2024.12_Number Replacement

[Submission]

https://www.luogu.com.cn/problem/B4066

[Problem Description]

Xiao Yang has a sequence of numbers, namely , and he wants to replace all numbers greater than with the maximum value of the sequence, and all numbers less than with the minimum value of the sequence. Please help him calculate the replaced sequence.

[Input Description]

The first line contains two positive integers , as described in the problem statement.

The second line contains numbers, representing the sequence .

[Output Description]

The output consists of positive integers, representing the replaced results.

[Sample Input 1]

5 0
-2 -1 0 1 2

[Sample Output 1]

-2 -2 0 2 2

[Data Range]

For all data, it is guaranteed that .

Reference Answer:

/*
* [GESP202412 Level 3] Number Replacement
* https://www.luogu.com.cn/problem/B4066
*/
#include<iostream>

using namespace std;

const int N = 100005;
int arr[N];
int main()
{
    int n, k, max = -1e-5, min = 1e5;
    cin >> n >> k;
    for (int i = 0;i < n;i++)
    {
        cin >> arr[i];
        if (arr[i] > max)
        {
            max = arr[i];
        }
        if (arr[i] < min)
        {
            min = arr[i];
        }
    }
    for (int i = 0;i < n;i++)
    {
        if (arr[i] > k)
        {
            cout << max << " ";
        }
        elseif (arr[i] < k)
        {
            cout << min << " ";
        }
        else
        {
            cout << arr[i] << " ";
        }
    }
    return 0;
}

Day 15: GESP Level 4 2024.03_Similar Strings

[Submission]

https://www.luogu.com.cn/problem/B3958

[Problem Description]

For two strings and , if can be transformed into by deleting one character, inserting one character, or modifying one character, we say that and are similar.

For example, apple can become applee by inserting one character, can become appe by deleting one character, and can become bpple by modifying one character. Therefore, apple and applee, appe, bpple are similar. However, applee cannot become bpple by any of the operations, so they are not similar.

In particular, two identical strings are also considered similar.

Given groups, please determine whether they are similar.

[Input Description]

The first line contains a positive integer.

The next lines, each containing two space-separated strings and .

It is guaranteed that the lengths of and do not exceed 50. It is guaranteed that and only contain lowercase letters.

[Output Description]

The output consists of lines. For each group, if they are similar, output <span>similar</span>, otherwise output <span>not similar</span>.

[Sample Input]

5
apple applee
apple appe
apple bpple
applee bpple
apple apple

[Sample Output]

similar
similar
similar
not similar
similar

Reference Answer:

/*
* March 2024 C++ Level 4 Exam Paper
* Similar Strings
*/
#include <iostream>
#include <string>

using namespace std;

string checkEq(string s1, string s2)
{
    int cnt = 0;
    for (int i = 0;i < s1.size();i++)
    {
        if (s1[i] != s2[i])
        {
            cnt += 1;
        }
    }
    return cnt <= 1 ? "similar" : "not similar";
}

string check(string s1, string s2)
{
    int len1 = s1.size();//short
    int len2 = s2.size();//long
    if (len2 - len1 > 1)
    {
        return "not similar";
    }
    if (len2 == len1)
    {
        return checkEq(s1, s2);
    }
    int i = 0, j = 0, cnt = 0;
    while (i < len1)
    {
        if (s1[i] != s2[j])
        {
            cnt += 1;
            j += 1;
            if (cnt == 2)
            {
                return"not similar";
            }
        }
        else
        {
            i += 1;
            j += 1;
        }
    }   
    return "similar";
}

int main()
{
    int T;
    string A, B;
    cin >> T;
    for (int i = 0;i < T;i++)
    {
        cin >> A >> B;
        if (A.size() < B.size())
        {
            cout << check(A, B) << endl;
        }
        else
        {
            cout << check(B, A) << endl;
        }
    }
    return 0;
}

Day 15: GESP Level 5 2025.03_Primitive Root Judgment

[Submission]

https://www.luogu.com.cn/problem/P11961

[Problem Description]

Xiao A knows that for prime number , the primitive root of is a positive integer that satisfies the following conditions:

• ;
• ;
• For any , it holds that .

Where represents the remainder of divided by .

Xiao A now has an integer , please help him determine whether is a primitive root of .

[Input Description]

The first line contains a positive integer, representing the number of test cases.

Each test case consists of a line with two positive integers .

[Output Description]

For each test case, output a line. If is a primitive root of , output <span>Yes</span>, otherwise output <span>No</span>.

[Sample Input 1]

3
3 998244353
5 998244353
7 998244353

[Sample Output 1]

Yes
Yes
No

[Data Range]

For the test points, it is guaranteed that .

For all test points, it is guaranteed that ,,, are prime numbers.

Reference Answer:

/*
* [GESP202503 Level 5] Primitive Root Judgment
* https://www.luogu.com.cn/problem/P11961
*/

# include <iostream>
# include<vector>

using namespace std;

// Prime factorization
vector<int> get_prime_factors(int m)
{
    vector<int> factors;
    if (m % 2 == 0)// Handle even factor 2
    {
        factors.push_back(2);
        while (m % 2 == 0)
        {
            m /= 2;
        }
    }
    // Handle odd factors
    for (int i = 3;i * i <= m;i += 2)
    {
        if (m % i == 0)
        {
            factors.push_back(i);
            while (m % i == 0)
            {
                m /= i;
            }
        }
    }
    if (m > 1)// Handle remaining prime factors greater than 1
    {
        factors.push_back(m);
    }
    return factors;
}

// Fast power algorithm to calculate (a^b) % mod
long long fast_pow(long long a, long long b, int mod)
{
    long long ans = 1;
    a = a % mod;
    while (b != 0)
    {
        if ((b && 1) != 0)
        {
            ans = ans * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

int main()
{
    int T;
    cin >> T;
    for (int i = 0;i < T;i++)
    {
        int a, p;
        cin >> a >> p;
        int m = p - 1;
        vector&lt;int&gt; factors = get_prime_factors(m);
        bool flag = true;
        for (int q : factors)
        {
            if (fast_pow(a, m / q, p) == 1)
            {
                flag = false;
                cout << "No" << endl;
                break;
            }
        }
        if (flag == true)
        {
            cout << "Yes" << endl;
        }
    }
    return 0;
}

Day 15: GESP Level 6 2024.12_Transporting Goods

[Submission]

https://www.luogu.com.cn/problem/P11376

[Problem Description]

Xiao Yang manages trucks, each truck needs to transport goods to City A and City B several times a day. Xiao Yang also has transport stations located between City A and City B.

Each time goods are transported, the truck departs from the initial transport station to City A or City B, and then returns to the initial transport station. The positions of City A, City B, and the transport stations can be viewed as three points on a number line, where the coordinate of City A is , City B is , and the coordinates of the transport stations are with at most trucks as the initial transport station. Xiao Yang wants to know the shortest total driving distance of all trucks per day under optimal allocation of each truck’s initial transport station.

[Input Description]

The first line contains three positive integers , representing the number of transport stations, the number of trucks, and the distance between the two cities.

The next lines each contain two positive integers , representing the position of the transport station and the maximum number of trucks it can accommodate.

The next lines each contain two positive integers , representing the number of times the truck needs to transport goods to City A and City B each day.

[Output Description]

The output is a positive integer representing the shortest total driving distance of all trucks per day.

[Sample Input 1]

3 4 10
1 1
2 1
8 3
5 3
7 2
9 0
1 10000

[Sample Output 1]

40186

[Sample Explanation]

The initial transport station for the truck is station , the initial transport station for the truck is station . The initial transport station for the truck is station , the initial transport station for the truck is station . The shortest total driving distance is 40186.

[Data Range]

Subtask Number	Data Point Proportion
1	20%
2	20%
3	60%

For all data, it is guaranteed that ,,,,, are valid.

Reference Answer:

Distance calculation: If the truck departs from station, the total distance for one trip to City A is. The total distance for one trip to City B is. Therefore, if the truck is assigned to station, its total daily driving distance is

Optimization goal: We need to minimize the total driving distance of all trucks, which means minimizing, since is a constant, it can be ignored, thus the problem is transformed into minimizing.

Greedy strategy: To minimize the total, we discuss two cases.

• If, we hope to assign to the smaller.
• If, we hope to assign to the larger.

Thus, we need to sort the trucks by into one group and by into another group in ascending order, and sort the stations in ascending order, then perform matching.

/*
* [GESP202412 Level 6] Transporting Goods
* https://www.luogu.com.cn/problem/P11376
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Site
{
    int p; // Position of the transport station
    int c; // Maximum number of trucks it can accommodate
};
bool cmp1(Site s1, Site s2)
{
    return s1.p < s2.p;
}

struct Truck
{
    int a; // Number of times to transport goods to City A
    int b; // Number of times to transport goods to City B
    int diff; //
};
bool cmp2(Truck t1, Truck t2)
{
    return t1.diff > t2.diff;
}

int main()
{
    vector<Site> sites;
    vector<Truck> trucks01;//a>b
    vector<Truck> trucks02;//a<b
    // 1. Get data
    int n, m, x;
    cin >> n >> m >> x;
    for (int i = 0;i < n;i++)
    {
        Site s;
        cin >> s.p >> s.c;
        sites.push_back(s);
    }
    for (int i = 0;i < m;i++)
    {
        Truck t;
        cin >> t.a >> t.b;
        if (t.a >= t.b)
        {
            t.diff = t.a - t.b;
            trucks01.push_back(t);
        }            
        else
        {
            t.diff = t.b - t.a;
            trucks02.push_back(t);
        }
    }
    
    // 2. Process data
    sort(sites.begin(), sites.end(),cmp1);
    sort(trucks01.begin(), trucks01.end(), cmp2);
    sort(trucks02.begin(), trucks02.end(), cmp2);

    long long ans = 0;
    int k = 0;
    for (int i = 0;i < trucks01.size();i++)
    {
        if (sites[k].c == 0)
        {
            k++;
        }
        int a = trucks01[i].a;
        int b = trucks01[i].b;
        int p = sites[k].p;
        // 2ll indicates 2 is of long long data type
        ans += 2ll * a * p + 2ll * (x - p) * b;
        sites[k].c--;
    }
    k = n - 1;
    for (int i = 0;i < trucks02.size(); i++)
    {
        if (sites[k].c == 0)
        {
            k--;
        }
        int a = trucks02[i].a;
        int b = trucks02[i].b;
        int p = sites[k].p;
        // 2ll indicates 2 is of long long data type
        ans += 2ll * a * p + 2ll * (x - p) * b;
        sites[k].c--;
    }
    // 3. Output result
    cout << ans;
    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, Ministry of Education whitelist competition coaching, and youth programming team competitions.