이 문제에서는 3개의 배열 X, Y, Z가 주어집니다. 우리의 임무는 3개의 배열에서 요소를 갖는 특수 삼중항의 합을 찾는 프로그램을 만드는 것입니다.
특별 삼중주 다음 속성을 보유하는 특별한 유형의 삼중항입니다 -
(a, b, c):a ≤ b 및 b ≥ c, 즉, 삼중항의 중간 요소는 다른 두 요소보다 더 반갑게 맞아야 합니다.
그리고, 삼중항의 값은 공식으로 주어집니다 -
f(a, b, c) = (a+b) * (b+c)
이 삼중항을 생성하려면 주어진 세 개의 배열에서 서로 하나의 요소를 사용해야 합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력 -
X[] = {5, 9, 4} ; Y[] = {8, 6} ; Z[] = {7, 1} 출력
설명 − 모든 특수 삼중항의 값을 찾아봅시다.
(5, 8, 7) : value = (5+8) * (8+7) = 195 (5, 8, 1) : value = (5+8) * (8+1) = 117 (4, 8, 7) : value = (4+8) * (8+7) = 180 (4, 8, 1) : value = (4+8) * (8+1) = 108 (5, 6, 1) : value = (5+6) * (6+1) = 77 (4, 6, 1) : value = (4+6) * (6+1) = 70 Sum of special triplets = 747
이 문제에 대한 간단한 해결책은 어레이에서 모든 삼중항을 생성하는 것입니다. 모든 특수 삼중항의 경우 위 공식을 사용하여 값을 계산합니다. 그런 다음 합계 변수에 추가하고 최종 합계를 반환합니다.
예시
솔루션을 설명하는 프로그램,
#include <iostream>
using namespace std;
int findSpecialTripletSum(int X[], int Y[], int Z[], int sizeX, int sizeY, int sizeZ) {
int sum = 0;
for (int i = 0; i < sizeX; i++) {
for (int j = 0; j < sizeY; j++) {
for (int k = 0; k < sizeZ; k++) {
if (X[i] <= Y[j] && Z[k] <= Y[j])
sum = sum + (X[i] + Y[j]) * (Y[j] + Z[k]);
}
}
}
return sum;
}
int main() {
int X[] = {5, 9, 4};
int Y[] = {8, 6};
int Z[] = {7, 1};
int sizeX = sizeof(X) / sizeof(X[0]);
int sizeY = sizeof(Y) / sizeof(Y[0]);
int sizeZ = sizeof(Z) / sizeof(Z[0]);
cout<<"Sum of special triplets = "<<findSpecialTripletSum(X, Y, Z,
sizeX, sizeY, sizeZ);
} 출력
Sum of special triplets = 747
또 다른 보다 효율적인 솔루션은 배열 X와 Z를 정렬하는 것입니다. 그런 다음 배열 Y의 각 요소에 대한 특별한 삼중항 요구 사항을 충족하는 요소를 확인하십시오.
따라서 배열 Y의 인덱스 i에 있는 모든 요소, 즉 Y[i]에 대해. 배열 X {x1, x2} 및 Z {z1, z2}의 요소가 Y[i]보다 작으면
값의 합,
S = (x1+Y[i])(Y[i]+z1) + (x1+Y[i])(Y[i]+z2) + (x2+Y[i])(Y[i]+z1) + (x2+Y[i])(Y[i]+z2) S = (x1+Y[i])(Y[i]+z1+Y[i]+z2) + (x2+Y[i])(Y[i]+z1+Y[i]+z2) S = (2Y[i] + x1 + x2)(2y[i] + z1 + z2)
N =X에서 Y[i]보다 큰 요소의 수
M =Z에서 Y[i]보다 큰 요소의 수
Sx =X에서 Y[i]보다 큰 요소의 합
Sz =Z에서 Y[i]보다 큰 요소의 합
S = (N*Y[i] + Sx) * (M*Y[i] + Sz)
예시
위의 솔루션을 설명하는 프로그램,
#include <bits/stdc++.h>
using namespace std;
int tripletSumCalc(int X[], int Y[], int Z[], int prefixSumA[], int prefixSumC[], int sizeA, int sizeB, int sizeC){
int totalSum = 0;
for (int i = 0; i < sizeB; i++) {
int currentElement = Y[i];
int n = upper_bound(X, X + sizeA, currentElement) - X;
int m = upper_bound(Z, Z + sizeC, currentElement) - Z;
if (n == 0 || m == 0)
continue;
totalSum += ((prefixSumA[n - 1] + (n * currentElement)) * (prefixSumC[m - 1] + (m * currentElement)));
}
return totalSum;
}
int* findPrefixSum(int* arr, int n) {
int* prefixSumArr = new int[n];
prefixSumArr[0] = arr[0];
for (int i = 1; i < n; i++)
prefixSumArr[i] = prefixSumArr[i - 1] + arr[i];
return prefixSumArr;
}
int findSpecialTripletSum(int A[], int B[], int C[], int sizeA, int sizeB, int
sizeC){
int specialTripletSum = 0;
sort(A, A + sizeA);
sort(C, C + sizeC);
int* prefixSumA = findPrefixSum(A, sizeA);
int* prefixSumC = findPrefixSum(C, sizeC);
return tripletSumCalc(A, B, C, prefixSumA, prefixSumC, sizeA, sizeB, sizeC);
}
int main() {
int A[] = {5, 9, 4};
int B[] = {8, 6};
int C[] = {7, 1};
int sizeA = sizeof(A) / sizeof(A[0]);
int sizeB = sizeof(B) / sizeof(B[0]);
int sizeC = sizeof(C) / sizeof(C[0]);
cout<<"Sum of special triplets = "<<findSpecialTripletSum(A, B, C, sizeA, sizeB, sizeC);
} 출력
Sum of special triplets = 747