Day 10: Developing Programming Habits in 21 Days – C++ Problem Solving

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 practice
  • Preparation advice: Choose corresponding questions based on your preparation level
  • Additional value: Can be used as preparation training for whitelist competitions

Day 10: GESP Level 1 2023.09_Stationery Purchase

[Submit]

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

[Problem Description]

School has started, and Xiao Ming goes to the stationery store to buy supplies. The price of a pen is 2 yuan, and he needs pens; the price of a notebook is 5 yuan, and he needs notebooks; the price of a ruler is 3 yuan, and he needs rulers. Xiao Ming has yuan. Please help Xiao Ming calculate through programming whether he has enough money to buy the supplies he needs.

[Input Description]

Input consists of 4 lines.

The first line contains a positive integer, which is the number of pens Xiao Ming wants to buy. It is agreed that .

The second line contains a positive integer, which is the number of notebooks Xiao Ming wants to buy. It is agreed that .

The third line contains a positive integer, which is the number of rulers Xiao Ming wants to buy. It is agreed that .

The fourth line contains a positive integer, which is the amount of money Xiao Ming has (in yuan).

[Output Description]

Output consists of 2 lines. If Xiao Ming has enough money to buy the supplies he needs, the first line outputs “Yes”, and the second line outputs the amount of money Xiao Ming will have left (in yuan); otherwise, the first line outputs “No”, and the second line outputs the amount of money Xiao Ming is short (in yuan).

[Sample Input 1]

1
1
1
20

[Sample Output 1]

Yes
10

[Sample Input 2]

1
1
1
5

[Sample Output 2]

No
5

Reference Answer:

/*
* [GESP202309 Level 1] Buy Stationery
* https://www.luogu.com.cn/problem/B3863
*/
#include <iostream>

using namespace std;

int main()
{
    int x = 0, y = 0, z = 0, q = 0;
    cin >> x >> y >> z >> q;
    int t = 2 * x + 5 * y + 3 * z;
    if (t <= q)
    {
        cout << "Yes" << endl;
        cout << q - t;
    }
    else
    {
        cout << "No" << endl;
        cout << t - q;
    }
    return 0;
}

Day 10: GESP Level 2 2023.03_Chicken Problem

[Submit]

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

[Problem Description]

The “Chicken Problem” is a famous mathematical problem from ancient China’s “Zhang Qiu Jian Calculation Classic”. The essence is: “Each rooster costs 5 yuan, each hen costs 3 yuan, and every 3 chicks cost 1 yuan; now with 100 yuan, how many ways can 100 chickens be bought?”

Xiao Ming loves this story, and he decided to expand on this problem and solve it using programming: If each rooster costs yuan, each hen costs yuan, each chick costs 1 yuan; now with yuan, how many ways can chickens be bought?

[Input Description]

Input consists of one line, containing five integers, representing the , , , , and . It is agreed that ,.

[Output Description]

Output consists of one line, containing an integer, representing the number of ways.

[Sample Input 1]

5 3 3 100 100

[Sample Output 1]

4

[Sample Explanation 1]

This is the “Chicken Problem” described above. The 4 ways are: 0 roosters, 25 hens, 75 chicks; 4 roosters, 18 hens, 78 chicks; 8 roosters, 11 hens, 81 chicks; 12 roosters, 4 hens, 84 chicks.

[Sample Input 2]

1 1 1 100 100

[Sample Output 2]

5151

Reference Answer:

/*
* GESP202303 Level 2 Chicken Problem
* https://www.luogu.com.cn/problem/B3836
*/
#include <iostream>

using namespace std;

int main()
{
    int x, y, z, n, m, cnt = 0;
    cin >> x >> y >> z >> n >> m;
    for (int gj = 0; gj * x <= n && gj <= m; gj++)
        for (int mj = 0; mj * y + gj * x <= n && mj + gj <= m; mj++) 
        {
            int xj = (n - gj * x - mj * y) * z;
            if (gj + mj + xj == m)
                cnt++;
        }
    cout << cnt << endl;
    return 0;
}

Day 10: Openjudge 1.6.03_Calculate Book Fees

[Submit]

http://noi.openjudge.cn/ch0106/03/

[Description]

Below is a price list for books:

  • Introduction to Computing 28.9 yuan/book
  • Data Structures and Algorithms 32.7 yuan/book
  • Digital Logic 45.6 yuan/book
  • C++ Programming Tutorial 78 yuan/book
  • Artificial Intelligence 35 yuan/book
  • Computer Architecture 86.2 yuan/book
  • Compiler Principles 27.8 yuan/book
  • Operating Systems 43 yuan/book
  • Computer Networks 56 yuan/book
  • JAVA Programming 65 yuan/book

