ในปัญหานี้ เราได้รับค่า A, B และ N สามค่า หน้าที่ของเราคือค้นหาจำนวนเต็มบวก n ตัวที่ตรงตามสมการที่กำหนด
คำอธิบายปัญหา − เราจำเป็นต้องหาค่าบวก N ที่ตรงกับสมการทั้งสอง
x12 + x22 + … xn2 ≥ A x1 + x2 + … xn ≤ B
พิมพ์ค่า n หากมี หรือพิมพ์ -1
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
N = 4, A = 65, B = 16
ผลลัพธ์
1 1 1 8
คำอธิบาย
สมการคือ −
12 + 12 + 12 + 82 = 1 + 1 + 1 + 64 = 67 ≥ 65 1 + 1 + 1 + 8 = 11 < 16
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาง่ายๆ คือการเพิ่มผลรวมกำลังสองให้ได้มากที่สุด แนวคิดคือการใช้ตัวเลขหนึ่งเป็นตัวเลขหลักเพื่อเพิ่มผลรวมกำลังสองสูงสุดและใช้อีกจำนวนหนึ่งเป็น 1 ดังนั้นการใช้ตัวเลขนี้จะทำให้ผลรวมกำลังสองสูงสุดและเป็นไปตามเงื่อนไขผลรวม
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
void findNintegers(int N, int A, int B) {
vector<int> numbers;
for (int i = 0; i < N - 1; i++)
numbers.push_back(1);
if (B - (N - 1) <= 0) {
cout << "-1";
return;
}
numbers.push_back(B - (N - 1));
int vals = 0;
for (int i = 0; i < N; i++)
vals += numbers[i] * numbers[i];
if (vals < A) {
cout << "-1";
return;
}
for (int i = 0; i < N; i++)
cout << numbers[i] << " ";
}
int main(){
int N = 4, A = 65, B = 17;
cout<<N<<" positive integers that satisfy the given equations are ";
findNintegers(N, A, B);
return 0;
} ผลลัพธ์
4 positive integers that satisfy the given equations are 1 1 1 14
