codeforces-scrape

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

818B.md (2063B)


      1 Source: https://codeforces.com/problemset/problem/818/B
      2 
      3 B. Permutation Game
      4 
      5 time limit per test
      6 
      7 1 second
      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 *n* children are standing in a circle and playing a game. Children's numbers in clockwise order form a permutation *a*1, *a*2, ..., *a**n* of length *n*. It is an integer sequence such that each integer from 1 to *n* appears exactly once in it.
     22 
     23 The game consists of *m* steps. On each step the current leader with index *i* counts out *a**i* people in clockwise order, starting from the next person. The last one to be pointed at by the leader becomes the new leader.
     24 
     25 You are given numbers *l*1, *l*2, ..., *l**m* — indices of leaders in the beginning of each step. Child with number *l*1 is the first leader in the game.
     26 
     27 Write a program which will restore a possible permutation *a*1, *a*2, ..., *a**n*. If there are multiple solutions then print any of them. If there is no solution then print -1.
     28 
     29 Input
     30 
     31 The first line contains two integer numbers *n*, *m* (1 ≤ *n*, *m* ≤ 100).
     32 
     33 The second line contains *m* integer numbers *l*1, *l*2, ..., *l**m* (1 ≤ *l**i* ≤ *n*) — indices of leaders in the beginning of each step.
     34 
     35 Output
     36 
     37 Print such permutation of *n* numbers *a*1, *a*2, ..., *a**n* that leaders in the game will be exactly *l*1, *l*2, ..., *l**m* if all the rules are followed. If there are multiple solutions print any of them.
     38 
     39 If there is no permutation which satisfies all described conditions print -1.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 4 5  
     47 2 3 1 4 4
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 3 1 2 4
     54 ```
     55 
     56 Input
     57 
     58 ```
     59 3 3  
     60 3 1 2
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 -1
     67 ```
     68 
     69 Note
     70 
     71 Let's follow leadership in the first example:
     72 
     73 * Child 2 starts.
     74 * Leadership goes from 2 to 2 + *a*2 = 3.
     75 * Leadership goes from 3 to 3 + *a*3 = 5. As it's greater than 4, it's going in a circle to 1.
     76 * Leadership goes from 1 to 1 + *a*1 = 4.
     77 * Leadership goes from 4 to 4 + *a*4 = 8. Thus in circle it still remains at 4.