Class Average

PROBLEM :

There is this renowned University named Fibonacci University. It is perfect in all aspects. However it has a rule which is completely different from any other school or University - its marking system. The rule says:

1) Allot marks to each and every student based on his/her perfomance.

2) Multiply the marks of those students whose roll numbers are belong to fibonacci number.

3) In case the marks of any student crosses 100, divide it by 100 and take the remainder.

Professor Basu teaches Logic Design in this University. Exams are over and all the teachers are required to submit the class average of students in their particular course. However Professor Basu is sick and wants you to do the task on his behalf.

Input:

The first line of input takes the number of test case, T. Then T test cases follow .
Each test case consist of 2 lines .
The first line  of each test takes has an integer N where N is the number of students.
The second line takes N space separated integers, where  i th integer denoting the marks obtained by the student with roll number i.


Output:
For each test case print the class average (floor value) for each test case in a new line.


Constraints:
1<=T<=100

1<=N<=100

1<=Marks<=100


Example:

Input:
3
5
34 78 80 91 99
7
30 20 67 90 23 34 53
10
78 87 89 90 67 78 65 56 99 35

Output:
63
37
66

Explanation:

In the first test case, there are 5 students.
Roll No 1 gets 34. 1 is a fibonacci number and hence 34 is multiplied by 1.
Roll No 2 gets 78. 2 is a fibonacci number and hence 78 is multiplied by 2 and becomes 156 which being greater than 100 is reduced to 56.
Roll No 3 gets 80. 3 is a fibonacci number and hence 80 is multiplied by 3 and it becomes 240 which being greater than 100 is reduced to 40.
Roll No 4 gets 91. 4 is not a fibonacci number and hence 91 is kept as it is.
Roll No 5 gets 99. 5 is a fibonacci number and hence 99 is multiplied by 5 and becomes 495 which being greater than 100 is reduced to 95. The class total becomes 316 and an average of 63.2 floor of which is 63 .

The other test cases follow from the same logic.

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

#include<iostream>
#include <math.h>
using namespace std;

void multiply_rollno(int [],int ) ;
bool check_Fibonacci(int ) ;
int average_marks(int [],int ) ;

int main()
 {
int t,no,i ;
int arr[100] ;
cin>>t ;
while(t--)
{
   cin>>no ;
   for(i=0;i<no;i++)
       cin>>arr[i] ;
     
   multiply_rollno(arr,no) ;
 
   cout<<average_marks(arr,no)<<endl ;
}
return 0;
}

void multiply_rollno(int arr[],int no)
{
    int i ;
    for(i=0;i<no;i++)
    {
        if(check_Fibonacci(i+1))
        {
            arr[i]=arr[i]*(i+1) ;
            if(arr[i]>100)
                arr[i]=arr[i]%100 ;
        }
    }
}

bool check_Fibonacci(int no)
{
    if(no==1)
        return true ;
       
    int a,b,c ;
    a=1;
    b=1 ;
    c=a+b ;
   
    while(c<=no)
    {
        c=a+b ;
       
        if(c==no)
            return true ;
           
        a=b ;
        b=c ;
    }
    return false ;
}

int average_marks(int arr[],int no)
{
    int i,sum ;
    sum=0 ;
   
    for(i=0;i<no;i++)
        sum=sum+arr[i] ;
       
    return floor(sum/no) ;
}

---------------------------------------------------------------------------------