Much-Match-March! Challenge Tutorial

Tutorial

Click here to download the PDF of the problems or click here to see the challenge results.

Contents:

• Problem A: Babies Matching Game
• Problem B: Teens Matching Game
• Problem C: Adults Don’t Match
• Problem D: Vending Machine
• Problem E: Fixing the Vending Machine

Problem A: Babies Matching Game

This problem requires a typical application of an if-then-else block. After inputting the number (N) as an integer, the response can be evaluated as follows:

if( N % 15 == 0 ) cout << "Much-Match-March!" << endl;
else if( N % 3 == 0 ) cout << "March!" << endl;
else if( N % 5 == 0 ) cout << "Much!" << endl;
else cout << "Match!" << endl;Code language: JavaScript (javascript)

Notice how you need to check if the number is divisible by both 3 and 5 (line 1) before checking if it is divisible by only 3 (line 2) or only 5 (line 3).

Problem B: Teens Matching Game

This problem has two parts: (1) calculating the sum and product of individual digits of a number, and (2) compare which of the two quantities is greater.

Part (1) can be solved in a number of ways. One useful method is to see a number as a collection of digits. This means that we can first input the number as a string.

string N;
cin >> N;

Then, we can go over each digit of the number (which are now stored as characters of the string) and sum/multiply them. Before we can sum/multiply individual digits, we will need to convert them to numbers. This can easily be achieved by using the ASCII code values of the characters.

int sum = 0, product = 1;
for( int i = 0; i < N.size(); i++ ){
    sum += N[i] - '0';
    product *= N[i] - '0';
}Code language: HTML, XML (xml)

At this point, sum and product can be compared, which is Part (2) of the problem. This part is similar to Problem A above as well as this problem from Challenge 06.

Problem C: Adults Don’t Match

This problem is similar to problems A and B above. The unique challenge here is how to reverse the digits of the number. If we input a number as a string as follows.

string NS;
cin >> NS;

The reverse of the number in string can be computed by going over the digits of the number from its end to the beginning and adding the digits to the reverse number.

string RNS = "";
for( int i = NS.size()-1; i >= 0; i--){
    RNS += NS[i];
}Code language: JavaScript (javascript)

Then, we can convert the two strings to their integer equivalent using stoi() function.

int N = stoi(NS);
int RN = stoi(RNS);

Then the two quantities can be compared like in Problem B above.

Problem D: Vending Machine

This is a simulation problem similar to Mike’s Puzzle problem we solved in Challenge 06. Again, the challenge here is to track all the relevant data and simulate the operation of selling water bottles to students.

A good question to always ask is, what information needs to be tracked throughout the operation of the vending machine. Clearly, it is:

• how many coins of each type (50, 100, and 200) are in the vending machine. This will help us compute total sales as well as if it is possible to return change to the next student.
• how many bottles are left (since the problem wants us to assume that the vending machine will always have enough bottles, this will not be necessary to track).

We can use an array to track available coins.

int vm_coins[] = { 0, 0, 0 }; // 1st:50, 2nd:100, 3rd:200Code language: JavaScript (javascript)

Then, we can serve one student at a time. For each student, we will get his/her coin and how many bottles he/she wants to buy. If the student needs a change (e.g. has a 100-coin and wants a single bottle), then we can check in the coins tracker, if we have enough coins to return the change. If we can return the change, we will remove the coins that will be used to return the change and add the new coin. If we cannot return the change, then we can stop here, report as “NO”, and terminate the program.

If we can repeat the above for all students, then we will report as “YES”.

Note that, in this case, since only 50, 100, and 200 are used, change can only be needed for a student who has 100 or 200 coin. Hence, change that need to be returned can only be either TZS 50, 100, or 150. For this reason, the coins that are needed to return change are only 50 and 100. We will use this knowledge to quickly determine the coins to use to return a change.

Hence, suppose we store the total students in an integer, N, we can implement the above process with a simple loop:

