# Codeforces Round #636 (Div. 3) 解题报告

A. Candies
Recently Vova found n candy wrappers. He remembers that he bought x candies during the first day, 2x candies during the second day, 4x candies during the third day, …, 2k−1x candies during the k-th day. But there is an issue: Vova remembers neither x nor k but he is sure that x and k are positive integers and k>1.

Vova will be satisfied if you tell him any positive integer x so there is an integer k>1 that x+2x+4x+⋯+2k−1x=n. It is guaranteed that at least one solution exists. Note that k>1.

You have to answer t independent test cases.

Input
The first line of the input contains one integer t (1≤t≤104) — the number of test cases. Then t test cases follow.
The only line of the test case contains one integer n (3≤n≤109) — the number of candy wrappers Vova found. It is guaranteed that there is some positive integer x and integer k>1 that x+2x+4x+⋯+2k−1x=n.

Output
Print one integer — any positive integer value of x so there is an integer k>1 that x+2x+4x+⋯+2k−1x=n.

``````
int T;
long long calc,n;
int main()
{
for (register int i=1;i<=30;++i) // 计算30次即可满足所有n对应的要求
calc[i]=calc[i-1]+pow((long long)2,i-1); // 预处理所有可能的 “A”
{
for (register int i=2;i<=30;++i)
{
if(n%calc[i]==0)
{
printf("%lld\n",n/calc[i]);
break;
}
}
}
return 0;
}

``````

B. Balanced Array
You are given a positive integer n, it is guaranteed that n is even (i.e. divisible by 2).

You want to construct the array a of length n such that:

• The first n/2 elements of a are even (divisible by 2);
• the second n/2 elements of a are odd (not divisible by 2);
• all elements of a are distinct and positive;
• the sum of the first half equals to the sum of the second half (∑ai (i=1,2,...,n/2) = ∑ai (i=n/2+1,...,n)).
If there are multiple answers, you can print any. It is not guaranteed that the answer exists.

You have to answer t independent test cases.

Input
The first line of the input contains one integer t (1≤t≤104) — the number of test cases. Then t test cases follow.

The only line of the test case contains one integer n (2≤n≤2⋅105) — the length of the array. It is guaranteed that that n is even (i.e. divisible by 2).

It is guaranteed that the sum of n over all test cases does not exceed 2⋅105 (∑n ≤ 2⋅105).

Output
For each test case, print the answer — "NO" (without quotes), if there is no suitable answer for the given test case or "YES" in the first line and any suitable array a1,a2,…,an (1≤ai≤109) satisfying conditions from the problem statement on the second line.

• 当 n/2 为奇数的时候，奇数个奇数的和为奇数，奇数个偶数的和为偶数，不可能存在满足题意的情况，应该输出`NO`
• 当 n/2 为偶数的时候，偶数按 2 4 6 8 ... 的顺序输出 n/2 个，并记录所有偶数和为 sum1 ，奇数按 1 3 5 7 ... 的顺序输出 n/2-1 个，并记录已输出的奇数和为 sum2 ，最后输出一个 sum2 - sum1 （一定是奇数）即可。
``````
int T,n,sum1,sum2;
int main()
{
{
sum1=sum2=0;
if((n/2)&1) { printf("NO\n"); continue; };
printf("YES\n");
for (register int i=2;i<=n;i+=2) printf("%d ",i),sum1+=i;
n>>=1;
for (register int i=1;i<n;++i) printf("%d ",2i-1),sum2+=2i-1;
printf("%d\n",sum1-sum2);
}
return 0;
}

``````

C. Alternating Subsequence
Recall that the sequence b is a a subsequence of the sequence a if b can be derived from a by removing zero or more elements without changing the order of the remaining elements. For example, if a = [1,2,1,3,1,2,1], then possible subsequences are: [1,1,1,1],  and [1,2,1,3,1,2,1], but not [3,2,3] and [1,1,1,1,2].

You are given a sequence a consisting of n positive and negative elements (there is no zeros in the sequence).

Your task is to choose maximum by size (length) alternating subsequence of the given sequence (i.e. the sign of each next element is the opposite from the sign of the current element, like positive-negative-positive and so on or negative-positive-negative and so on). Among all such subsequences, you have to choose one which has the maximum sum of elements.

In other words, if the maximum length of alternating subsequence is k then your task is to find the maximum sum of elements of some alternating subsequence of length k.

You have to answer t independent test cases.

Input
The first line of the input contains one integer t (1≤t≤104) — the number of test cases. Then t test cases follow.

The first line of the test case contains one integer n (1≤n≤2⋅105) — the number of elements in a. The second line of the test case contains n integers a1,a2,…,an (−109ai≤109,ai≠0), where ai is the i-th element of a.

It is guaranteed that the sum of n over all test cases does not exceed 2⋅105 (∑n≤2⋅105).

Output
For each test case, print the answer — the maximum sum of the maximum by size (length) alternating subsequence of a.

``````
const int MAXN=200005;
long long T,n,a[MAXN],ans,tmp;
int main()
{
{
ans=0;
a[n+1]=0;
for (register int i=1;i<=n;++i) read(a[i]);
bool flag=(a>0);
tmp=a;
for (register long long i=2;i<=n+1;++i)
{
if(flag)
{
if(a[i]>0)
{
tmp=max(tmp,a[i]);
} else {
flag=!flag;
ans+=tmp;
tmp=a[i];
}
} else {
if(a[i]<0)
{
tmp=max(tmp,a[i]);
} else {
flag=!flag;
ans+=tmp;
tmp=a[i];
}
}
}
printf("%lld\n",ans);
}
return 0;
}

``````