Codeforces Round #618 (Div. 2)

A. Non-zero

  • time limit per test: 1 second
  • memory limit per test: 256 megabytes

Guy-Manuel and Thomas have an array $a$ of $n$ integers $[a_1,a_2,…,a_n]$. In one step they can add $1$ to any element of the array. Formally, in one step they can choose any integer index $i (1≤i≤n)$ and do $a_i:=a_i+1$.

If either the sum or the product of all elements in the array is equal to zero, Guy-Manuel and Thomas do not mind to do this operation one more time.

What is the minimum number of steps they need to do to make both the sum and the product of all elements in the array different from zero? Formally, find the minimum number of steps to make $a_1+a_2+ … +a_n≠0$ and $a_1⋅a_2⋅ … ⋅a_n≠0$.

Input

Each test contains multiple test cases.

The first line contains the number of test cases $t (1≤t≤10^3)$. The description of the test cases follows.

The first line of each test case contains an integer $n (1≤n≤100)$ — the size of the array.

The second line of each test case contains $n$ integers $a_1,a_2,…,a_n (−100≤a_i≤100)$ — elements of the array .

Output

For each test case, output the minimum number of steps required to make both sum and product of all elements in the array different from zero.

Example

input

4
3
2 -1 -1
4
-1 0 0 1
2
-1 2
3
0 -2 1

output

1
2
0
2

Note

In the first test case, the sum is $0$. If we add 1 to the first element, the array will be $[3,−1,−1]$, the sum will be equal to $1$ and the product will be equal to $3$.

In the second test case, both product and sum are $0$. If we add $1$ to the second and the third element, the array will be $[−1,1,1,1]$, the sum will be equal to $2$ and the product will be equal to $−1$. It can be shown that fewer steps can’t be enough.

In the third test case, both sum and product are non-zero, we don’t need to do anything.

In the fourth test case, after adding $1$ twice to the first element the array will be $[2,−2,1]$, the sum will be $1$ and the product will be $−4$.

Code

题意:给数组中一个元素加$1$记为一次操作,问至少需要多少次操作才能让数组元素之和、之积均不为$0$。
首先考虑积,数组中只要有元素为$0$,则积必为$0$,所以对于所有的为$0$的元素,必须进行$+1$操作。
然后考虑和,在积不为$0$的前提下,如果和为$0$,则选择任意元素进行$+1$操作即可让和不为$0$。
综上,答案为数组中$0$元素的个数$+1$。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100 + 5;
int a[MAXN];

int main() {
    // freopen("in.txt", "r", stdin);
    int T; scanf("%d", &T);
    for(int t=1; t<=T; t++) {
        int n; scanf("%d", &n);
        int ans = 0;
        for(int i=0; i<n; i++) scanf("%d", &a[i]);
        for(int i=0; i<n; i++) {
            if(a[i] == 0) {
                ans++;
                a[i] = 1;
            }
        }
        int sum = 0;
        for(int i=0; i<n; i++) sum += a[i];
        if(sum == 0) ans++;
        printf("%d\n", ans);
    }
    return 0;
}

B. Assigning to Classes

  • time limit per test: 2 seconds
  • memory limit per test: 256 megabytes

Reminder: the median of the array $[a_1,a_2,…,a_{2k+1}]$ of odd number of elements is defined as follows: let $[b_1,b_2,…,b_{2k+1}]$ be the elements of the array in the sorted order. Then median of this array is equal to $b_{k+1}$.

There are $2n$ students, the $i$-th student has skill level $a_i$. It’s not guaranteed that all skill levels are distinct.

Let’s define skill level of a class as the median of skill levels of students of the class.

As a principal of the school, you would like to assign each student to one of the $2$ classes such that each class has odd number of students (not divisible by $2$). The number of students in the classes may be equal or different, by your choice. Every student has to be assigned to exactly one class. Among such partitions, you want to choose one in which the absolute difference between skill levels of the classes is minimized.

What is the minimum possible absolute difference you can achieve?

Input

Each test contains multiple test cases. The first line contains the number of test cases $t (1≤t≤104)$. The description of the test cases follows.

The first line of each test case contains a single integer $n (1≤n≤105)$ — the number of students halved.

