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

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

Day 02: GESP Level 1 Exam for Xiao Yang on 2023.12

[Submit]

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

[Problem Description]

Today is day , and Xiao Yang has days left until the exam. Can you calculate what day of the week Xiao Yang’s exam will be? (In this problem, represents Sunday)

[Input Description]

Input consists of 2 lines, the first line contains an integer (); the second line contains an integer ().

[Output Description]

Output an integer representing what day of the week Xiao Yang’s exam will be.

[Special Reminder]

In regular programs, it is good practice to provide prompts for 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]

1
6

[Sample Output 1]

7

[Sample Explanation 1]

If today is day 1, then 6 days later will be Sunday, which is represented by .

[Sample Input 2]

5
3

[Sample Output 2]

1

[Sample Explanation 2]

If today is day 5, then 3 days later will be day 1.

Reference Answer:

Method 1:

/*
* [GESP202312 Level 1] Xiao Yang's Exam
* https://www.luogu.com.cn/problem/B3921
*/
#include <iostream>

using namespace std;

int main()
{
    int X, N;
    cin >> X >> N;
    int a = (X + N) % 7;
    cout << (a == 0 ? 7 : a);
    return 0;
}
</iostream>

Method 2:

/*
* [GESP202312 Level 1] Xiao Yang's Exam
* https://www.luogu.com.cn/problem/B3921
*/
#include <iostream>

using namespace std;

int main()
{
    int X, N;
    cin >> X >> N;
    int a = (X - 1 + N) % 7 + 1;
    cout << a;
    return 0;
}
</iostream>

Day 02: GESP Level 2 Exam on 2023.09 – Digital Black Hole

[Submit]

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

[Problem Description]

Given a three-digit number, the digits must be different. For example, 352 meets the requirement, while 112 does not. Rearranging the three digits of this three-digit number to get the largest number and subtracting the smallest number forms a new three-digit number. The above process can be repeated. Amazingly, it will eventually yield 495!

For instance, rearranging 352 gives the largest number 532 and the smallest number 235, their difference is 297; transforming 297 gives 972-279=693; transforming 693 gives 963-369=594; transforming 594 gives 954-459=495. Thus, 352 reaches 495 after 4 transformations.

Now, given a three-digit number, can you determine how many transformations it takes to reach 495 through programming?

[Input Description]

Input consists of one line containing a valid three-digit number.

[Output Description]

Output one line containing an integer representing the number of transformations to reach 495.

[Sample Input 1]

352

[Sample Output 1]

4

Reference Answer:

/*
* [GESP202309 Level 2] Digital Black Hole
* https://www.luogu.com.cn/problem/B3866
*/
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int N, C = 0;
    cin >> N;
    while (N != 495)
    {
        int a, b, c;
        a = N % 10;
        b = N / 10 % 10;
        c = N / 100;

        int a_ = max(max(a, b), c);
        int c_ = min(min(a, b), c);
        int b_ = a + b + c - a_ - c_;

        int max_ = a_ * 100 + b_ * 10 + c_;
        int min_ = c_ * 100 + b_ * 10 + a_;
        N = max_ - min_;
        C += 1;
    }
    cout << C;
    return 0;
}
</algorithm></iostream>

Day 02: GESP Level 3 Exam on 2023.09 – Base System Judgment

[Submit]

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

[Problem Description]

A base number system refers to a counting system that carries over at a certain base. For example, people commonly use the decimal system in daily life, while computers generally use binary at a lower level. Additionally, octal and hexadecimal are also commonly used in certain situations (in hexadecimal, letters A to F represent ten to fifteen).

Now, given numbers, please determine whether they can be represented in binary, octal, decimal, or hexadecimal. For example, <span>15A6F</span> can only be hexadecimal, while <span>1011</span> can be represented in all four bases.

[Input Description]

The first line contains a decimal integer . The next lines each contain a string representing the number to be judged. Ensure that all strings consist of digits and uppercase letters, and do not start with 0. Ensure that there are no empty lines.

Ensure that , and that the length of all strings does not exceed 10.

[Output Description]

Output lines, each containing 4 numbers separated by spaces, indicating whether the given string can represent a binary, octal, decimal, or hexadecimal number. Use 1 to indicate possible and 0 to indicate not possible.

For example, for the string that can only be hexadecimal <span>15A6F</span>, the output should be <span>0 0 0 1</span>; for the string that can be represented in all four bases <span>1011</span>, the output should be <span>1 1 1 1</span>.

[Sample Input 1]

2
15A6F
1011

[Sample Output 1]

0 0 0 1
1 1 1 1

[Sample Input 2]

4
1234567
12345678
FF
GG

[Sample Output 2]