while ( N-- ){
    // Get the coin and bottles for the next order
    int coin, bottles;
    cin >> coin >> bottles;

    // When change needs to be returned
    const int PRICE = 50;
    if ( PRICE * bottles < coin ){
        // Calculate the change
        int change = coin - PRICE * bottles; 

        // Compute if 100s are needed and available to be returned as change
        if( change >= 100 && vm_coins[1] > 0 ){
            change -= 100;
            vm_coins[1]--;
        }

        // Compute if the remaining change can be returned using 50s
        if( change >= 50 && vm_coins[2] >= change/50){
            vm_coins[2] -= change / 50;
            change = 0;
        }

        // When returning a change cannot be done
        if( change > 0 ){
            cout << "NO" << endl;
            return 0;
        }
    }

    // Add the coin to the vending machine
    vm_coins[coin==200 ? 0 : (coin==100 ? 1 : 2)]++;
}

cout << "YES" << endl;Code language: JavaScript (javascript)

Problem E: Fixing the Vending Machine

This problem is similar to Problem D above. However, in this case, we need to rearrange the students in the best way to serve them.

The question then becomes, “What is the best way to rearrange the students before serving them?”. If you think about it, the best approach is to serve all students who do not need change first. Then, we can serve those who need some change. We can achieve this by sorting the students from those with the smaller coin (50) to those with the largest coin (200).

Since we need to sort the students, we will need to store all of them (i.e. keep a list of each student’s coin and the number of bottles). C++ has a data structure called pair that stores two things as a single item. Each pair will belong to one student. We can store all the pairs in an array or vector. For the sake of learning, we will use a vector.

Hence, as a summary, we will get all students orders into a list. Then, we will sort them according to their coins (from smallest to largest). Then, we will try to serve the orders exactly as we did in Problem D above.

The above can be implemented as followed. A complete source code is provided to showcase a good way to write and organize source code. The source code is heavily commented on to help you follow along.

#include<iostream>  // pair, exit(), cin, cout, endl
#include<cstdio>  // freopen(), stdin, stdout
#include<vector>   // vector
#include<algorithm>   // sort()

using  namespace std;

int main(){
    // For easy debugging
    freopen("1.in", "r", stdin);
    //freopen("1.out", "w", stdout);

    // Get students count
    int N;
    cin >> N;

    // Tracks coins in the vending machine (1st:50, 2nd:100, 3rd:200)
    int vm_coins[] = { 0, 0, 0 };

    // Get all students orders
    vector<pair<int, int> > orders;
    while ( N-- ){
        int coin, bottles;
        cin >> coin >> bottles;
        orders.push_back(make_pair(coin, bottles));
    }

    // Sort students orders. By default, sorting pairs chooses the first item
    // in the pair, and also sorts the items from smallest to largest
    sort(orders.begin(), orders.end());

    // Try to serve each student's order
    for( pair<int, int> order : orders ){  // C++11 or above is needed for shorthand for loop
        int coin = order.first;  // Get coin from the current student's order
        int bottles = order.second;  // Get the number of bottles

        // When change needs to be returned
        const int PRICE = 50;
        if ( PRICE * bottles < coin ){
            int change = coin - PRICE * bottles; // Calculate the change

            // Compute if 100s are needed and available to be returned
            if( change >= 100 && vm_coins[1] > 0 ){
                change -= 100;
                vm_coins[1]--;
            }

            // Compute if the remaining change can be returned using 50s
            if( change >= 50 && vm_coins[2] >= change/50){
                vm_coins[2] -= change / 50;
                change = 0;
            }

            // When returning a change cannot be done
            if( change > 0 ){
                cout << "NO" << endl;
                exit(0);  // Terminate the program. Also, "return 0;" can be used
            }
        }

        // Add the new coin to the vending machine
        vm_coins[coin==200 ? 0 : (coin==100 ? 1 : 2)]++;
    }

    cout << "YES" << endl;

    return 0;
}Code language: PHP (php)