Algorithm

D. N Problems During K Days
time limit per test
1 second
memory limit per test
256 megabytes
problem link- https://codeforces.com/contest/1157/problem/D
input
standard input
output
standard output

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 2x2� 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�+1 problem during the next day.

More formally: let [a1,a2,…,ak][�1,�2,…,��] 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 ai�� for i� from 11 to k� should be n�;
  • ai�� should be greater than zero for each i� from 11 to k�;
  • the condition ai<ai+1≤2ai��<��+1≤2�� should be satisfied for each i� from 11 to k−1�−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.

Input

The first line of the input contains two integers n� and k� (1≤n≤109,1≤k≤1051≤�≤109,1≤�≤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 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 a1,a2,…,ak�1,�2,…,�� in the second line, where ai�� should be the number of problems Polycarp should solve during the i�-th day. If there are multiple answers, you can print any.

Examples
input
Copy
26 6
output
Copy
YES
1 2 4 5 6 8
input
Copy
8 3
output
Copy
NO
input
Copy
1 1
output
Copy
YES
1
input
Copy
9 4
output
Copy
NO

 



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 1e5 + 1;
int n, k, a[N];

int main() {
  scanf("%d %d", &n, &k);

  if(n < 1ll * k * (k + 1) / 2) {
    puts("NO");
    return 0;
  }

  for(int i = 0; i < k; ++i)
    a[i] = i + 1, n -= (i + 1);
  
  int add = n / k;
  int rem = n % k;

  for(int i = 0; i < k; ++i)
    a[i] += add;
  
  for(int i = k - 1; i > 0; --i) {
    if(rem == 0)
      break;
    
    add = min(a[i - 1] * 2 - a[i], rem);
    rem -= add;
    a[i] += add;
  }

  if(rem > 0) {
    puts("NO");
    return 0;
  }

  puts("YES");
  for(int i = 0; i < k; ++i)
    printf("%s%d", i == 0 ? "" : " ", a[i]);
  puts("");

  return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
26 6

Output

x
–
+
cmd
YES
1 2 4 5 6 8
Advertisements

Demonstration

Codeforoces Solution D. N Problems During K Days-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+