Given the quantity of each book purchased, calculate the total cost.

[Input]

Input consists of one line, containing 10 integers (greater than or equal to 0, less than or equal to 100), representing the quantity purchased of each book (in copies). Each two integers are separated by a space.

[Output]

Output consists of one line, containing a floating-point number f, representing the total cost. Accurate to one decimal place.

[Sample Input]

1 5 8 10 5 1 1 2 3 4

[Sample Output]

2140.2

[Reference Program]

C Language Version

# include <cstdio>

int main()
{
    double price[10] = { 28.9,32.7,45.6,78,35,86.2,27.8,43,56,65 };
    double total = 0;
    int n;
    for (int i = 0; i < 10; i++)
    {
        scanf("%d", &n);
        total += n * price[i];
    }
    printf("%.1lf", total);
    return 0;
}

C++ Version

# include <iostream>
# include <iomanip>

using namespace std;

int main()
{
    double price[10] = { 28.9,32.7,45.6,78,35,86.2,27.8,43,56,65 };
    double total = 0;
    int n;
    for (int i = 0; i < 10; i++)
    {
        cin >> n;
        total += n * price[i];
    }
    cout << fixed << setprecision(1) << total;
    return 0;
}

Day 10: GESP Level 4 2023.12_Xiao Yang’s Dictionary

[Submit]

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

[Problem Description]

On a distant planet, there are two countries, and , which use different languages: and . Xiao Yang is a translator from , and his job is to translate articles from into .

To successfully complete his work, Xiao Yang created a dictionary that records words corresponding to words. Coincidentally, these words are composed of the 26 lowercase letters from Earth.

Xiao Yang hopes you can write a program to help him translate a piece of text from into . This text consists of punctuation marks <span>!()-[]{}\|;:'",./?<></span> and some words, each word is separated by at least one punctuation mark, and your program needs to replace all words in the text with their translations. Specifically, if a word is not in the dictionary, please replace it with uppercase <span>UNK</span>.

For example, if Xiao Yang’s dictionary contains 2 words <span>abc</span> and <span>d</span>, their translations are <span>a</span> and <span>def</span>, then we can translate the text <span>abc.d.d.abc.abcd.</span> into the text <span>a.def.def.a.UNK.</span>, where the word <span>abcd</span> is not in the dictionary, so we need to use <span>UNK</span> to replace it.

[Input Description]

The first line contains an integer , indicating the number of entries in the dictionary. It is guaranteed that .

The next lines, each containing two strings separated by a single space, represent a word in the dictionary and its corresponding translation. It is guaranteed that all are unique; it is guaranteed that and do not exceed 10 characters in length.

The last line contains a string representing the text to be translated. It is guaranteed that the length of the string does not exceed 1000, and it is guaranteed that the string only contains lowercase letters and punctuation marks <span>!()-[]{}\|;:'",./?<></span>.

[Output Description]

Output one line, representing the translated result.

[Special Reminder]

In regular programs, it is good practice to provide prompts during input and output. However, in this exam, due to system limitations, please do not include any prompt information in the input and output.

[Sample Input 1]

2
abc a
d def
abc.d.d.abc.abcd.

[Sample Output 1]

a.def.def.a.UNK.

[Sample Input 2]

3
abc a
d def
abcd xxxx
abc,(d)d!-abc?abcd

[Sample Output 2]

a,(def)def!-a?xxxx

[Sample Input 3]

1
abcdefghij klmnopqrst
!()-[]{}\|;:'",./?<>abcdefghijklmnopqrstuvwxyz

[Sample Output 3]

!()-[]{}\|;:'",./?<>UNK

Reference Answer:

/*
* [GESP202312 Level 4] Xiao Yang's Dictionary
* https://www.luogu.com.cn/problem/B3927
*/
#include <iostream>
#include <string>

using namespace std;

int N;
string dic[105][2];

string fun(string s1)
{
    for (int i = 0;i < N;i++)
    {
        if (dic[i][0] == s1)
        {
            return dic[i][1];
        }
    }
    return "UNK";
}

int main()
{
    string s, result = "";
    cin >> N;
    for (int i = 0;i < N;i++)
    {
        cin >> dic[i][0] >> dic[i][1];
    }
    cin >> s;
    int i = 0;
    while (i < s.size())
    {
        int j = i;
        while (s[j] >= 'a' && s[j] <= 'z' && j < s.size())
        {
            j += 1;
        }
        int len = j - i;
        if (len > 0)
        {
            result += fun(s.substr(i, len));
            i = j;
        }
        else
        {
            result += s[i];
            i += 1;
        }
    }
    cout << result;
    return 0;
}