The second line of each test case contains $2n$ integers $a_1,a_2,…,a_{2n} (1≤a_i≤10^9)$ — skill levels of students.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output a single integer, the minimum possible absolute difference between skill levels of two classes of odd sizes.

Example

input

3
1
1 1
3
6 5 4 1 2 3
5
13 4 20 13 2 5 8 3 17 16

output

0
1
5

Note

In the first test, there is only one way to partition students — one in each class. The absolute difference of the skill levels will be $|1−1|=0$.

In the second test, one of the possible partitions is to make the first class of students with skill levels $[6,4,2]$, so that the skill level of the first class will be $4$, and second with $[5,1,3]$, so that the skill level of the second class will be $3$. Absolute difference will be $|4−3|=1$.

Note that you can’t assign like $[2,3]$, $[6,5,4,1]$ or $[]$, $[6,5,4,1,2,3]$ because classes have even number of students.

$[2]$, $[1,3,4]$ is also not possible because students with skills $5$ and $6$ aren’t assigned to a class.

In the third test you can assign the students in the following way: $[3,4,13,13,20]$,$[2,5,8,16,17]$ or $[3,8,17]$,$[2,4,5,13,13,16,20]$. Both divisions give minimal possible absolute difference.

Code

题意:将$2n$个数的数组分成两个奇数数组,并使它们中位数的差最小。
显然,最优的解法一定是让原数组两个差最小的数作为新的两个数组中间的数,直觉告诉我排完序之后选$a[n-1]$和$a[n]$就好……

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;
int a[2 * MAXN];

int main() {
    // freopen("in.txt", "r", stdin);
    int T; scanf("%d", &T);
    for(int t=1; t<=T; t++) {
        int n; scanf("%d", &n);
        for(int i=0; i<2*n; i++) scanf("%d", &a[i]);
        sort(a, a + 2 * n);
        printf("%d\n", a[n]-a[n-1]);
    }
    return 0;
}

C. Anu Has a Function

  • time limit per test: 1 second
  • memory limit per test: 256 megabytes

Anu has created her own function $f: f(x,y)=(x|y)−y$ where $|$ denotes the bitwise OR operation. For example, $f(11,6)=(11|6)−6=15−6=9$. It can be proved that for any nonnegative numbers $x$ and $y$ value of $f(x,y)$ is also nonnegative.

She would like to research more about this function and has created multiple problems for herself. But she isn’t able to solve all of them and needs your help. Here is one of these problems.

A value of an array $[a_1,a_2,…,a_n]$ is defined as $f(f(…f(f(a_1,a_2),a_3),…a_{n−1}),a_n)$ (see notes). You are given an array with not necessarily distinct elements. How should you reorder its elements so that the value of the array is maximal possible?

Input

The first line contains a single integer $n$ ($1≤n≤105$).

The second line contains $n$ integers $a_1,a_2,…,a_n$ ($0≤a_i≤10^9$). Elements of the array are not guaranteed to be different.

Output

Output $n$ integers, the reordering of the array with maximum value. If there are multiple answers, print any.

Examples

input 1

4
4 0 11 6

output 1

11 6 4 0

input 2

1
13

output 2

13

Note

In the first testcase, value of the array $[11,6,4,0]$ is $f(f(f(11,6),4),0)=f(f(9,4),0)=f(9,0)=9$.

$[11,4,0,6]$ is also a valid answer.

Code

题意:给你一个数组,对数组进行排序,给出一个能让$f(f(…f(f(a_1,a_2),a_3),…a_{n−1}),a_n)$结果最大的排列,其中$f: f(x,y)=(x|y)−y$。
比赛的时候疯狂WA,但是最终还是没有过……其实感觉想法已经很靠近了。
首先可以分析出,只有在$x[i]=1$并且$y[i]=1$时,$y$才会对$x$产生影响。其他情况下,$x$在经过$f(x,y)$的变换之后,不会产生变化。
一切操作都是对于第一个$x$进行的,所以选择一个数作为$a[0]$格外重要。事实上确实只需要确定$a[0]$,其他数字的排列可以任意
根据上面的结论,当某一个数字$x$的某一位$x[i]$是所有数字第$i$位中唯一的一个$1$时,以它作为前一个操作数,它的$1$才能保留,否则这个$1$一定在函数运算后变为$0$。而这个$1$所在的位置很显然是越高位越好。所以我们从高位至低位遍历数组,第一个遇到的该位唯一的一个$1$,则说明这个数应当作为$a[0]$。剩下的数随意排列。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;
int a[MAXN];

