Monthly Archives: July 2016

Billing algorithm

This problem is from Codechef. I am re-wording it for more clarity.

A garments shop has “Buy 2, Get 2” offer for it’s customers. Whatever the items may be, they charge for costliest items from an order and give the cheapest ones free.
However we can divide the items into multiple orders to save more.

For example, Let us say we have 6 items with prices 200, 600, 100, 900, 800, 700. If we take them as one order, we will have to pay 3000.

6 items are divided into two groups {900,800,200,100}, {700,600} because they charge for highest price items. So the total bill would be 900+800+700+600 = 3000
Suppose we divide the items into two groups {900,800,700,600}, {200,100} we need to pay only 900+800+200+100 = 2000

Now the problem is, given a list of prices, how do we calculate the minimum amount we need to pay?

This is a simple greedy algorithm. We just need to sort all the prices in descending order and group them into 4 per order. The last order might contain less than 4 items.

Here is the C++ code for the same

Minimum number of jumps to reach top

There are N steps in a staircase, and a person can jump 5 steps at max, i.e he can jump any number of steps between 1 and 5.
What is the minumum number of jumps he has to make to reach the top?

A simple math problem which can be solved using a simple greedy approach. Try to make as many maximum jumps as possible before reaching the top. Take a smaller jump if needed at the end.

For example if there are 10 steps, he can make two maximum jumps of 5 steps each to reach the top.
If there 8 steps, First he can jump 5 steps and then jump 3 steps. So within 2 jumps, he can reach the top.

The code for this very simple. This problem can also be generalized by customizing the jump capacity to any number instead of a fixed number 5.

#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
int loc;
scanf("%d", &loc);
printf("%d\n",loc/5 + (loc%5 == 0?0:1));
return 0;
}