Codevita Previous Questions | Marathon Winner

Marathon Winner

LEVEL:Beginner

Description

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.

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 seperated by space.
First T integers are as follows :
ith integer denotes number of steps taken by the participant at the i-th second.
T+1st integer denotes the distance (in meters) of each step.

Output Format

Index of Marathon winner, where index starts with 1.

Example 1:

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

Example 2:

Input

4
12
2 2 6 4 3 2 4 3 5 2 6 2 3
7 3 5 7 4 3 9 3 1 6 3 2 2
1 2 4 2 5 2 4 2 7 5 3 2 4
8 9 3 4 5 1 3 4 5 2 3 4 5

Output

Example 3:

Input

5
12
2 2 6 4 3 2 4 3 5 2 6 2 3
7 3 6 2 7 3 9 3 1 6 3 2 2
1 2 3 1 5 2 4 2 7 5 3 2 4
8 9 3 4 5 2 4 7 5 2 3 4 5
1 4 7 3 9 0 7 5 7 5 8 5 9

Output

Approach

Here the main approach is take individual input as array
from that get the last element and get the sum of product of last element and other elements of the list and store it in
another list
Do it for all the inputs

Now from that list get the respective ith element from every row where i goes from 0 to end of colums

Now traverse the above list from 1 and get the max element of every row. Now traverse the row and check which index is
equal to that max element . then append max element next to the list_racers

then by using counters get the dictionary of racers which has them as keys and their occurences as values

finally get the index of max element from list one and return the value of list 2 which is at that

Note :

Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.

Beginner

Marathon Winner

LEVEL:Beginner

Description

Input Format

Output Format

Approach

Recommended Questions

Topic: Codevita Previous Questions

Beginner