HOODIEOFFER - Editorial

PROBLEM LINK:

Contest Link

Author and Editorialist: Sanjay Reddy

DIFFICULTY:

EASY

PREREQUISITES:

Basic Programming

PROBLEM:

You are given a set of hoodies of different colors that you need to purchase. Buying a hoodie of color k makes you eligible to get another hoodie of color k for free, by availing of the Buy1-Get1 offer. All hoodies, irrespective of color, costs Rs.100/-. Find the minimum cost you pay by using Buy1-Get1offer.

EXPLANATION:

Consider a frequency array where each element stores how many hoodies of that particular color is there. There are only 26 colors (from the constraint that each color is denoted by a case-sensitive Latin character and there are 26 characters from a-z).

First of all, The first line of input contains a single line T, which represents the number of test cases. Then T lines will follow, and each contains a string S, which represents the hoodies the user needed.
We should want to output the minimum cost for each test case.

Consider two cases.
The user selects the hoodies as “ssss”

In this case, the user needs 4 hoodies of color s. One of the optimal ways is the following:

Buy the first s with cost 100, and the user can get the second s without charge. Then the user can buy the third s with cost 100, and he can get the last s without charge.

Hence, in this case the user can get 4 hoodies with only cost 200.

The user selects the hoodies as “ssvs”
In this case, the user needs 3 hoodies of color s and 1 hoodie of color v. One of the optimal ways is the following:

Buy the second s with cost 100, and the user can get the last s without charge. Then buy the v and the first s with cost 200.

Hence, in this case the user can get 4 hoodies with only cost 300.

SOLUTION:

Click Me
//Code for the problem HOODIEOFFER.
#include <bits/stdc++.h>
using namespace std;

//Declaring Main Function
int main()
{
    int t;
    cin>>t;                  //Reading the Testcases
    while(t--)
    {
        string s;
        cin>>s;              //Reading the string
        int cost=0;
        int(int i=0;i<s.length();i++)
        {
            char a=s[i];
            if(a=='0')
            {
                continue;
            }
            else
            {
                cost=cost+100;          //Increase the cost if we are unable to purchase the hoodie at a free of cost with Buy1-Get1 offer
            }
            s[i]='0';
            int temp=1;
            int(int j=i+1;j<s.length();j++)
            {
                if(a==s[j])
                {
                    temp++;
                    if(temp%2!=0)
                    {
                        cost=cost+100;   //Increase the cost if we are unable to purchase the hoodie at a free of cost with Buy1-Get1 offer
                    }
                    s[j]='0';
                }
            }
        }
        cout<<cost<<end1;            //Printing the final minimum cost
    }
    return 0;
}