int main() {
    // freopen("in.txt", "r", stdin);
    int n; scanf("%d", &n);
    for(int i=0; i<n; i++) scanf("%d", &a[i]);
    for(int i=30; i>=0; i--) {
        int cnt = 0, first = 0;
        for(int j=0; j<n; j++) {
            int x = ((a[j] >> i) & 1);
            if(x == 1) {
                first = j;
                cnt++;
            }
        }
        if(cnt == 1) {
            printf("%d ", a[first]);
            for(int i=0; i<n; i++) if(i != first) printf("%d ", a[i]);
            return 0;
        }
    }
    for(int i=0; i<n; i++) printf("%d ", a[i]);
    return 0;
}

D. Aerodynamic

  • time limit per test: 1 second
  • memory limit per test: 256 megabytes
    Guy-Manuel and Thomas are going to build a polygon spaceship.

You’re given a strictly convex (i. e. no three points are collinear) polygon $P$ which is defined by coordinates of its vertices. Define $P(x,y)$ as a polygon obtained by translating $P$ by vector $\vec{(x,y)}$. The picture below depicts an example of the translation:

Define $T$ as a set of points which is the union of all $P(x,y)$ such that the origin $(0,0)$ lies in $P(x,y)$ (both strictly inside and on the boundary). There is also an equivalent definition: a point $(x,y)$ lies in T only if there are two points $A$,$B$ in $P$ such that $\vec{AB}=\vec(x,y)$. One can prove $T$ is a polygon too. For example, if $P$ is a regular triangle then $T$ is a regular hexagon. At the picture below $P$ is drawn in black and some $P(x,y)$ which contain the origin are drawn in colored:

The spaceship has the best aerodynamic performance if $P$ and $T$ are similar. Your task is to check whether the polygons $P$ and $T$ are similar.

Input

The first line of input will contain a single integer $n$ ($3≤n≤105$) — the number of points.

The $i$-th of the next $n$ lines contains two integers $x_i$,$y_i$ ($|x_i|,|y_i|≤10^9$), denoting the coordinates of the $i$-th vertex.

It is guaranteed that these points are listed in counterclockwise order and these points form a strictly convex polygon.

Output

Output “YES” in a separate line, if $P$ and $T$ are similar. Otherwise, output “NO” in a separate line. You can print each letter in any case (upper or lower).

Examples

input 1

4
1 0
4 1
3 4
0 3

output 1

YES

input 2

3
100 86
50 0
150 0

output 2

NO

input 3

8
0 0
1 0
2 1
3 3
4 6
3 6
2 5
1 3

output 3

YES

Note

The following image shows the first sample: both $P$ and $T$ are squares. The second sample was shown in the statements.

Code

题意:给你一些点,顺时针顺序连成一个多边形。在平面直角坐标系上平移这个多边形,要求原点必须在多边形内部。求平移所覆盖到的多边形区域是否与原多边形相似。
通过手画可以得出如果这个图形关于某点中心对称于本身,那么输出YES,否则输出NO。
至于证明……orz(逃。
判断中心对称的方法:首先,如果是奇数个点,肯定无法中心对称。如果是偶数个点,找出两个关于对称中心对称的点求出对称中心,判断多边形上每一对点是否都关于对称中心对称即可。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;
int x[MAXN], y[MAXN];

int main() {
    // freopen("in.txt", "r", stdin);
    int n; scanf("%d", &n);
    for(int i=0; i<n; i++) scanf("%d %d", &x[i], &y[i]);
    if(n & 1) {
        printf("NO\n");
        return 0;
    }
    int x0 = x[0] + x[n/2], y0 = y[0] + y[n/2];
    for(int i=0; i<n/2; i++) {
        if(x[i]+x[n/2+i]!=x0 || y[i]+y[n/2+i]!=y0) {
            printf("NO\n");
            return 0;
        }
    }
    printf("YES\n");
    return 0;
}

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