Codeforces 349A. Cinema Line Solution

 Explain:

In the problem you need to decide whether cashier can give a change to all customers if the price of the ticket is 25 rubles and there's 3 kinds of bills: 25, 50 and 100 rubles. There's no money in the ticket office in the beginning.

Let's consider 3 cases.

• Customer has 25 rubles hence he doesn't need a change.
• Customer has 50 rubles hence we have to give him 25 rubles back.
• Customer has 100 rubles hence we need to give him 75 rubles back. It can be done in 2 ways. 75=25+50 и 75=25+25+25. Notice that it's always worth to try 25+50 first and then 25+25+25. It's true because bills of 25 rubles can be used both to give change for 50 and 100 rubles and bills of 50 rubles can be used only to give change for 100 rubles so we need to save as much 25 ruble bills as possible.

The solution is to keep track of the number of 25 and 50 ruble bills and act greedily when giving change to 100 rubles — try 25+50 first and then 25+25+25.

Solution in C++:

///**********ALLAH IS ALMIGHTY************///

///AH Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh  

#include <bits/stdc++.h>

using namespace std;

int main()

{

    int n,i,a25=0,a50=0,a100=0;

    cin>>n;

    int a[n+9];

    for(i=0; i<n; i++)

    {

        cin>>a[i];

        if(a[i]==25) a25++;

        if(a[i]==50)

        {

            a50++;

            a25--;

        }

        if(a[i]==100)

        {

            if(a50>0)

            {

                a25--;

                a50--;

            }

            else

                a25=a25-3;

        }

        if(a25<0)

        {

            cout<<"NO";

            return 0;

        }

    }

    cout<<"YES"<<endl;

}