Header Ads Widget

James and the menus solution

Rajnish 21:04

 James and the menus Problem

James visits a restaurant, looks at the menu, and realizes that there is no price on it. Since he wanted to know the prices before he orders, he looked up the restaurant online and found � different versions of the menu. He knew from experience that usually the menu which has the maximum number of items that have the maximum price on that item between the menus is the most updated one and if there are multiple menus with that condition the one with the maximum average price is the most updated one. Help him find the most updated menu.

In other words, a price on an item is good if it is the maximum price on that item among all menus, and a menu is the most updated one if it has the maximum number of good prices on it.
If there are multiple menus with the maximum number of good prices, the menu with the higher price average is the most updated one.

Input format

  • The first line contains integers � and � that denote the number of menus and the number of items on each menu respectively.
  • The next � line each contains � integers represented as ���, the ��ℎ price on the ��ℎ menu.

Output format

Print a single number denoting the number of the most updated menu.

It is guaranteed that the answer is unique.

Constraints

1≤�,�≤103

1≤���≤109

Sample Input
3 4
1 2 1 10
3 2 3 4
1 3 3 2
Sample Output
2
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

There are 4 items in this example. The maximum price for the first three items is 3 and for the last item is 10.

First menu has only one good price which is the last one, Second menu has 2 good prices on it, which are first and third items and the last menu, has 2 good prices too.

Se between second and third menus, we have to compare averages. Average of second menu is 3+2+3+44=3 and average of third menu is 1+3+3+24=2.25, so the second menu would be the answer.


Solution :-


 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fast_IO ios::sync_with_stdio(false);
#define DEBUG fprintf(stderr,"Running on Line %d in Function %s\n",__LINE__,__FUNCTION__)
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define fir first
#define sec second
#define mod 998244353
#define int long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
    char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
    int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
    if(nega==-1) return -ans;
    return ans;
}
typedef pair<int,int> pii;
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
#define N 1005
int a[N][N],cnt[N],sum[N],mx[N],n,m;
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=read(),mx[j]=max(mx[j],a[i][j]);
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cnt[i]+=a[i][j]==mx[j],sum[i]+=a[i][j];
    int id=1;
    for(int i=1;i<=n;i++)
    {
        if(cnt[i]>cnt[id]) id=i;
        else if(cnt[i]==cnt[id]&&sum[i]>sum[id]) id=i;
    }
    cout<<id<<endl;
    return 0;
}
 

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#define pcx putchar_unlocked
#define gcx getchar_unlocked
typedef int32_t ichar;
typedef int_fast64_t fint;
 
static inline fint getfi() {
  ichar c = gcx();
  while (!isdigit(c)) c = gcx();
  fint n = 0;
  while (isdigit(c)) {
    n = n * 10 + c - '0';
    c = gcx();
  }
  return n;
}
static inline void putfi(fint n, char lc) {
  if (0 == n) {
    pcx('0');
    if (lc) pcx(lc);
    return;
  }
  char s[24];
  fint rdi = 0;
  while (n) {
    s[rdi++] = '0' + n % 10;
    n /= 10;
  }
  while (rdi) pcx(s[--rdi]);
  if (lc) pcx(lc);
}
 
int main() {
  fint NM = getfi();
  fint NI = getfi();
  int PM[NM][NI];
  int MP[1000] = {
    0
  };
  float MA[1000] = {
    0
  };
 
  for (fint mi = 0; mi < NM; ++mi) {
    for (fint ii = 0; ii < NI; ++ii) {
      PM[mi][ii] = (int) getfi();
      if (PM[mi][ii] > MP[ii]) MP[ii] = PM[mi][ii];
      MA[mi] += PM[mi][ii];
    }
    MA[mi] /= NI;
  }
  int RMP[1000] = {
    0
  };
  int bestMenuScore = 0;
  float bestMenuAvg = 0;
  int ans = 0;
  for (fint mi = 0; mi < NM; ++mi) {
    for (fint ii = 0; ii < NI; ++ii) {
      if (PM[mi][ii] == MP[ii])
        ++RMP[mi];
    }
    if ((RMP[mi] > bestMenuScore) ||
      ((RMP[mi] == bestMenuScore) && (MA[mi] > bestMenuAvg))) {
      bestMenuScore = RMP[mi];
      bestMenuAvg = MA[mi];
      ans = mi + 1;
    }
  }
  putfi(ans, 0);
  return 0;
}

from collections import Counter
n, items = map(int,input().split())
menus = []
avgs = []
for i in range(n):
    menus.append(list(map(int,input().split())))
    avgs.append(sum(menus[i])/items)
cols = zip(*menus)
maxes = [col.index(max(col)) for col in cols]
mc = dict(Counter(maxes).most_common())
new_dict = {}
for key, value in mc.items():
   if value in new_dict:
       new_dict[value].append(key)
   else:
       new_dict[value]=[key]
 
max_occ = max(new_dict.keys())
if len(new_dict[max_occ]) == 1:
    print(new_dict[max_occ][0]+1)
else:
    max_avg = max([sum(menus[i])/items for i in new_dict[max_occ]])
    print(avgs.index(max_avg)+1)

Text Copied!

easycodingzone

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-

Tags: