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 ```