UVa 12626 – I Love Pizza
Everyone loves various types of pizza: Margarita, Four cheese, Salami, Caprichosa, Neapolitan, Hawaiian, and more...
The famous pizza Margherita is named after Queen Margherita of Italy. It is said that chef Raffaele Esposito let her choose from various pizzas he specially prepared for the queen. Margherita chose this pizza to commemorate the colors of the Italian flag: red tomatoes, white cheese, and green basil.
However, some argue that Queen Margherita disliked onions, and all other pizzas had onions. She had no choice but to eat that pizza.
In our special computerized kitchen, ingredients are named with capital letters: "A", "B", "C", "D", and so on.
Therefore, to make a Margherita pizza, we need ingredients as many as the letters, specifically, "one 'M'", "three 'A's", "two 'R's", "one 'G'", "one 'I'", and "one 'T'".
For example, if we have the following ingredients:
AAAAAAMMRRTITIGGRRRRRRRR
We can make 2 MARGARITA pizzas and still have some "R" left.
Given a set of ingredients, you must state how many MARGARITA pizzas can be made. Please note that there may be leftover ingredients or unnecessary ingredients, such as "B".
Sample Inputs/Outputs
Sample Input(s) | Sample Output(s) |
---|---|
The first line contains a number N representing the number of test cases. The following N lines each represent the existing ingredients, with each ingredient consisting of uppercase English letters A to Z. Each line contains a maximum of 600 letters. | For each set of test data, output how many "MARGARITA" pizzas can be made. |
5 MARGARITA AAAAAAMMRRTITIGGRRRRRRRR AMARGITA BOLOGNESACAPRICHOSATOMATERA ABCDEFGHIJKLMNOPQRSTUVWXYZ | 1 2 0 1 0 |
Thought Process
Declare a Map to record the frequency of each character. Then, divide the map values of the six letters "M", "A", "R", "G", "I", and "T" by their respective required quantities for making one pizza. After division, determine the smallest value among the map values, which will be the answer.
Sample Code-ZeroJudge I918: I Love Pizza
#include <iostream>
#include <map>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
char pizza[6] = {'M', 'A', 'R', 'G', 'I', 'T'};
int usage[6] = {1, 3, 2, 1, 1, 1};
for (int i = 0; i<N; i++)
{
map<char, int>MAP;
string str;
cin >> str;
for (int j = 0; j<str.length(); j++)
{
MAP[str[j]]++;
}
int min = -1;
for (int j = 0; j<6; j++)
{
MAP[pizza[j]] /= usage[j];
if (MAP[pizza[j]] < min || min == -1) min = MAP[pizza[j]];
}
cout << min << "\n";
}
}
//ZeroJudge I918
//Dr. SeanXD