1360C.md (1799B)
1 Source: https://codeforces.com/problemset/problem/1360/C 2 3 C. Similar Pairs 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 We call two numbers $x$ and $y$ similar if they have the same parity (the same remainder when divided by $2$), or if $|x-y|=1$. For example, in each of the pairs $(2, 6)$, $(4, 3)$, $(11, 7)$, the numbers are similar to each other, and in the pairs $(1, 4)$, $(3, 12)$, they are not. 22 23 You are given an array $a$ of $n$ ($n$ is even) positive integers. Check if there is such a partition of the array into pairs that each element of the array belongs to exactly one pair and the numbers in each pair are similar to each other. 24 25 For example, for the array $a = [11, 14, 16, 12]$, there is a partition into pairs $(11, 12)$ and $(14, 16)$. The numbers in the first pair are similar because they differ by one, and in the second pair because they are both even. 26 27 Input 28 29 The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. Then $t$ test cases follow. 30 31 Each test case consists of two lines. 32 33 The first line contains an even positive integer $n$ ($2 \le n \le 50$) — length of array $a$. 34 35 The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 100$). 36 37 Output 38 39 For each test case print: 40 41 * YES if the such a partition exists, 42 * NO otherwise. 43 44 The letters in the words YES and NO can be displayed in any case. 45 46 Example 47 48 Input 49 50 ``` 51 7 52 4 53 11 14 16 12 54 2 55 1 8 56 4 57 1 1 1 1 58 4 59 1 2 5 6 60 2 61 12 13 62 6 63 1 6 3 10 5 8 64 6 65 1 12 3 10 5 8 66 ``` 67 68 Output 69 70 ``` 71 YES 72 NO 73 YES 74 YES 75 YES 76 YES 77 NO 78 ``` 79 80 Note 81 82 The first test case was explained in the statement. 83 84 In the second test case, the two given numbers are not similar. 85 86 In the third test case, any partition is suitable.