D. N Problems During K Days
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Polycarp has to solve exactly nn 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 kk days. It means that Polycarp has exactly kk days for training!
Polycarp doesn’t want to procrastinate, so he wants to solve at least one problem during each of kk days. He also doesn’t want to overwork, so if he solves xx problems during some day, he should solve no more than 2x2x problems during the next day. And, at last, he wants to improve his skill, so if he solves xx problems during some day, he should solve at least x+1x+1 problem during the next day.
More formally: let [a1,a2,…,ak][a1,a2,…,ak] be the array of numbers of problems solved by Polycarp. The ii-th element of this array is the number of problems Polycarp solves during the ii-th day of his training. Then the following conditions must be satisfied:
- sum of all aiai for ii from 11 to kk should be nn;
- aiai should be greater than zero for each ii from 11 to kk;
- the condition ai<ai+1≤2aiai<ai+1≤2ai should be satisfied for each ii from 11 to k−1k−1.
Your problem is to find any array aa of length kk satisfying the conditions above or say that it is impossible to do it.
Input
The first line of the input contains two integers nn and kk (1≤n≤109,1≤k≤1051≤n≤109,1≤k≤105) — the number of problems Polycarp wants to solve and the number of days Polycarp wants to train.
Output
If it is impossible to find any array aa of length kk satisfying Polycarp’s rules of training, print “NO” in the first line.
Otherwise print “YES” in the first line, then print kk integers a1,a2,…,aka1,a2,…,ak in the second line, where aiai should be the number of problems Polycarp should solve during the ii-th day. If there are multiple answers, you can print any.
Examples
inputCopy
26 6
outputCopy
YES 1 2 4 5 6 8
inputCopy
8 3
outputCopy
NO
inputCopy
1 1
outputCopy
YES 1
inputCopy
9 4
outputCopy
NO 思路：通过手推可以发现其实输出为NO的情况很少，只有k*(k+1)/2 > n 或者 n == 8 && k == 3 或者 n == 4 && k == 2这三种情况，所以可以直接将上述三种情况输出。接下来则是构造如何让k天里做题的数量恰好等于n，由题意易知：每天做题数量至少也要为前一天的数量+1，所以当第一天做题数量a1确定了，那么总的最少做题数为k*(k+1)/2+(a1-1)*k。所以我们可以通过这个式子算出第一天需要做多少题。让后每天做题都比前一天多做一个即可，多余的题数可以都放在最后一天做。 需要注意的是，当k==1或者k*(k+1)/2-1 == n的时候需要特判。
AC代码：
//include <bits/stdc++.h>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <time.h>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#define sdddd(x,y,z,k) scanf("%d%d%d%d", &x, &y, &z, &k)
#define sddd(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define sdd(x,y) scanf("%d%d", &x, &y)
#define sd(x) scanf("%d", &x)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
//#define mp make_pair
#define pb push_back
#define ms(x, y) memset(x, y, sizeof x)
#define lowbit(x) -x&x
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
const int maxn = 1e5 + 50;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
//typedef vector<ll> vec;
//typedef vector<vec> mat;
template <class T>
inline bool scan_d(T &ret) {
char c; int sgn;
if (c = getchar(), c == EOF) return 0;
while (c != '-' && (c<'0' || c>'9')) c = getchar();
sgn = (c == '-') ? -1 : 1;
ret = (c == '-') ? 0 : (c - '0');
while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
ret *= sgn;
return 1;
}
ll n, m;
int main()
{
cin >> n >> m;
if(m*(m+1)/2 > n || (n == 8 && m == 3) || (n == 4 && m == 2)){
cout << "NO" << endl;
return 0;
}
n -= m*(m+1)/2;
int base = n/m;
int cul = n%m;
int cu = 0;
if(n > 1 && (base+m+cul > 2*(base+m-1)))
{
cul--;
cu++;
}
cout << "YES" << endl;
rep(i, 1, m){
if(i == 1){
;
}
else{
cout << " ";
}
if(i == m)
cout << base+i+cul;
else if(i == m-1)
cout << base+i+cu;
else
cout << base+i;
}
cout << endl;
return 0;
}