Petya and Inequiations题解

Little Petya loves inequations. Help him find n positive integers a₁, a₂, ..., a_n, such that the following two conditions are satisfied:

a₁² + a₂² + ... + a_n² ≥ xa₁ + a₂ + ... + a_n ≤ y Input

The first line contains three space-separated integers n, x and y (1 ≤ n ≤ 10⁵, 1 ≤ x ≤ 10¹², 1 ≤ y ≤ 10⁶).

Please do not use the %lld specificator to read or write 64-bit integers in С++. It is recommended to use cin, cout streams or the %I64d specificator.

Output

Print n positive integers that satisfy the conditions, one integer per line. If such numbers do not exist, print a single number "-1". If there are several solutions, print any of them.

Example Input 5 15 15 Output 4 4 1 1 2 Input 2 3 2 Output -1 Input 1 99 11 Output 11

思路：

令a₁ + a₂ + ... + a_n= y，那么现在想办法如何拆分y使得a₁² + a₂² + ... + a_n²取得最大值，当其中n-1个数都取1，剩下一个数取y-（n-1）时a₁² + a₂² + ... + a_n²取得最大值。因此，令a₁ + a₂ + ... + a_n= y时，若a₁² + a₂² + ... + a_n²大于等于x，那么存在解，且此时的a1,…,an是其中的一组解，否则不存在解。

代码：

#include <iostream> using namespace std; int main() { int64_t n,y; int64_t x; while(cin>>n>>x>>y) { if(y>=n) { int64_t temp=y-(n-1); if(temp*temp+(n-1)>=x) { cout<<temp<<endl; for(int i=0;i<n-1;i++) cout<<1<<endl; } else cout<<-1<<endl; } else cout<<-1<<endl; } return 0; }