codeforces-scrape

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

1038B.md (1517B)


      1 Source: https://codeforces.com/problemset/problem/1038/B
      2 
      3 B. Non-Coprime Partition
      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 Find out if it is possible to partition the first $n$ positive integers into two non-empty disjoint sets $S_1$ and $S_2$ such that:
     22 
     23 $\mathrm{gcd}(\mathrm{sum}(S_1), \mathrm{sum}(S_2)) \gt 1$ 
     24 
     25 Here $\mathrm{sum}(S)$ denotes the sum of all elements present in set $S$ and $\mathrm{gcd}$ means the[greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor).
     26 
     27 Every integer number from $1$ to $n$ should be present in exactly one of $S_1$ or $S_2$.
     28 
     29 Input
     30 
     31 The only line of the input contains a single integer $n$ ($1 \le n \le 45\,000$)
     32 
     33 Output
     34 
     35 If such partition doesn't exist, print "No" (quotes for clarity).
     36 
     37 Otherwise, print "Yes" (quotes for clarity), followed by two lines, describing $S_1$ and $S_2$ respectively.
     38 
     39 Each set description starts with the set size, followed by the elements of the set in any order. Each set must be non-empty.
     40 
     41 If there are multiple possible partitions — print any of them.
     42 
     43 Examples
     44 
     45 Input
     46 
     47 ```
     48 1
     49 ```
     50 
     51 Output
     52 
     53 ```
     54 No
     55 ```
     56 
     57 Input
     58 
     59 ```
     60 3
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 Yes  
     67 1 2  
     68 2 1 3
     69 ```
     70 
     71 Note
     72 
     73 In the first example, there is no way to partition a single number into two non-empty sets, hence the answer is "No".
     74 
     75 In the second example, the sums of the sets are $2$ and $4$ respectively. The $\mathrm{gcd}(2, 4) = 2 \gt 1$, hence that is one of the possible answers.