Televisores | TCS Mock Vita 2020

Descripción del problema

El Dr. Vishnu está abriendo un nuevo hospital de clase mundial en un pequeño pueblo diseñado para ser la primera preferencia de los pacientes de la ciudad. El hospital cuenta con N habitaciones de dos tipos con TV y sin TV, con tarifas diarias de R1 y R2 respectivamente. Sin embargo, por su experiencia, el Dr. Vishnu sabe que el número de pacientes no es constante a lo largo del año, sino que sigue un patrón. El número de pacientes en un día determinado del año viene dado por la siguiente fórmula:

Pacientes por día = (6 – M) ² + |D – 15|
donde,
M: el número de mes que comienza del 1 al 12
D: la fecha del 1 al 31

Todos los pacientes prefieren salas sin TV porque son más económicas, pero optarán por salas con TV solo si no hay salas sin TV disponibles. El hospital tiene un objetivo de ingresos para el primer año de funcionamiento. Dado este objetivo y los valores de N , R1 y R2 , debe identificar la cantidad de televisores que el hospital debe comprar para cumplir con el objetivo de ingresos. Suponga que el hospital abre el 1 de enero y el año no es bisiesto.

Ejemplos:

Entrada: N = 20, R1 = 1500, R2 = 1000, objetivo = 7000000
Salida: 14
Explicación:
Usando la fórmula:
El número de pacientes el 1 de enero será 39, el 2 de enero será 38 y así sucesivamente.
Teniendo en cuenta que solo hay veinte habitaciones y las tarifas de ambos tipos de habitaciones son 1500 y 1000 respectivamente.
Por lo tanto, se necesitan 14 televisores para obtener el ingreso de 7119500 con 13 televisores.
Los ingresos totales serán inferiores a 7000000.

Entrada: N = 10, R1 = 1000, R2 = 1500, objetivo = 10000000
Salida: 10
Explicación:
En el ejemplo anterior, no se logrará el objetivo, incluso equipando todas las habitaciones con TV.
Por lo tanto, la respuesta es 10, es decir, el número total de habitaciones en el hospital.

Enfoque: La idea es recorrer todo el año y generar ingresos para cada día. Encuentre los ingresos del primer año para cada número posible de habitaciones que pueden tener un televisor. Siga los pasos a continuación para resolver el problema:

1. Supongamos que el número total de habitaciones que tienen un televisor es televisores , donde 0 ≤ televisores ≤ N.
2. Para cada número de televisores, los ingresos del primer año se pueden encontrar recorriendo cada día.
3. La fórmula anterior se puede utilizar para encontrar el número de pacientes por día. Supongamos que np es el número actual de pacientes.
4. El número actual de pacientes np puede tener el valor del número de pacientes hoy o el número total de habitaciones, lo que sea mínimo.
5. Si el número de pacientes es menor que el número de habitaciones sin TV, entonces el ingreso total de hoy será np*R2 porque es barato.
6. De lo contrario, si el número de pacientes es mayor que las habitaciones sin TV, entonces el ingreso total para hoy está dado por:
   

   (N – televisores)*R2 + (np – (N – televisores))*R1

7. Agregue los ingresos de cada día en el valor objetivo e imprima el valor objetivo máximo generado después de verificar todas las combinaciones posibles.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
  
#include <bits/stdc++.h>
using namespace std;
  
// Function that returns number of
// patient for a day in a month
int getPatients(int M, int D)
{
    return ((6 - M) * (6 - M))
           + abs(D - 15);
}
  
// Function that count the TVs with
// given amount of revenue target
void countTVs(long long n, long long r1,
              long long r2, long long target)
{
    long long np, tvs, current_target;
  
    // Days in each month
    vector<int> days = { 0, 31, 28, 31,
                         30, 31, 30, 31,
                         31, 30, 31, 30,
                         31 };
  
    // Check all possible combinations
    for (tvs = 0; tvs <= n; tvs++) {
  
        // Stores the current target
        current_target = 0;
  
        for (int m = 1; m <= 12; m++) {
  
            for (int d = 1;
                 d <= days[m]; d++) {
  
                // Number of patients
                // on day d of month m
                np = getPatients(m, d);
  
                // Patients cannot be
                // exceed number of rooms
                np = min(np, n);
  
                // If the number of patient is
                // <= count of rooms without tv
                if (np <= n - tvs) {
  
                    // All patients will opt
                    // for rooms without tv
                    current_target += np * r2;
                }
  
                // Otherwise
                else {
  
                    // Some will opt for
                    // rooms with tv and
                    // others without tv
                    current_target
                        += ((n - tvs) * r2
                            + ((np - (n - tvs))
                               * r1));
                }
            }
        }
  
        // If current target meets
        // the required target
        if (current_target >= target) {
            break;
        }
    }
  
    // Print the count of TVs
    cout << min(tvs, n);
}
  
// Driver Code
int main()
{
    long long N = 20, R1 = 1500;
    long long R2 = 1000;
    long long target = 7000000;
  
    // Function Call
    countTVs(N, R1, R2, target);
  
    return 0;
}

14

Complejidad de tiempo: O(N*365), donde N es el número dado de habitaciones.
Espacio Auxiliar: O(1)