Header Ads Widget

The Theatre Problem | codechef solution

Rajnish Tripathi 12:18

Chef's friend Alex runs a movie theatre. Due to the increasing number of platforms for watching movies online, his business is not running well. As a friend, Alex asked Chef to help him maximise his profits. Since Chef is a busy person, he needs your help to support his friend Alex.

Alex's theatre has four showtimes: 12 PM, 3 PM, 6 PM and 9 PM. He has four movies which he would like to play ― let's call them A, B, C and D. Each of these movies must be played exactly once and all four must be played at different showtimes. For each showtime, the price of a ticket must be one of the following: Rs 25, Rs 50, Rs 75 or Rs 100. The prices of tickets for different showtimes must also be different.

Through his app, Alex receives various requests from his customers. Each request has the form "I want to watch this movie at this showtime". Let's assume that the number of people who come to watch a movie at a given showtime is the same as the number of requests for that movie at that showtime.

It is not necessary to accommodate everyone's requests ― Alex just wants to earn the maximum amount of money. There is no restriction on the capacity of the theatre. However, for each movie that is not watched by anyone, Alex would suffer a loss of Rs 100 (deducted from the profit).

You are given � requests Alex received during one day. Find the maximum amount of money he can earn on that day by choosing when to play which movies and with which prices.

Input

  • The first line of the input contains a single integer � denoting the number of test cases. The description of � test cases follows.
  • The first line of each test case contains a single integer �.
  • � lines follow. Each of these lines contains a character �, followed by a space and an integer �, describing a request to see the movie � at the showtime �.

Output

For each test case, print a single line containing one integer ― the maximum profit Alex can earn (possibly negative).

Finally, print a line containing one integer ― the total profit over all test cases, i.e. over � days.

Constraints

  • 1≤�≤150
  • 0≤�≤100
  • � is 'A', 'B', 'C' or 'D'
  • � is 12, 3, 6 or 9

Subtasks

Subtask #1 (30 points): it is possible to fulfill all requests

Subtask #2 (70 points): original constraints

Sample 1:

Input
Output
5
12
A 3
B 12
C 6
A 9
B 12
C 12
D 3
B 9
D 3
B 12
B 9
C 6
7
A 9
A 9
B 6
C 3
D 12
A 9
B 6
2
A 9
B 6
1
D 12
0
575
525
-25 
-200 
-400
475

Explanation:

Example case 1: The following table shows the number of people that want to watch the movies at the given showtimes:

12369
A0101
B3002
C1020
D0200

The maximum number of requests was sent for movie B at 12 PM. Therefore, we play this movie at this time and the tickets cost Rs 100. Next, we play movie D at 3 PM with ticket price Rs 75 and movie C at 6 PM with ticket price Rs 50. Finally, we have a slot for 9 PM and the only movie we can play at that time now is movie A, with ticket price Rs 25. The total profit is 3⋅100+2⋅75+2⋅50+1⋅25=300+150+100+25=575. Since each movie was watched by at least one person, there is no additional loss.

Example case 2: Just like above, we show the requests in a table:

12369
A0003
B0020
C0100
D1000

The optimal solution is to play movie A at 9 PM, movie B at 6 PM, movie C at 3 PM and movie D at 12 PM, with decreasing ticket prices in this order. The profit is 3⋅100+2⋅75+1⋅50+1⋅25=300+150+50+25=525.

Example case 3: Again, we show the requests in a table:

12369
A0001
B0010
C0000
D0000

The optimal solution is to play movie A at 9 PM with ticket price Rs 100, movie B at 6 PM with ticket price Rs 75 and the remaining two movies in any order at 12 PM and 3 PM ? either way, there will be nobody watching them. We earn 1⋅100+1⋅75=175, but we have to deduct Rs 200, so the resulting profit is 175−200=−25.

Example case 4: The optimal solution is to play movie D at 12 PM; the other three movies go unattended. We have to deduct Rs 300, so the profit is 1⋅100−300=−200.

Example case 5: Since there are no requests for any movie at any time, all movies go unattended and Alex just suffers a loss of Rs 400.

The total profit for all 5 days is 575+525−25−200−400=475.

 Code(C++):-

#include <bits/stdc++.h>
using namespace std;

int main()
{
int t;
long long int Tp = 0;
cin >> t;
while (t--)
{
int n;
cin >> n;
int m[4][4] = {0};
vector<int> M;
while (n--)
{
char c;
int t;
cin >> c >> t;
m[(t / 3) - 1][c - 'A']++;
}
for (int i = 0; i < 4; i = (i + 1) % 4)
{
int mi1 = i, mj, mi2, mx = 0;
for (int j = 0; j < 4; j++)
{
mx = max(mx, m[mi1][j]);
if (mx == m[mi1][j])
mj = j;
}
for (int j = 0; j < 4; j++)
{
mx = max(mx, m[j][mj]);
if (mx == m[j][mj])
mi2 = j;
}
if (mi1 == mi2 && m[mi1][mj] != -1)
{
M.push_back(m[mi1][mj]);
for (int j = 0; j < 4; j++)
{
m[mi1][j] = -1;
m[j][mj] = -1;
}
}
if (M.size() == 4)
break;
}
int p = 25, P = 0;
sort(M.begin(), M.end());
for (auto &i : M)
{
if (i == 0)
P -= 100;
else
P += (i * p);
p += 25;
}
Tp += P;
cout << P << "\n";
}
cout << Tp << "\n";
return 0;
}

Code(JAVA):-
import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
static ArrayList<String> list;
static void allComb(String s, String r){
if(s.length()==0){
list.add(r);
return;
}
for(int i=0;i<s.length();i++){
allComb(s.substring(0,i)+s.substring(i+1,s.length()),r+s.charAt(i));
}
}
    public static void main (String[] args) throws java.lang.Exception
    {
        // your code goes here
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        list = new ArrayList<>();
        int t = Integer.parseInt(br.readLine());
        ArrayList<Integer> res = new ArrayList<>();
        allComb("ABCD","");
        
        for(int q=0;q<t;q++){
        
         int n = Integer.parseInt(br.readLine().trim());
         int[][] a = new int[4][4];
        
         if(n==0){
         res.add(-400);
         System.out.println(-400);
         } else {
         for(int i=0;i<n;i++){
String[] s=br.readLine().split(" ");
char ch=s[0].charAt(0);
int m=Integer.parseInt(s[1]);
if(m==12){
a[ch-'A'][0]++;
}
else if(m==3){
a[ch-'A'][1]++;
}
else if(m==6){
a[ch-'A'][2]++;
}
else{
a[ch-'A'][3]++;
}
}
int max=Integer.MIN_VALUE;
for(int i=0;i<24;i++){
String curr=list.get(i);
int sum=0;
int pro=100;
List<Integer> temp=new ArrayList<>();
for(int j=0;j<4;j++){
temp.add(a[curr.charAt(j)-'A'][j]);
}
Collections.sort(temp,Collections.reverseOrder());
for(int j=0;j<4;j++){
if(temp.get(j)==0){
sum+=-100;
}
else{
sum+=temp.get(j)*pro;
pro-=25;
}
}
max=Math.max(max,sum);
}
res.add(max);
System.out.println(max);
         }
        }
        int profit=0;
for(int i=0;i<t;i++){
profit+=res.get(i);
}
System.out.println(profit);
    }
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-

Tags:

Post a Comment

0 Comments