7. COOK — SOLUTION
Task text
NOTE: A task from round 1 of the qualifications, season 2022/2023. Taken from dms.rs/informatika-osnovne-skole/
Task for grade 8.
Required prior knowledge: Data in C++, Operators in C++
For one portion, a cook needs m grams of meat for the main dish
(besides other ingredients), and for the salad
either k grams of cabbage or c grams of
beetroot.
There are M grams of meat, K grams of
cabbage and C grams of beetroot available, and there is
much more of all the other ingredients.
Write a program that reads the quantities needed for one portion
m, k, c, and then the available
quantities M, K, C, and prints
for how many whole portions (main dish and salad) the cook has enough
ingredients.
Input
Standard input contains the numbers
m, k, c, M,
K, C in this order, each in a separate line.
All numbers are integers, positive and less than 50000.
Output
Print only one unsigned integer to standard output, the number of whole portions that can be prepared.
Example 1
Input
200
250
150
2200
1400
890
Output
10
Example 2
Input
150
200
100
6100
5100
1000
Output
35
Explanation of the solution
For one complete portion we need to prepare a main dish and a salad.
First we can compute how many main dishes the cook can prepare from the available amount of meat:
M / m
Since we are looking for the number of whole portions, integer division is used. For example, if we have 2200 grams of meat, and one portion needs 200 grams, we can prepare 11 whole main dishes.
Then we compute how many salads we can prepare from cabbage and how many from beetroot.
K / k
C / c
An important detail is that for one salad we use either cabbage or beetroot. This means that the cook can make some salads from cabbage and some from beetroot. That is why these two numbers are added.
K / k + C / c
Finally, the number of complete portions is determined by the smaller of the number of possible main dishes and the number of possible salads.
min(M / m, K / k + C / c)
The function min() returns the smaller of two values.
This smaller value is exactly the maximum number of complete
portions the cook can prepare.
Idea of the algorithm
- Read the quantities needed for one portion:
m,kandc. - Read the available quantities:
M,KandC. - Compute how many main dishes can be prepared:
Pm = M / m. - Compute how many salads can be prepared from cabbage:
Pk = K / k. - Compute how many salads can be prepared from beetroot:
Pc = C / c. - Compute the total number of salads as
Ps = Pk + Pc. - Take the minimum of the number of main dishes and the total number of salads.
- Print the number obtained.
The key idea is that one complete portion needs both a main dish and a salad. That is why we cannot prepare more complete portions than we can prepare of either of these two parts of the meal.
Complete C++ solution
// TASK 7. COOK - SOLUTION
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int m, k, c, M, K, C;
// m - amount of meat needed for one portion
// k - amount of cabbage needed for one salad
// c - amount of beetroot needed for one salad
//
// M - available amount of meat
// K - available amount of cabbage
// C - available amount of beetroot
// Reading the data.
cin >> m >> k >> c >> M >> K >> C;
// Number of main dishes we can prepare
// from the available amount of meat.
int Pm = M / m;
// Number of salads we can prepare from cabbage.
int Pk = K / k;
// Number of salads we can prepare from beetroot.
int Pc = C / c;
// For every salad we can use either cabbage or beetroot.
// That is why the total number of possible salads is obtained by adding.
int Ps = Pk + Pc;
// A complete portion needs
// both a main dish and a salad.
// That is why we take the smaller of these two values.
int numberOfPortions = min(Pm, Ps);
// Printing the final result.
cout << numberOfPortions << endl;
return 0;
}
Code explanation
1. Program headers
The header <iostream> enables working with standard
input and output, i.e. using the statements cin and
cout.
The header <algorithm> is needed because of the function
min(), which is used at the end of the program.
2. Reading the data
The statement
cin >> m >> k >> c >> M >> K >> C;
reads all six values.
The first three values are the quantities of ingredients needed for one portion, and the other three are the quantities available to the cook.
3. Computing the number of main dishes
We find the number of main dishes by integer division of the available amount
of meat by the amount needed for one dish:
int Pm = M / m;
For example, if M = 2200 and m = 200,
we get:
2200 / 200 = 11
So we have enough meat for 11 main dishes.
4. Computing the cabbage salads
If one salad needs k grams of cabbage, and we have
K grams, the number of cabbage salads is:
int Pk = K / k;
5. Computing the beetroot salads
In the same way we compute how many salads we can make from beetroot:
int Pc = C / c;
6. Total number of salads
Since one salad can be made either from cabbage or from beetroot,
we can use both available resources.
That is why we compute the total number of salads as:
int Ps = Pk + Pc;
For example, if we can make 5 cabbage salads and 5 beetroot salads, we can make 10 salads in total.
7. Final number of complete portions
One complete portion needs both a main dish and a salad.
That is why the final result cannot be greater than either of these two numbers.
We use the function min():
int numberOfPortions = min(Pm, Ps);
If we have ingredients for 11 main dishes and 10 salads, we can prepare only 10 complete portions.
Following the algorithm on example 1
Needed:
m = 200
k = 250
c = 150
Available:
M = 2200
K = 1400
C = 890
Number of main dishes:
Pm = 2200 / 200 = 11
Number of cabbage salads:
Pk = 1400 / 250 = 5
Number of beetroot salads:
Pc = 890 / 150 = 5
Total number of salads:
Ps = 5 + 5 = 10
Final number of complete portions:
min(11, 10) = 10
That is why the result is:
10
Following the algorithm on example 2
Needed:
m = 150
k = 200
c = 100
Available:
M = 6100
K = 5100
C = 1000
Number of main dishes:
Pm = 6100 / 150 = 40
Number of cabbage salads:
Pk = 5100 / 200 = 25
Number of beetroot salads:
Pc = 1000 / 100 = 10
Total number of salads:
Ps = 25 + 10 = 35
Final number of complete portions:
min(40, 35) = 35
That is why the result is:
35
Why is max() not used?
One possible mistake in this task is using the function
max() to choose between the number of cabbage salads and the number of
beetroot salads.
For example, if we can make 7 cabbage salads and 4 beetroot salads, it is not true that we can make only 7 salads. We can make:
7 + 4 = 11
That is why the correct line is:
Ps = Pk + Pc;
The function min() is used only at the end, when we compare
the number of main dishes with the total number of salads.
Common mistakes
1. Using max() instead of addition
Wrong:
int Ps = max(Pk, Pc);
Correct:
int Ps = Pk + Pc;
2. Forgetting the function min()
It is not enough to compute only the number of main dishes or only the number of salads.
We need both parts of a complete meal.
That is why at the end we use:
min(Pm, Ps)
3. Using real (floating-point) division
The task asks for the number of whole portions, so integer
division is needed.
For example:
890 / 150 = 5
The remaining 140 grams are not enough for another whole salad, so they are not counted.
4. Leaving out the header <algorithm>
The function min() belongs to the standard algorithms library,
so it is correct to include:
#include <algorithm>
Time and memory complexity
The program performs only a few arithmetic operations, regardless of the size of the input numbers.
That is why the time complexity is:
O(1).
The program uses only a few integer variables, so the
memory complexity is also:
O(1).
Summary of the solution
To solve the task we need to compute three basic things: how many main dishes we can make, how many salads we can make from cabbage and how many from beetroot.
Since one salad can be made either from cabbage or from beetroot, the total number of salads is the sum:
K / k + C / c
A complete portion requires both a main dish and a salad, so the final answer is the minimum of these two numbers:
min(M / m, K / k + C / c)
That is the whole essence of the task.
Back
|<
Qualifications for district competitions
