codeforces-scrape

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

888D.md (945B)


      1 Source: https://codeforces.com/problemset/problem/888/D
      2 
      3 D. Almost Identity Permutations
      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 A permutation *p* of size *n* is an array such that every integer from 1 to *n* occurs exactly once in this array.
     22 
     23 Let's call a permutation an almost identity permutation iff there exist at least *n* - *k* indices *i* (1 ≤ *i* ≤ *n*) such that *p**i* = *i*.
     24 
     25 Your task is to count the number of almost identity permutations for given numbers *n* and *k*.
     26 
     27 Input
     28 
     29 The first line contains two integers *n* and *k* (4 ≤ *n* ≤ 1000, 1 ≤ *k* ≤ 4).
     30 
     31 Output
     32 
     33 Print the number of almost identity permutations for given *n* and *k*.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 4 1
     41 ```
     42 
     43 Output
     44 
     45 ```
     46 1
     47 ```
     48 
     49 Input
     50 
     51 ```
     52 4 2
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 7
     59 ```
     60 
     61 Input
     62 
     63 ```
     64 5 3
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 31
     71 ```
     72 
     73 Input
     74 
     75 ```
     76 5 4
     77 ```
     78 
     79 Output
     80 
     81 ```
     82 76
     83 ```