MysteriousRestaurant
SRM 512 · 2011-05-25 · by fushar
SRM 512 · 2011-05-25 · by fushar · Brute Force, Greedy
Problem Statement
Problem Statement
A mysterious new restaurant is open in the city for only N days. Happy to hear that, Ash and Elsh would like to have lunch at the restaurant on as many days as possible.
The restaurant sells M types of dishes. Being a mysterious restaurant, it has mysterious rules for the customers:
Mysteriously, the price of each type of dish varies every day. You are given aString[] prices consisting of N elements, each containing M characters. prices[i][j] represents the price of the j-th type of dish on the i-th day, encoded as follows:
Ash and Elsh have only budget dollars allocated for having lunch in the restaurant. Return the maximum number of days they could have lunch in the restaurant.
The restaurant sells M types of dishes. Being a mysterious restaurant, it has mysterious rules for the customers:
- They can only buy one single dish per day.
- If they buy a dish of type j on the i-th day, then on the same day next week, i.e., on the (i+7)-th day, they can only buy a dish of type j.
- If they don't buy any dishes on any day, then they can't buy any dishes again from the restaurant.
Mysteriously, the price of each type of dish varies every day. You are given a
- '0' - '9': denotes the price of 0 - 9 dollars.
- 'A' - 'Z': denotes the price of 10 - 35 dollars.
- 'a' - 'z': denotes the price of 36 - 61 dollars.
Ash and Elsh have only budget dollars allocated for having lunch in the restaurant. Return the maximum number of days they could have lunch in the restaurant.
Constraints
- prices will contain between 1 and 50 elements, inclusive.
- Each element of prices will contain the same number of characters, between 1 and 50 characters, inclusive.
- Each character in prices will be '0'-'9', 'a'-'z', or 'A'-'Z'.
- budget will be between 0 and 10,000, inclusive.
Examples
0)
{"26", "14", "72", "39", "32", "85", "06"}
13
Returns: 5
The restaurant is open for 7 days. They can have lunch for 5 days, each picking the cheaper dish from the two available types. The total prices would be 2+1+2+3+2 = 10.
1)
{"26", "14", "72", "39", "32", "85", "06", "91"}
20
Returns: 8
In this case, it is better to buy the second type of dish on the first and the eighth day, so they can have lunch for the entire 8 days.
2)
{"SRM", "512"}
4
Returns: 0
They don't have sufficient budget.
3)
{"Dear", "Code", "rsHa", "veFu", "nInT", "heCh", "alle", "ngeP", "hase", "andb", "ecar", "eful"}
256
Returns: 10
4)
{"0"}
0
Returns: 1
Submissions are judged against all 143 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class MysteriousRestaurant with a public method int maxDays(vector<string> prices, int budget) · 143 test cases · 2 s / 256 MB per case