codeforces-scrape

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

932C.md (1225B)


      1 Source: https://codeforces.com/problemset/problem/932/C
      2 
      3 C. Permutation Cycle
      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 For a permutation *P*[1... *N*] of integers from 1 to *N*, function *f* is defined as follows:
     22 
     23  ![](https://espresso.codeforces.com/98fc8e4e8550ac029076d5ab28da515b0d97985a.png) 
     24 
     25 Let *g*(*i*) be the minimum positive integer *j* such that *f*(*i*, *j*) = *i*. We can show such *j* always exists.
     26 
     27 For given *N*, *A*, *B*, find a permutation *P* of integers from 1 to *N* such that for 1 ≤ *i* ≤ *N*, *g*(*i*) equals either *A* or *B*.
     28 
     29 Input
     30 
     31 The only line contains three integers *N*, *A*, *B* (1 ≤ *N* ≤ 106, 1 ≤ *A*, *B* ≤ *N*).
     32 
     33 Output
     34 
     35 If no such permutation exists, output -1. Otherwise, output a permutation of integers from 1 to *N*.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 9 2 5
     43 ```
     44 
     45 Output
     46 
     47 ```
     48 6 5 8 3 4 1 9 2 7
     49 ```
     50 
     51 Input
     52 
     53 ```
     54 3 2 1
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 1 2 3
     61 ```
     62 
     63 Note
     64 
     65 In the first example, *g*(1) = *g*(6) = *g*(7) = *g*(9) = 2 and *g*(2) = *g*(3) = *g*(4) = *g*(5) = *g*(8) = 5
     66 
     67 In the second example, *g*(1) = *g*(2) = *g*(3) = 1