Day 10: Openjudge 1.11.05_Pie

[Submit]

http://noi.openjudge.cn/ch0111/05/

[Description]

My birthday is coming! According to tradition, I need to share some pies with everyone. I have pies of different flavors and sizes. friends will come to my party, and each person will get 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 the same size of pie (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 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 get, 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, use the largest pie to perform 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 pie volume;
    }
    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 10: GESP Level 6 2023.09_Xiao Yang’s Handshake Problem

[Submit]

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

[Problem Description]

In Xiao Yang’s class, there are students, with student IDs from to .

During a certain class, the teacher arranged a handshake game for the whole class, with the following rules: The teacher arranged an order for all students to enter the classroom. Each student, upon entering the classroom, must shake hands with students who are already in the classroom and have a student ID less than their own.

Now, Xiao Yang wants to know how many handshakes will occur in total in the class.

Tip: Consider using merge sort for descending order sorting and solving during this process.

[Input Description]

The input consists of lines. The first line contains an integer , representing the number of students; the second line contains integers separated by a single space, describing the order in which students enter the classroom, with each integer between .

It is guaranteed that each student will enter the classroom once.

[Output Description]

Output one line containing an integer, representing the total number of handshakes in the class.

[Sample Input 1]

4
2 1 3 0

[Sample Output 1]

2

[Sample Explanation 1]

When student 2 enters the classroom, there are no other students present.

When student 1 enters, student 2 is present, but student 2’s ID is greater than student 1’s, so they do not shake hands.

When student 3 enters, student 2 is present, and student 2’s ID is less than student 3’s, so student 3 shakes hands with student 2.

When student 0 enters, student 0’s ID is less than student 2’s, so student 0 does not shake hands with anyone.

[Sample Input 2]

6
0 1 2 3 4 5

[Sample Output 2]

15

[Sample Explanation 2]

All students will shake hands with each other because each student will find that their ID is the largest among those already in the classroom, so they will shake hands with every other student present.

[Note/Tip]

  • For test points, it is guaranteed that .
  • For all test points, it is guaranteed that .

Reference Answer:

/*
* [GESP202309 Level 6] Xiao Yang's Handshake Problem
* https://www.luogu.com.cn/problem/B3874
*/
# include<iostream>

using namespace std;

const int N = 3e5 + 10;
int tr[N],n;//tr[N] Binary Indexed Tree

// x in binary representation, the lowest bit 1 and the following 0s form the value
int lowbit(int x)
{
    return x && -x;
}

// Binary Indexed Tree x position becomes 1
void add(int x)
{
    for (;x <= n;x += lowbit(x))
    {
        tr[x]++;
    }
}

// Sum before x
int query(int x)
{
    int sum = 0;
    for (;x;x -= lowbit(x))
    {
        sum += tr[x];
    }
    return sum;
}

int main()
{
    long long ans = 0;
    cin >> n;
    for (int i = 0;i < n;i++)
    {
        int x;
        cin >> x;
        x++;
        ans += query(x);
        add(x);
    }
    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 to join the learning group. After joining, 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.

Day 10: Developing Programming Habits in 21 Days - C++ Problem Solving

Related posts

  1. Calling nvdxt.exe (NVIDIA Texture Compression Tool) in C++ for Image to DDS Conversion
  2. GESP C++ Level 2 Exercise luogu-T259140: Triangle
  3. Implementing a General Layout Scheme of Top/Left/Main in QT C++
  4. Learning C++ Programming from Scratch, Day 386: Solving the Number of Interception Systems for Missiles; Question Bank Answers; Fourth Method
  5. Advanced Python Regression Prediction – Log Transformation of Target Variables
  6. An In-Depth Analysis of Four Common Python Plotting Libraries
  7. Are You Really Using Python’s super() Correctly? Recommended to Bookmark
  8. The 16th Blue Bridge Cup C++ Provincial Competition Questions for Youth Group
  9. QT C++ Practical: Implementation of a Draggable Chart Component System
  10. Analysis of PLC Scanning Cycle and Single Button Start/Stop Case
  11. In-Depth Understanding of C++ Lambda Expressions: Reference Capture Principles, Usage, and Potential Pitfalls
  12. Simdjson: A High-Speed JSON Parsing Tool
  13. Computer Level 2 – C Language – Multiple Choice Question Training – 5
  14. In-Depth Guide to YOLOv8 TensorRT C++ Deployment: From XMake Build to Inference Pipeline
  15. Breaking Communication Barriers: MIMO Self-Organizing Networks Pave the Way for Future Emergency Solutions!

Leave a Comment