codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.