codeforces-scrape

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

303A.md (2174B)


      1 Source: https://codeforces.com/problemset/problem/303/A
      2 
      3 A. Lucky Permutation Triple
      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 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Bike is interested in permutations. A permutation of length *n* is an integer sequence such that each integer from 0 to (*n* - 1) appears exactly once in it. For example, [0, 2, 1] is a permutation of length 3 while both [0, 2, 2] and [1, 2, 3] is not.
     22 
     23 A permutation triple of permutations of length *n* (*a*, *b*, *c*) is called a Lucky Permutation Triple if and only if ![](https://espresso.codeforces.com/a5c95acda2f8bfd5804d6d872b623ebd819b0d2a.png). The sign *a**i* denotes the *i*-th element of permutation *a*. The modular equality described above denotes that the remainders after dividing *a**i* + *b**i* by *n* and dividing *c**i* by *n* are equal.
     24 
     25 Now, he has an integer *n* and wants to find a Lucky Permutation Triple. Could you please help him?
     26 
     27 Input
     28 
     29 The first line contains a single integer *n* (1 ≤ *n* ≤ 105).
     30 
     31 Output
     32 
     33 If no Lucky Permutation Triple of length *n* exists print -1.
     34 
     35 Otherwise, you need to print three lines. Each line contains *n* space-seperated integers. The first line must contain permutation *a*, the second line — permutation *b*, the third — permutation *c*.
     36 
     37 If there are multiple solutions, print any of them.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 5
     45 ```
     46 
     47 Output
     48 
     49 ```
     50 1 4 3 2 0  
     51 1 0 2 4 3  
     52 2 4 0 1 3
     53 ```
     54 
     55 Input
     56 
     57 ```
     58 2
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 -1
     65 ```
     66 
     67 Note
     68 
     69 In Sample 1, the permutation triple ([1, 4, 3, 2, 0], [1, 0, 2, 4, 3], [2, 4, 0, 1, 3]) is Lucky Permutation Triple, as following holds:
     70 
     71 * ![](https://espresso.codeforces.com/a6bf1b9b57809dbec5021f65f89616f259587c07.png);
     72 * ![](https://espresso.codeforces.com/48cc13134296b68f459f69d78e0240859aaec702.png);
     73 * ![](https://espresso.codeforces.com/ac44412de7b46833e90348a6b3298f9796e3977c.png);
     74 * ![](https://espresso.codeforces.com/3825b0bb758208dda2ead1c5224c05d89ad9ab55.png);
     75 * ![](https://espresso.codeforces.com/0a72e2da40048a507839927a211267ac01c9bf89.png).
     76 
     77 In Sample 2, you can easily notice that no lucky permutation triple exists.