Codeforces Yogurt Sale Problem in Python and C++

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.

• n represents the number of yogurts Maxim wants to buy.
• a represents the price of 1 yogurt.
• b represents 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

yogurt_sale.py

# 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.