AVG Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Hasan Jaddouh
Tester: Teja Vardhan Reddy
Editorialist: Hussain Kara Fallah

DIFFICULTY:

Cakewalk

PREREQUISITES:

NONE

PROBLEM:

Chef had a sequence of positive integers with a length of N+K. He managed to calculate the arithmetic average of all elements of this sequence (an integer value let’s denote it by V), but then, his little brother deleted K elements from it. All deleted elements had the same value. Chef still knows the remaining N elements — a sequence A_1,A_2,…,A_N. Help him with restoring the original sequence by finding the value of the deleted elements or deciding that there is some mistake and the described scenario is impossible.

Explanation:

Let’s denote the sum of the given N elements by S (S=A_1+A_2+A_3+...+A_N).

We know that the missing value ans occurred K times. So the sum of our original sequence is tot=S+K*ans. Also, the total number of elements of the original sequence is N+K. We have the mean average value of V.

V\,=\, \frac{S+K*ans}{N+K}

V*(N+K) = S+K*ans

V*(N+K) - S = K*ans

ans = \frac{V*(N+K) - S}{K}

Since the missing number is an integer that implies that K divides V*(N+K) - S

In other words (V*(N+K) - S) \, \, modulo\, K \equiv 0

In case the remainder of the division wasn’t 0 then there was some mistake and the answer is -1.

We concluded that ans = \frac{V*(N+K) - S}{K}. In some cases, we may have a negative answer (because the average given is less than the sum of given elements). Or it may be even 0 if the average was equal to the sum. In such cases, we must report that there’s some mistake as well because it’s stated that the sequence consisted of positive integers only.

SOLUTIONS:

Editorialist’s solution

2

#include
using namespace std;
int main()
{
int T;
int N,K,V,i,l,j;
int s[T];
l=-1;
int A[N];
cin>>T;
for(j=0;j<T;j++)
{
cin>>N>>K>>V;
for(i=0;i<N;i++)
{
cin>>A[i];
}

for(i=0;i<T;i++)
{
int p=0;
for(i=0;i<N;i++)
{
p=p+A[i];
}
s[j]=(V*(N+K)-p)/K;

}
}
for(i=0;i<T;i++)
{
if(s[i]>0)
cout<<s[i]<<endl;
else
cout<<l<<endl;
}
}

3

#include
using namespace std;
int main()
{
int T;
int N,K,V,i,l,j;
int s[T];
l=-1;
int A[N];
cin>>T;
for(j=0;j<T;j++)
{
cin>>N>>K>>V;
for(i=0;i<N;i++)
{
cin>>A[i];
}

for(i=0;i<T;i++)
{
int p=0;
for(i=0;i<N;i++)
{
p=p+A[i];
}
s[j]=(V*(N+K)-p)/K;

}
}
for(i=0;i<T;i++)
{
if(s[i]>0)
cout<<s[i]<<endl;
else
cout<<l<<endl;
}
}