Tutorial
Click here to download the PDF of the problems or click here to see the challenge results.
Contents:
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 }; Code 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-- ){
int coin, bottles;
cin >> coin >> bottles;
const int PRICE = 50;
if ( PRICE * bottles < coin ){
int change = coin - PRICE * bottles;
if( change >= 100 && vm_coins[1] > 0 ){
change -= 100;
vm_coins[1]--;
}
if( change >= 50 && vm_coins[2] >= change/50){
vm_coins[2] -= change / 50;
change = 0;
}
if( change > 0 ){
cout << "NO" << endl;
return 0;
}
}
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.
using namespace std;
int main(){
freopen("1.in", "r", stdin);
int N;
cin >> N;
int vm_coins[] = { 0, 0, 0 };
vector<pair<int, int> > orders;
while ( N-- ){
int coin, bottles;
cin >> coin >> bottles;
orders.push_back(make_pair(coin, bottles));
}
sort(orders.begin(), orders.end());
for( pair<int, int> order : orders ){
int coin = order.first;
int bottles = order.second;
const int PRICE = 50;
if ( PRICE * bottles < coin ){
int change = coin - PRICE * bottles;
if( change >= 100 && vm_coins[1] > 0 ){
change -= 100;
vm_coins[1]--;
}
if( change >= 50 && vm_coins[2] >= change/50){
vm_coins[2] -= change / 50;
change = 0;
}
if( change > 0 ){
cout << "NO" << endl;
exit(0);
}
}
vm_coins[coin==200 ? 0 : (coin==100 ? 1 : 2)]++;
}
cout << "YES" << endl;
return 0;
}Code language: PHP (php)
