If you are preparing for USACO, ACSL or any other competitive programming, Codeforces is a good place to practice your programing. This article contains my Python and C++ solutions for the Yogurt Sale problem 1955A, a part of Codeforces Round 938 (Div. 3).
Yogurt Sale problem
Please read the Yogurt Sale problem on Codeforces first. Make sure you understand the problem fully. Write the algorithm on paper before coding anything. For your algorithm, you can write either pseudocode or draw a flowchart.
Test cases
You can download this test case input and the expected output:
- yogurt_sale_1.in input file
- yogurt_sale_1.out output file
Programming Solution Logic
The first line of input is t, the number of test cases.
The remaining t lines contain three integers, n, a, b.
nrepresents the number of yogurts Maxim wants to buy.arepresents the price of 1 yogurt.brepresents the price of 2 yogurts on promotion.
We will look at a few of the test cases in the the input file yogurt_sale_1.in and compare the answers to the ones in the output file yogurt_sale_1.out .
CONDITION 1: If a * 2 is lesser than or equal to b, then the minimum price will be a * n.
CONDITION 2: If a * 2 is greater than b, then we will:
1. find the value of (n // 2) * b đ this is to maximize the promo cost
2. find the value of (n % 2) * a đ this is the remaining yogurts after step (1)
3. add the values in steps (1) and (2)
This is our pseudocode:
minimum_cost = 0
if a * 2 > b:
# Case 1
minimum_cost = (n // 2) * b + (n % 2) * a
else:
# Condition 2
minimum_cost = n * a
First Test Case
The first test case is 2 5 9.
We will be working with these values.
n = 2, a = 5, b = 9
Condition 2 applies, since $5 * 2 = $10, which is greater than $9.
If we buy 2 yogurts with only the promotion price, we will pay $9.
If we buy 2 yogurts with the regular price, we will pay 2 * $5 = $10.
The lesser price is $9.
Second Test Case
The second test case is 3 5 9.
Condition 2 applies, since $5 * 2 = $10, which is greater than $9.
If we buy 3 yogurts using the promotion price, we will pay $9 + $5 = $14.
If we buy all 3 yogurts with the regular price, we will pay 3 * $5 = $15.
The lesser price is $14.
Third Test Case
The second test case is 3 5 11.
Condition 1 applies, since $5 * 2 = $10, which is lesser than $11.
If we buy 3 yogurts using the promotion price, we will pay $11 + $5 = $16.
If we buy all 3 yogurts with the regular price, we will pay 3 * $5 = $15.
The lesser price is $15.
Fourth Test Case
The second test case is 4 5 11.
Condition 1 applies, since $5 * 2 = $10, which is lesser than $11.
If we buy 4 yogurts using the promotion price, we will pay $11 + $11 = $22.
If we buy all 4 yogurts with the regular price, we will pay 4 * $5 = $20.
The lesser price is $20.
Install Python or C++
If you do not have Python or C++, you should first install it. Codeforces uses Python 3.8 for evaluating your code. If you are using C++, they have versions 17 and 20.
My Python solution
# https://codeforces.com/problemset/problem/1955/A
# line 1 : t = number of test cases
# line 2 : n, a, b
t = int(input())
for _ in range(t):
n, a, b = [int(x) for x in input().split()]
minimum_cost = (n // 2) * b + (n % 2) * a if a * 2 > b else n * a
print(minimum_cost)
In this Python code, used a ternary operator to condense the if loop into one line.
minimum_cost = (n // 2) * b + (n % 2) * a if a * 2 > b else n * a
Running the Python code
Run the Python code from your Terminal. I am using macOS, but you can use any Linux-based OS as well.
Here, I am running the program, which reads the input file with 4 test cases. Later, I also viewed the contents of the output file to compare the results.
$ cat yogurt_sale_1.in | python yogurt_sale.py
9
14
15
20
$ cat yogurt_sale_1.out
9
14
15
20
My C++ solution
This is my C++ solution:
#include <iostream>
#include <cmath>
using namespace std;
// Main function
int main() {
int t;
cin >> t;
for (int i=0; i < t; i++) {
int n, a, b;
cin >> n >> a >> b;
int minimum_cost = (a * 2 > b ? floor(n / 2) * b + (n % 2 * a) : n * a);
cout << minimum_cost << "\n";
}
}
In the C++ code, we used the same logic.
In order to use the floor() function, we include the cmath library at the top.
#include <cmath>
Running the C++ code
Compile the C++ code from your Terminal. This command creates a.out.
$ g++ yogurt_sale.cpp
Now, run the test cases against a.out.
$ cat yogurt_sale_1.in | ./a.out
9
14
15
20
$ cat yogurt_sale_1.out
9
14
15
20
Submit your code
Submit your Python code and C++ code to Codeforces. When your code successfully passes all test cases, you will get a green "Accepted" message with the time taken.
Which is faster?
In the Codeforces submission page, these were the results:
Python 3 -- Time taken: 93 ms GNU C++20 (64) -- Time taken: 92 ms
What about software design, conventions and standards?
This is competitive programming. The goal is to complete the program with minimum effort and maximum efficiency. Using single character variables and ugly formatted code are okay, as long as the program runs and runs well within the scope. In the C++ code, we also shamelessly exited the program. That is fine, as long as your program works and you are able to submit it.
Later in life, when you start working in a professional environment, please beautify your ugly code, follow conventions, add comments and make your code readable. Readability and maintainability is key if you want to be a successful software engineer.
Conclusion
If there is anything you would like me to add to this article, feel free to comment below or contact me. Thanks.
Related Posts
If you have any questions, please contact me at arulbOsutkNiqlzziyties@gNqmaizl.bkcom. You can also post questions in our Facebook group. Thank you.
