Race is generally organized by distance but this race will be organized by time. In order to predict the winner we will check every 2 seconds. Let’s say total race time is 7 seconds we will check for (7-1) seconds. For 7 sec : we will check who is leading at 2 sec, 4 sec, and 6 sec. Participant who is leading more number of times is winner from prediction perspective. Now our task is to predict a winner in this marathon.
Note:
1. At particular time let say at 4th second, top two (top N, in general) participants are at same distance, then in this case both are leading we’ll increase count for both(all N).
2. And after calculating at all time slices, if the number of times someone is leading, is same for two or more participants, then one who come first in input sequence will be the winner.
Ex. If participant 2 and 3 are both leading with same number, participant 2 will be the winner.
Constraints:
1 <= T <= 100
1 <= N <= 100
Input Format:
First line contains a single integer N denoting the number of participants. Second line contains a single integer T denoting the total time in seconds of this Marathon. Next N lines (for each participant) are as follows :
We have T+1 integers separated by space. First T integers are as follows :
ith integer denotes number of steps taken by the participant at the ith second.
T+1st integer denotes the distance (in meters) of each step.
Output Format:
Index of Marathon winner, where index starts with 1.
Example
Input:
3
8
2 2 4 3 5 2 6 2 3
3 5 7 4 3 9 3 2 2
1 2 4 2 7 5 3 2 4
Output:
2
Solution: In C
#include<stdio.h>
int main()
{
int n,sec,km,a[10][10],i,j,k=2,b[10],l[10],m[10],r[10],max=0,f;
scanf("%d",&n);
scanf("%d",&sec);
for(i=0;i<n;i++)
{
for(j=0;j<sec;j++)
{
scanf("%d",&a[i][j]);
}
scanf("%d",&b[i]);
}
for(i=0;i<n;i++)
{
m[i]=0;
r[i]=0;
}
while(k<=sec)
{
max=0;
for(i=0;i<n;i++)
{
l[i]=((a[i][k-2])*b[i]+(a[i][k-1]*b[i]));
m[i]=m[i]+l[i];
}
for(i=0;i<n;i++)
{
if(max < m[i]) {
max=m[i];
f=i;
}
}
r[f]=r[f]+1;
k=k+2;
max=0;
f=0;
}
for(i=0;i<n;i++)
{
if(max < r[i]) {
max=r[i];
f=i;
}
}
printf("%d\n",f+1);
}Solution: In Java
import java.io.*;
import java.util.Arrays;
class Main
{
public static void main (String[]args) throws IOException
{
BufferedReader br = new BufferedReader (new InputStreamReader (System.in));
int participants = Integer.parseInt(br.readLine ());
int seconds = Integer.parseInt(br.readLine ());
int record[][] = new int[participants][seconds + 1];
int lead[] = new int[participants];
Arrays.fill(lead, 0);
for (int i = 0; i < participants; i++)
{
String[] input = br.readLine().split(" ");
for (int j = 0; j < input.length; j++)
{
record[i][j] = Integer.parseInt(input[j]);
}
}
for (int i = 0; i < participants; i++)
{
int length = record[i][seconds];
for (int j = 0; j < seconds - 1; j++)
{
if (j != 0)
{
record[i][j] = record[i][j - 1] + (record[i][j] * length);
}
else
{
record[i][j] = (record[i][j] * length);
}
}
}
int start = (seconds % 2 == 0) ? 0 : 1;
int max = 0;
for (int i = start; i <= seconds - 2; i += 2)
{
for (int j = 0; j < max;j++)
if(max <record[j][i])
max = record[j][i];
for (int k = 0; k < participants; k++)
if (record[k][i] == max)
lead[k]++;
max = 0;
}
max = 0;
for (int i = 0; i < participants;i++)
if(max < lead[i])
max = lead[i];
for (int i = 0; i < participants; i++)
{
if (lead[i] == max)
{
System.out.println (i + 1);
break;
}
}
}
}Solution: In Python 3
import java.io.*;
import java.util.Arrays;
class Main
{
public static void main (String[]args) throws IOException
{
BufferedReader br = new BufferedReader (new InputStreamReader (System.in));
int participants = Integer.parseInt(br.readLine ());
int seconds = Integer.parseInt(br.readLine ());
int record[][] = new int[participants][seconds + 1];
int lead[] = new int[participants];
Arrays.fill(lead, 0);
for (int i = 0; i < participants; i++)
{
String[] input = br.readLine().split(" ");
for (int j = 0; j < input.length; j++)
{
record[i][j] = Integer.parseInt(input[j]);
}
}
for (int i = 0; i < participants; i++)
{
int length = record[i][seconds];
for (int j = 0; j < seconds - 1; j++)
{
if (j != 0)
{
record[i][j] = record[i][j - 1] + (record[i][j] * length);
}
else
{
record[i][j] = (record[i][j] * length);
}
}
}
int start = (seconds % 2 == 0) ? 0 : 1;
int max = 0;
for (int i = start; i <= seconds - 2; i += 2)
{
for (int j = 0; j < max;j++)
if(max <record[j][i])
max = record[j][i];
for (int k = 0; k < participants; k++)
if (record[k][i] == max)
lead[k]++;
max = 0;
}
max = 0;
for (int i = 0; i < participants;i++)
if(max < lead[i])
max = lead[i];
for (int i = 0; i < participants; i++)
{
if (lead[i] == max)
{
System.out.println (i + 1);
break;
}
}
}
}Also Checkout