Soluție HackerRank pentru Pairwise Sum and Divide, subdomeniul Algebra, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Pairwise Sum and Divide
- Domeniu: Algebra
- Limbaj: C++14
Challenge: Pairwise Sum and Divide
Subdomeniu: Algebra (algebra)
Scor cont: 20.0 / 20
Submission status: Accepted
Submission score: 1.0
Submission ID: 464721456
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/pairwise-sum-and-divide/problem
Cerință
You are given an array of numbers. Let us denote the array with A[]. Your task is very simple. You need to find the value returned by the function text{fun}(A).
fun(A)
sum = 0
for i = 1 to A.length
for j = i+1 to A.length
sum = sum + Floor((A[i]+A[j])/(A[i]*A[j]))
return sum
In short, this function takes all distinct pairs of indexes from the array and adds the value ≤ft lfloor (A[i]+A[j] / A[i]× A[j])right rfloor to the sum. Your task is to find the sum.
Note: ≤ft lfloor (A / B) rightrfloor is the integer division function.
Input Format
The first line contains T, the number of test cases to follow.
Each test case contains two lines: the first line contains N, the size of the array, and the second line contains N integers separated by spaces.
Output Format
The output should contain exactly T lines where the i^{text{th}} line contains the answer for the i^{text{th}} test case.
Constraints
1 ≤ T ≤ 15
1 ≤ N ≤ 2 × 10^5
1 ≤ text{Sum ofNover all test cases } ≤ 2 × 10^5
1 ≤ A[i] ≤ 10^9
Sample Input
2
3
4 2 3
3
1 4 1
Sample Output
0
4
Explanation
*First Test Case:* ≤ft lfloor (6 / 8)right rfloor + ≤ft lfloor (7 / 12)right rfloor + ≤ft lfloor (5 / 6)right rfloor = 0
*Second Test Case:* ≤ft lfloor (5 / 4)right rfloor + ≤ft lfloor (2 / 1)right rfloor + ≤ft lfloor (5 / 4)right rfloor = 4
Cod sursă
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {int t;
cin>>t;
while(t--)
{
long int n;
cin>>n;
long long int a[n];
long long int s=0;
long int c1=0,c2=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
if(a[i]==1)c1++;
if(a[i]==2)c2++;
}
s+=c1*(n-1);
s+=(c2*(c2-1))/2;
cout<<s<<endl;
}
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}