NPTEL closed

Question

Voting in Siruseri

Zonal Computing Olympiad 2010

Elections are on for the Siruseri Town Council. Elections in Siruseri work in a rather odd manner. Each candidate is assigned a unique identification number. The town is divided into five zones and each zone proposes a list of candidates, in some arbitrary order, that it would like to nominate to the Council. Any candidate who is proposed by three or more zones is elected. There is no lower limit or upper limit on the size of the Council.

Your task is to to calculate how many candidates are elected to the Council, given the lists proposed by the five zones.

For example, suppose the candidates proposed by the five zones are as follows:

• Zone 1: [12,387,15,162,5]

• Zone 2: [14,162,92,387,7,748]

• Zone 3: [14,5,12,387]

• Zone 4: [17,952,12,92,398,849]

• Zone 5: [14,5,92,12,387]

In this example, 5 candidates are elected: these are [12,387,5,14,92].

Solution hint

Sort each list and then do a 5-way merge.

Input format

The first line of the input contains five integers N₁, N₂ N₃, N₄ and N₅, where N_j is the number of candidates proposed by zone j, 1 ≤ j ≤ 5. This is followed by five lines of space separated integers. For 1 ≤ j ≤ 5, line j+1 of the input has N_j integers representing the list of candidates proposed by zone j.

Output format

Your output should be a single line consisting of one integer, the total number of candidates elected to the Town Council.

Testdata

In all cases, 1 ≤ N₁, N₂, N₃, N₄, N₅ ≤ 50,000. Each candidate ID is between 1 and 50,000. Also, each individual list is guaranteed to be free of duplicate entries.

Sample Input

5 6 4 6 5
12 387 15 162 5
14 162 92 387 7 748
14 5 12 387
17 952 12 92 398 849
14 5 92 12 387

Sample Output

5

Comments

#PYTHON CODE

arr = list(map(int, input().split()))
l1=list(map(int, input().split()))
l2=list(map(int, input().split()))
l3=list(map(int, input().split()))
l4=list(map(int, input().split()))
l5=list(map(int, input().split()))
e=0;
d=0;
l1.extend(l2)
l1.extend(l3)
l1.extend(l4)
l1.extend(l5)
l1.sort()
min=l1[0];
for i in range(len(l1)):
    if(l1[i]==min):
        d=d+1;
    else:
        min=l1[i];
        if(d>=3):
            e=e+1;
        d=1;

print(e)

---

#include<stdio.h>
struct region
{
    long int num;
    long int cand[50000];
}zone[5];

void swap(struct region a[10],long int  *l,long int *green,long int i)
{
    long int temp;
    temp=a[i].cand[*l];
    a[i].cand[*l]=a[i].cand[*green];
    a[i].cand[*green]=temp;
}
void sort(struct region a[10],long int l,long int r,int i)
{
    long int yellow,green;
    if(r-l<=1)
    {
        return;
    }
    yellow=l+1;
    for(green=l+1;green<r;green++)
    {
        if(a[i].cand[green]<=a[i].cand[l])
        {
            swap(a,&yellow,&green,i);
            yellow++;
        }
    }
    yellow--;
    swap(a,&l,&yellow,i);
    sort(a,l,yellow,i);
    sort(a,yellow+1,r,i);
}
long int merge(struct region arr1[5],long int size1,long int size2,long int arr3[50000],int m,int n)
{
/* Merging */
       long int i=0;   /*Index for first array*/
long int j=0;   /*Index for second array*/
long int k=0;   /*Index for merged array*/

while( (i < size1) && (j < size2) )
{
if( arr1[m].cand[i] < arr1[n].cand[j] )
arr3[k++]=arr1[m].cand[i++];
else
arr3[k++]=arr1[n].cand[j++];
}/*End of while*/
/*Put remaining elements of arr1 into arr3*/
while( i < size1 )
arr3[k++]=arr1[m].cand[i++];
/*Put remaining elements of arr2 into arr3*/
while( j < size2 )
        {
arr3[k++]=arr1[n].cand[j++];
        }
        return k;

/*Merging completed*/

}
long int merge1(long int arr1[50000],long int size1,long int arr2[50000],long int size2,long int arr3[50000])
{
/* Merging */
       long int i=0;   /*Index for first array*/
long int j=0;   /*Index for second array*/
long int k=0;   /*Index for merged array*/

while( (i < size1) && (j < size2) )
{
if( arr1[i] < arr2[j] )
arr3[k++]=arr1[i++];
else
arr3[k++]=arr2[j++];
}/*End of while*/
/*Put remaining elements of arr1 into arr3*/
while( i < size1 )
arr3[k++]=arr1[i++];
/*Put remaining elements of arr2 into arr3*/
while( j < size2 )
        {
arr3[k++]=arr2[j++];
        }
        return k;

/*Merging completed*/

}
long int merge2(long int arr1[50000],long int size1,struct region arr2[50000],long int size2,long int arr3[50000])
{
/* Merging */
       long int i=0;   /*Index for first array*/
long int j=0;   /*Index for second array*/
long int k=0;   /*Index for merged array*/

while( (i < size1) && (j < size2) )
{
if( arr1[i] < arr2[4].cand[j] )
arr3[k++]=arr1[i++];
else
arr3[k++]=arr2[4].cand[j++];
}/*End of while*/
/*Put remaining elements of arr1 into arr3*/
while( i < size1 )
arr3[k++]=arr1[i++];
/*Put remaining elements of arr2 into arr3*/
while( j < size2 )
        {      
            arr3[k++]=arr2[4].cand[j++];
        }
        return k;
/*Merging completed*/

}

void main()
{
    long int i,j,x,k,l,y,arr3[50000],arr4[50000],arr5[50000],arr6[50000],size[5];
    long int count=1,z,candi=0;
 
    for(i=0;i<5;i++)
    {
        scanf("%ld",&(zone[i].num));
    }
    for(i=0;i<5;i++)
    {
        for(j=0;j<zone[i].num;j++)
        {
            scanf("%ld",&(zone[i].cand[j]));
        }
    }
    for(i=0;i<5;i++)
    {
                 sort(zone,0,zone[i].num,i);
   
           
    }
    for(i=0;i<5;i++)
    {
        size[i]=zone[i].num;
    }
   l= merge(zone,size[0],size[1],arr3,0,1);
   k= merge(zone,size[2],size[3],arr4,2,3);
   x =merge1(arr3,l,arr4,k,arr5);
   y=merge2(arr5,x,zone,size[4],arr6);
   for(i=0;i<y;)
   {
       z=arr6[i];
       j=i+1;
       while(arr6[j]==z)
       {
           count++;
           j++;
       }
       if(count>=3)
           candi++;
       i=j;
       count=1;
     
       
   }
   
       printf("\n%ld\n",candi);
   
   
   
   
   
   
   
   
}