Description

(You are allowed to view this webpage for a slightly better version: https://hackmd.io/@yurisoba/HJr-S8kLh)

Debby loves eating all kind of pastry, she also likes to make long term financial plan to optimize her savings. She would be very happy if you could help her find the most stably-priced type of pastry. As a financial expert, she has devised a way to calculate the stability.

Given n months of price data for m types of pastry, sort the pastries by their price in ascending order for each month, and record their position pm,n (i.e. the cheapest item has p=0).

The volatility of each pastry for each month Vm,i is defined as their position difference relative to the previous month.  Formally:

Find the most stable pastry by minimizing the sum of volatility of each pastry:

Break tie using the order from the original input, the type of pastry that appears first is preferred.

Debby is also an expert in programming and is very nice to give you a short C++ reference which might be useful:

// must compile with c++17 and above
#include <algorithm>
#include <vector>
struct Something {
    int a;
    int b;
};

int main()
{
    std::vector<Something> v;
    // sort a vector, use stable_sort if order has to be persisted
    std::sort(v.begin(), v.end(), [](auto& left, auto& right) {
        return left.a < right.a;
    });
    // vector is now sorted in ascending order
}

Hint: The most stable pastry is the one which its relative price position in each month changes the least.

Input

n m
[m lines x type of pastry (string)]
[n lines x [m x space separated price (unsigned int)]]

 

Output

[1 x type of pastry (string), ended with \n]

 

Sample Input  Download

Sample Output  Download

Tags

Discuss