0 1 1 1
0 0 1 1
0 0 0 1
0 0 0 0

Reference Answer:

Method 1:

/*
* [GESP202309 Level 3] Base System Judgment
* https://www.luogu.com.cn/problem/B3868
*/
#include <iostream>
#include <string>

using namespace std;

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        string s = "1 1 1 1";
        string str;
        cin >> str;
        for (int j = 0; j < str.size(); j++)
        {
            char a = str[j];
            if (a > '1')
            {
                s[0] = '0';
            }
            if (a > '7')
            {
                s[2] = '0';
            }
            if (a > '9')
            {
                s[4] = '0';
            }
            if (a > 'F')
            {
                s[6] = '0';
            }          
        }
        cout << s << endl;
    }
    return 0;
}
</string></iostream>

Method 2:

/*
* [GESP202309 Level 3] Base System Judgment
* https://www.luogu.com.cn/problem/B3868
*/
#include <iostream>

using namespace std;

int main()
{
    int N;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        string str;
        cin >> str;
        char max = '0';
        for (int j = 0; j < str.size(); j++)
        {
            if (str[j] > max)
                max = str[j];
        }
        cout << (max <= '1') << ' ' << (max <= '7') << ' ' << (max <= '9') << ' ' << (max <= 'F');
    }
    return 0;
}
</iostream>

Day 02: GESP Level 4 Exam on 2023.09 – Variable Length Encoding

[Submit]

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

[Problem Description]

Xiao Ming has just learned three integer encoding methods: original code, inverse code, and complement code, and has learned that computers usually use complement code to store integers. However, he always feels that such large numbers are rarely used in life, and commonly used numbers also need to be represented in 4 bytes of complement code, which seems wasteful.

Curious Xiao Ming searched and found a variable length encoding method for positive integers. The rules of this encoding method are as follows:

1. For a given positive integer, first express it in binary form. For example, .

2. Split the binary number into groups of 7 bits from low to high, padding with 0 at the high end if there are fewer than 7 bits. For example, becomes one group, becomes two groups.

3. Starting from the group representing the low end, add the highest bit. If this group is the last group, fill in 0 at the highest bit; otherwise, fill in 1. Thus, the variable length encoding of 0 is one byte, while the variable length encoding of 926 is two bytes.

This encoding method can express smaller numbers with fewer bytes and can express very large numbers with many bytes. For example, the binary representation of is , so its variable length encoding is (in hexadecimal representation) , totaling 9 bytes.

Can you write a program to find the variable length encoding of a positive integer?

[Input Description]

The first line contains a positive integer.

[Output Description]

Output one line, displaying each byte of the corresponding variable length encoding, with each byte represented in 2-digit hexadecimal (where A-F uses uppercase letters), separated by spaces.

[Sample Input 1]

0

[Sample Output 1]

00

[Sample Input 2]

926

[Sample Output 2]

9E 07

[Sample Input 3]

987654321012345678

[Sample Output 3]

CE 96 C8 A6 F4 CB B6 DA 0D

Reference Answer:

/*
* GESP202309 Level 4 Variable Length Encoding
* https://www.luogu.com.cn/problem/B3870
*/
#include <iostream>
#include <string>

using namespace std;

// Convert integer to binary
string functo2(long long n)
{
    string s = "";
    while (n != 0)
    {
        if (n % 2 == 0)
        {
            s = '0' + s;
        }
        else
        {
            s = '1' + s;
        }
        n = n / 2;
    }
    // Pad with 0 to make length a multiple of 7
    int len = 7 - s.size() % 7;
    while (len != 0)
    {
        s = '0' + s;
        len -= 1;
    }
    return s;
}

string to16(int i)
{
    string a;
    if (i >= 0 && i <= 9)
    {
        a = char('0' + i - 0);
    }
    else
    {
        a = char('A' + i - 10);
    }
    return a;
}

string functo16(string s)
{
    int k1 = 1, k2 = 1, total1 = 0, total2 = 0;
    for (int i = 7; i >= 4; i--)
    {
        total1 += (s[i] - '0') * k1;
        k1 *= 2;
    }
    for (int i = 3; i >= 0; i--)
    {
        total2 += (s[i] - '0') * k2;
        k2 *= 2;
    }
    return to16(total2) + to16(total1);
}

int main()
{
    long long n;
    cin >> n;
    string s = functo2(n);
    int len = s.length();
    for (int i = len - 7; i >= 0; i -= 7)
    {
        string a = s.substr(i, 7);
        if (i == 0)
        {
            a = '0' + a; // Highest bit padded with 0
        }
        else
        {
            a = '1' + a; // Non-highest bit padded with 1
        }
        cout << functo16(a) << " ";
    }
    return 0;
}
</string></iostream>

