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



  1. Read the quantities needed for one portion: m, k and c.
  2. Read the available quantities: M, K and C.
  3. Compute how many main dishes can be prepared: Pm = M / m.
  4. Compute how many salads can be prepared from cabbage: Pk = K / k.
  5. Compute how many salads can be prepared from beetroot: Pc = C / c.
  6. Compute the total number of salads as Ps = Pk + Pc.
  7. Take the minimum of the number of main dishes and the total number of salads.
  8. 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