getting wrong answer in SPOJ problem UCV2013J

general
1

here is my code

/*
Valences
submitted by 
Arjun Mishra
*/
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
long long int A;
long long int compare[21];
void function()
{long long int i;
compare[0]=1;
for(i=1;i<=20;i++)
compare[i]=(long long int)pow(2,i);
     }
int main()
{long long int N,i,a,sum=0;
function();
//for(i=0;i<=20;i++)
//cout<<compare[i]<<endl;
while(1)
{sum=0;
 cin>>N;
 if(N==0)
 return 0;
 for(i=0;i<=20;i++)
 {
 if(N>=compare[i]&&N<compare[i+1])
 {a=compare[i];
 //cout<<i<<endl;
 break;}              
 }
 //cout<<a<<endl;
 for(i=1;i<=a-1;i++)
 cin>>A;
 for(i=a;i<=N;i++)
 {cin>>A;
 sum+=A;
 //cout<<sum<<endl;
 }
 cout<<sum<<endl;
 }
 }

i don’t know why it is producing WA after 50s of execution

2

My logic is different than yours. You are making it complicated, just observe the pattern ( the leaf nos. you need to add ) by making binary trees with nodes 1 to 15.

Node Leaf

1 : 1

2 : 2

3 : 2 + 3

4 : 3 + 4

5 : 3 + 4 + 5

6 : 4 + 5 + 6

7 : 4 + 5 + 6 + 7

8 : 5 + 6 + 7 + 8

9 : 5 + 6 + 7 + 8 + 9

10 : 6 + 7 + 8 + 9 + 10

Here is my code for reference : SPOJ/UCV2013J.cpp at master · Ouditchya/SPOJ · GitHub

Regards,

Ouditchya Sinha.

3

It is very gud example of heap.
Just traverse array from middle to last and add each element into the total.
Because index of first leaf element is (N/2) and index last non-leaf element is (N/2-1).
So,the rest half array is of leaf nodes.