Day 02: Openjudge 1.11.06 – Monthly Expenses

[Submit]

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

[Description]

Farmer John is a shrewd accountant. He realizes that he may not have enough money to keep the farm running. He calculates and records the expenses needed for the next days.

John plans to create a budget for a continuous financial period, which he calls a fajo month. Each fajo month contains one day or multiple consecutive days, with each day being included in exactly one fajo month.

John’s goal is to reasonably arrange the number of days included in each fajo month so that the maximum expense of the fajo month is minimized.

[Input]

The first line contains two integers , separated by a single space.

The next lines each contain an integer between 1 and 10000, representing the daily expenses for the next days.

[Output]

An integer representing the minimum value of the maximum monthly expense.

[Sample Input]

7 5
100
400
300
100
500
101
400

[Sample Output]

500

[Hint]

If John considers the first two days as one month, the third and fourth days as another month, and the last three days as one month, then the maximum monthly expense would be 500. Any other allocation scheme would yield a higher value.

[Reference Program]

Since the solution’s range is clear, binary search can be used to find the actual solution.

Assume the binary search range is left~right, where left is the maximum of the daily expenses, and right is the total of the daily expenses (considering an extreme case where each day is treated as a separate month, the maximum monthly expense would be the maximum daily expense; conversely, if all days are combined into one month, the maximum monthly expense would be the total of all daily expenses).

/*
* 06: Monthly Expenses
* http://noi.openjudge.cn/ch0111/06/
*/
#include <iostream>

using namespace std;

int N, M;
int a[100005];

/*
* Problem statement:
* Divide all days into several segments, first calculate the sum of numbers in each segment,
* then count the maximum sum of segments, which should be minimized.
*/
bool check(int mid)
{
    // When dividing by mid, the number of financial periods t compared to M
    // If t >= M, increase expenses to reduce t
    int sum = 0, t = 0;
    for (int i = 0; i < N; i++)
    {
        if (sum + a[i] > mid)
        {
            sum = a[i];
            t++;
        }
        else
        {
            sum += a[i];
        }
    }
    return t >= M ? true : false;
}

int main()
{
    cin >> N >> M;
    int sum = 0, max = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> a[i];
        sum += a[i];
        if (a[i] > max)
        {
            max = a[i];
        }
    }
    int left = max, right = sum, mid;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (check(mid) == true)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    cout << mid << endl;
    return 0;
}
</iostream>

Day 02: Openjudge 3.3.1696 – Polish Expression

[Submit]

http://noi.openjudge.cn/ch0303/1696/

[Description]

A Polish expression is an arithmetic expression with operators placed before their operands. For example, the Polish representation of the expression 2 + 3 is + 2 3. The advantage of Polish expressions is that there is no need for operator precedence or parentheses to change the order of operations; for instance, the Polish representation of (2 + 3) * 4 is * + 2 3 4. This problem requires calculating the value of a Polish expression, which includes the operators +, -, *, and /.

[Input]

The input consists of a single line, where operators and operands are separated by spaces, and operands are floating-point numbers.

[Output]

The output is a single line with the value of the expression.

You can directly use <span>printf("%f\n", v)</span> to output the value v.

[Sample Input]

* + 11.0 12.0 + 24.0 35.0

[Sample Output]

1357.000000

[Hint]

You can use <span>atof(str)</span> to convert a string to a double type floating-point number.<span>atof</span> is defined in math.h.

This problem can be solved using recursive function calls.

[Reference Program]

/*
* 1696: Polish Expression
* http://noi.openjudge.cn/ch0303/1696/
*/
#include <iostream>
#include <string>
#include <iomanip>

using namespace std;

string s;
double f()
{
    cin >> s;
    if (s == "+")
        return f() + f();
    else if (s == "-")
        return f() - f();
    else if (s == "*")
        return f() * f();
    else if (s == "/")
        return f() / f();
    else
        return stod(s);
}

int main()
{
    cout << fixed << setprecision(6) << f();
    return 0;
}
</iomanip></string></iostream>

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 31: Developing Programming Habits in 21 Days - C++ Problem Solving Day 2

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. Learning C++ Programming from Scratch, Day 386: Solving the Number of Interception Systems for Missiles; Question Bank Answers; Fourth Method
  4. The 16th Blue Bridge Cup C++ Provincial Competition Questions for Youth Group
  5. QT C++ Practical: Implementation of a Draggable Chart Component System
  6. In-Depth Understanding of C++ Lambda Expressions: Reference Capture Principles, Usage, and Potential Pitfalls
  7. Breaking Communication Barriers: MIMO Self-Organizing Networks Pave the Way for Future Emergency Solutions!

Leave a Comment