codeforces-scrape

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

225B.md (1376B)


      1 Source: https://codeforces.com/problemset/problem/225/B
      2 
      3 B. Well-known Numbers
      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 Numbers *k*-bonacci (*k* is integer, *k* > 1) are a generalization of Fibonacci numbers and are determined as follows:
     22 
     23 * *F*(*k*, *n*) = 0, for integer *n*, 1 ≤ *n* < *k*;
     24 * *F*(*k*, *k*) = 1;
     25 * *F*(*k*, *n*) = *F*(*k*, *n* - 1) + *F*(*k*, *n* - 2) + ... + *F*(*k*, *n* - *k*), for integer *n*, *n* > *k*.
     26 
     27 Note that we determine the *k*-bonacci numbers, *F*(*k*, *n*), only for integer values of *n* and *k*.
     28 
     29 You've got a number *s*, represent it as a sum of several (at least two) distinct *k*-bonacci numbers.
     30 
     31 Input
     32 
     33 The first line contains two integers *s* and *k* (1 ≤ *s*, *k* ≤ 109; *k* > 1).
     34 
     35 Output
     36 
     37 In the first line print an integer *m* (*m* ≥ 2) that shows how many numbers are in the found representation. In the second line print *m* distinct integers *a*1, *a*2, ..., *a**m*. Each printed integer should be a *k*-bonacci number. The sum of printed integers must equal *s*.
     38 
     39 It is guaranteed that the answer exists. If there are several possible answers, print any of them.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 5 2
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 3  
     53 0 2 3
     54 ```
     55 
     56 Input
     57 
     58 ```
     59 21 5
     60 ```
     61 
     62 Output
     63 
     64 ```
     65 3  
     66 4 1 16
     67 ```