N Problems During K Days
题意翻译
给出两个整数 $n$、$k$ 你需要构造出一个有 $k$ 项的数列 $A$ 满足以下条件:
- 对于任意的 $i\in [1,k]$,有 $A_i>0$;
- 对于任意的 $i\in (1,k]$,有$A_{i-1}<A_i\le2A_{i-1}$;
- $\sum\limits_{i=1}^kA_i=n$。
不保证有解,无解时输出 `NO`。
有解时输出一行 `YES`,之后一行输出数列 $A$。
题目描述
Polycarp has to solve exactly $ n $ problems to improve his programming skill before an important programming competition. But this competition will be held very soon, most precisely, it will start in $ k $ days. It means that Polycarp has exactly $ k $ days for training!
Polycarp doesn't want to procrastinate, so he wants to solve at least one problem during each of $ k $ days. He also doesn't want to overwork, so if he solves $ x $ problems during some day, he should solve no more than $ 2x $ problems during the next day. And, at last, he wants to improve his skill, so if he solves $ x $ problems during some day, he should solve at least $ x+1 $ problem during the next day.
More formally: let $ [a_1, a_2, \dots, a_k] $ be the array of numbers of problems solved by Polycarp. The $ i $ -th element of this array is the number of problems Polycarp solves during the $ i $ -th day of his training. Then the following conditions must be satisfied:
- sum of all $ a_i $ for $ i $ from $ 1 $ to $ k $ should be $ n $ ;
- $ a_i $ should be greater than zero for each $ i $ from $ 1 $ to $ k $ ;
- the condition $ a_i < a_{i + 1} \le 2 a_i $ should be satisfied for each $ i $ from $ 1 $ to $ k-1 $ .
Your problem is to find any array $ a $ of length $ k $ satisfying the conditions above or say that it is impossible to do it.
输入输出格式
输入格式
The first line of the input contains two integers $ n $ and $ k $ ( $ 1 \le n \le 10^9, 1 \le k \le 10^5 $ ) — the number of problems Polycarp wants to solve and the number of days Polycarp wants to train.
输出格式
If it is impossible to find any array $ a $ of length $ k $ satisfying Polycarp's rules of training, print "NO" in the first line.
Otherwise print "YES" in the first line, then print $ k $ integers $ a_1, a_2, \dots, a_k $ in the second line, where $ a_i $ should be the number of problems Polycarp should solve during the $ i $ -th day. If there are multiple answers, you can print any.
输入输出样例
输入样例 #1
26 6
输出样例 #1
YES
1 2 4 5 6 8
输入样例 #2
8 3
输出样例 #2
NO
输入样例 #3
1 1
输出样例 #3
YES
1
输入样例 #4
9 4
输出样例 #4
NO