GESP C++ Level 5 Practice (Greedy Algorithm Focus) luogu-P9532 [YsOI2023] Prefix Sum

Real Questions	Practice Questions	Syllabus Analysis
Level 1 Real Questions List	Level 1 Practice Questions List	Level 1-5 Syllabus Analysis
Level 2 Real Questions List	Level 2 Practice Questions List	Essential Skills for GESP/CSP Programming
Level 3 Real Questions List	Level 3 Practice Questions List
Level 4 Real Questions List	Level 4 Practice Questions List
Level 5 Real Questions List	Level 5 Practice Questions List

CSP-XL
2025 Liaoning CSP-XL Re-examination Real Questions Analysis

GESP C++ Level 5 practice questions, although titled prefix sum, actually focus on greedy algorithms, which is somewhat misleading. The difficulty level is ⭐⭐★☆☆, moderate for level 5. The difficulty rating on Luogu is Popular−

luogu-P9532 [YsOI2023] Prefix Sum

Problem Requirements

Problem Background

Ysuperman template testing machine problem.

Be careful of the beginning of autumn, be careful of Qiu Li.

Problem Description

At the beginning of autumn, there is an array of length , all numbers are positive integers, and except for the first number, all other numbers equal the sum of all previous numbers.

For example, the array could be one of the arrays at the beginning of autumn, because except for the first number , each subsequent number is the sum of the previous numbers, such as:

The second number .

The third number .

The fourth number .

The fifth number .

The sixth number .

Now, the beginning of autumn tells Qiu Li that the number exists in this array, and Qiu Li wants to know what the minimum could be, or how small the last number of the entire array could be.

Input Format

This problem has multiple sets of test data.

The first line contains a number indicating the number of test data sets.

Next lines each contain two positive integers .

Output Format

Output a total of lines, each representing the answer for each set of test data.

For a set of data , output a line with a positive integer indicating the possible minimum .

Input Output Example #1

Input #1

Output #1

2
2
4

Input Output Example #2

Input #2

Output #2

2
2
4

Input Output Example #3

Input #3

Output #3

6
6
12

Input Output Example #4

Input #4

Output #4

6
6
12

Explanation/Tip

Example 1 Explanation

The first set of data has only one possible array , so the answer is ;
The second set of data has two possible arrays, namely and , so the answer is ;
The third set of data has two possible arrays, namely and , so the answer is .

Example 2 Explanation

The first set of data has only one possible array , so the answer is ;
The second set of data has two possible arrays, namely and , so the answer is ;
The third set of data has two possible arrays, namely and , so the answer is .

Data Range

For the first data, it satisfies that cannot be divided by , or that is not a factor of , or that is odd.

For the other data, it satisfies that can be divided by , or that is a factor of .

For the other data, it satisfies that , it can be proven that under this data range the answer can be stored using an int type variable.

For the data, it satisfies that , , .

Problem Analysis

This is a Number Theory + Greedy problem. The key is to understand the growth properties of the sequence and determine its limit position in the array based on the binary factor characteristics of .

1. Problem Pattern Derivation

First, we need to analyze the generation pattern of the array . The problem states: except for the first number , all other numbers equal the sum of all previous numbers.

Let (where is a positive integer), then:

The general term formula is:

It can be seen that except for the first two terms being equal, from the third term onwards, each term is twice the previous term. This is a property of a geometric sequence with as the common ratio.

2. Problem Analysis

Given Conditions：

The length of the array is .
The number exists in the array (i.e., , where ).

Goal：

Find the minimum value of .

Derivation：

Assuming is at the position in the array (i.e., ). According to the general term formula, the relationship between the last position of the array and the position is as follows (assuming ):

To make as small as possible , we need to make the exponent as small as possible . Since is fixed, we need to make as large as possible . Conclusion: This means that the number should appear as far back in the array as possible.

3. Restriction Conditions

Although we want the position of to be as far back as possible, the value of is subject to two restrictions:

Array Length Restriction： It must be within the array, so .
Divisibility Property Restriction：From the formula it can be seen that . Because the problem requires all numbers to be positive integers , so must be an integer. This means that must be divisible by . In other words, the number of factors of 2 contained in determines how far it can be placed in the array.

4. Algorithm Process (Greedy Strategy)

Based on the above analysis, the logic for solving the problem is as follows:

Calculate the “potential” of ：

Calculate how many times can be divided by 2, denoted as cnt . Then can be placed at most at position cnt + 2 (because at this point, is odd and cannot be divided by 2 anymore).

Determine the actual position of :

The position of depends on the number of factors of 2 it has, as well as the total length of the array .

If has many factors of 2, exceeding the length of the array, then it can only optimally be placed at position (at this point, ).
If has few factors of 2, it must be placed in a relatively forward position.

Calculate the final answer :

Once the optimal position of is determined, the answer is:

Special Case Handling

: can only be , the answer is directly .
: Regardless of whether it is or , as long as is in the array, the minimum value is itself.

5. Complexity Analysis

Time Complexity： . Each test case requires to calculate the number of factors of 2 in .
Space Complexity： . Only a constant number of extra variables are used.

Example Code

#include <cmath>#include <iostream>int main() {    int T;    std::cin >> T;    while (T--) {        int n, x;        std::cin >> n >> x;        // Special case for x=1        // If x=1, since all numbers are positive integers, k can only be 1.        // The sequence can only be 1, 1, 2, 4...        // a[n] = 1 * 2^(n-2)        if (x == 1) {            // pow returns double, which may lose precision for large numbers, but within the problem range (2^18)            // is safe. A more rigorous way is to use bit manipulation: (1LL << (n - 2))            std::cout << (long long)std::pow(2, n - 2) << std::endl;            continue;        }        // Special case for n <= 2        // If n=1, a[1]=x.        // If n=2, a[2]=x (because a[2]=a[1], if x is in the array, the minimum a[2] is x).        if (n <= 2) {            std::cout << x << std::endl;            continue;        }        // Calculate how many factors of 2 are in x, denoted as cnt.        // At the same time, divide x by these factors of 2, the remaining x is the odd part (odd_part).        int cnt = 0;        while (x % 2 == 0) {            cnt++;            x /= 2;        }        // power takes max(cnt, n-2).        int power = std::max(cnt, n - 2);        // Output result        // Use long long to prevent overflow        std::cout << (long long)std::pow(2, power) * x << std::endl;    }    return 0;}

【Recommended】Mobile Version Recommended:【GESP】C++ Certification Learning Resource Summary

【Recommended】Desktop Version Recommended: GESP/CSP Examination Materials Website:https://wiki.coderli.com/ Dictionary-style resource organization, categorized for easy and quick access.