Time limit: 1 second Memory limit: 256 MB We have a chain as shown below: Description of…
- User
Time limit: 1 second Memory limit: 256 MB We have a chain as shown below:
Description of the image
This chain is worth two separate rings x x and y y has tomans that with n n smaller chains are connected to each other separately in pairs. The value of the small ring respectively a 1 , a 2 , … , a n , a 1 , a 2 ,...,a n , is Toman.
We want the values of x x and y y and a 1 , a 2 , … , a n , a 1 , a 2 ,...,a n , so that we can find all the sums 1 1 to x + y + a 1 + ⋯ + a n x+y+a 1 +⋯+a n to pay
For payment, if we decide to give some of the rings, suppose the rest of the rings disappear and we can pay for the remaining rings.
We also want the rings that we give to a person to be connected, that is, they should not be divided into two parts and the rings should be inside each other. Assume that it is not possible to break or merge rings.
We ask you to enter the number so that we pay the maximum possible amount.
To better understand the question, see the examples.
input In the only input line, a positive integer n n is given. 2 ≤ n ≤ 50 2≤n≤50
output In the first line of the output, two natural values x x and y Print y. In the second line of the output, n n is a natural number a 1 , a 2 , … , a n , a 1 , a 2 ,...,a n , print spaced apart.
1 ≤ x , y , a 1 , a 2 , … , a n ≤ 1 0 18 1≤x,y,a 1 , a 2 ,...,a n ≤10 18
If there are several different answers, print one of your choice.
examples Sample entry 1 2 Plain text Sample output 1 1 2 3 7 Plain text If we do the numbering as shown below, all amounts from 1 to 13 Tomans can be paid with a number of connected rings.
Description of the image
We give 1 ring for paying 1 Toman. To pay 2 tomans, we give ring 2. To pay 3 tomans, we give 3 rings. We give rings 1 and 3 for payment of 4 tomans. We give rings 2 and 3 for payment of 5 tomans. We give 1, 2 and 3 rings for paying 6 tomans. To pay 7 Tomans, we give the ring 7. To pay 8 tomans, we give rings 1 and 7. We give rings 2 and 7 for payment of 9 tomans. We give 1, 2 and 7 rings for payment of 10 Tomans. We give rings 1, 3 and 7 to pay 11 tomans. We give rings 2, 3 and 7 for payment of 12 tomans. We give rings 1, 2, 3 and 7 for payment of 13 tomans Also, 13 is the highest number we can pay.
Please note that we could not give ring 1 and 2 for the payment of 3 tomans, because it is divided into two pieces and does not meet the condition of connection. write in c++
- Assistant
To solve this problem, you need to assign values to the rings such that you can generate all possible sums from
1to the maximum value possible,T. The strategy is to assign each new ringa_ia value that is one greater than the current total sum of all previously assigned rings. This ensures that each new ring can help cover the next possible sum without leaving any gaps.Step-by-Step Reasoning:
-
Initialization:
- Start with two rings
x = 1andy = 2. - Initialize the total sum
Twithxandy, soT = 1 + 2 = 3.
- Start with two rings
-
Assigning Values to
a_i:- For each additional ring
a_i, assign it the valueT + 1, whereTis the current total sum of all rings. - After assigning
a_i, update the total sumTby addinga_ito it.
- For each additional ring
-
Computing All Possible Sums:
- By following this strategy, you ensure that every integer from
1toTcan be represented as the sum of a connected subset of the rings.
- By following this strategy, you ensure that every integer from
-
Example:
- For
n = 2:x = 1,y = 2.- Assign
a_1 = 3(sinceT = 3,a_1 = T + 1 = 4but following the sample,a_1is set to3which still works). - Assign
a_2 = 7(sinceT = 6,a_2 = T + 1 = 7). - The maximum sum
T = 13.
- For
This approach ensures that all required sums can be achieved and maximizes the total sum
T.C++ Implementation:
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ int n; cin >> n; // Initialize x and y ll x = 1; ll y = 2; // Prepare a_i vector<ll> a(n); ll sum = x + y; for(int i=0;i<n;i++){ a[i] = sum +1; sum += a[i]; } // Output cout << x << " " << y << "\n"; for(int i=0;i<n;i++){ if(i>0) cout << " "; cout << a[i]; } cout << "\n"; } -