Eres un pobre en una isla. Solo hay una tienda en esta isla, esta tienda está abierta todos los días de la semana excepto los domingos. Considere las siguientes restricciones:
- N – Unidad máxima de alimentos que puedes comprar cada día.
- S: número de días que debe sobrevivir.
- M – Unidad de alimento requerida cada día para sobrevivir.
Actualmente, es lunes y necesita sobrevivir durante los próximos S días.
Encuentra el número mínimo de días en los que necesitas comprar comida en la tienda para poder sobrevivir los próximos S días, o determina que no es posible sobrevivir.
Ejemplos:
Entrada: S = 10 N = 16 M = 2
Salida: Sí 2
Explicación 1: Una posible solución es comprar una caja el primer día (lunes), es suficiente comer de esta caja hasta el 8º día (lunes) inclusive. Ahora, el noveno día (martes), compras otra caja y usas los chocolates que contiene para sobrevivir el noveno y décimo día.
Entrada: 10 20 30
Salida: No
Explicación 2: No puedes sobrevivir incluso si compras comida porque la cantidad máxima de unidades que puedes comprar en un día es menos que la comida requerida para un día.
Enfoque:
En este problema, el enfoque codicioso de comprar alimentos durante algunos días tempranos consecutivos es la dirección correcta.
Si podemos sobrevivir durante los primeros 7 días, entonces podemos sobrevivir cualquier cantidad de días, para eso debemos verificar dos cosas
-> Verificar si podemos sobrevivir un día o no.
-> (S >= 7) Si compramos alimentos en los primeros 6 días de la semana y podemos sobrevivir durante la semana, es decir, el total de alimentos que podemos comprar en una semana (6*N) es mayor o igual que el total de alimentos que requieren sobrevivir en una semana (7*M) entonces podemos sobrevivir.
Nota: Estamos comprando la comida en los primeros 6 días porque contamos desde el lunes y la tienda permanecerá cerrada el domingo.
Si alguna de las condiciones anteriores no es cierta, entonces no podemos sobrevivir más
la ecuación se puede derivar como:
la cantidad de comida que compramos debe ser >= la cantidad de comida necesaria para sobrevivir.—-> ecuación 1
la cantidad de alimentos que compramos = número de veces que compramos (días) * cantidad de alimentos que obtenemos por una sola compra (N)
la cantidad de comida requerida para sobrevivir = la cantidad de días que necesitamos para sobrevivir (S) * la cantidad de comida requerida en cada día (M).
ahora de nuestra ecuación 1:
días * N >= S * M
por lo tanto, días = techo (S * M) / N
CPP
// C++ program to find the minimum days on which
// you need to buy food from the shop so that you
// can survive the next S days
#include <bits/stdc++.h>
using namespace std;
// function to find the minimum days
void survival(int S, int N, int M)
{
// If we can not buy at least a week
// supply of food during the first week
// OR We can not buy a day supply of food
// on the first day then we can't survive.
if (((N * 6) < (M * 7) && S > 6) || M > N)
cout << "No\n";
else {
// If we can survive then we can
// buy ceil(A/N) times where A is
// total units of food required.
int days = (M * S) / N;
if (((M * S) % N) != 0)
days++;
cout << "Yes " << days << endl;
}
}
// Driver code
int main()
{
int S = 10, N = 16, M = 2;
survival(S, N, M);
return 0;
}
C
// C program to find the minimum days on which
// you need to buy food from the shop so that you
// can survive the next S days
#include <stdio.h>
// function to find the minimum days
void survival(int S, int N, int M)
{
// If we can not buy at least a week
// supply of food during the first week
// OR We can not buy a day supply of food
// on the first day then we can't survive.
if (((N * 6) < (M * 7) && S > 6) || M > N)
printf("No\n");
else {
// If we can survive then we can
// buy ceil(A/N) times where A is
// total units of food required.
int days = (M * S) / N;
if (((M * S) % N) != 0)
days++;
printf("Yes %d\n",days);
}
}
// Driver code
int main()
{
int S = 10, N = 16, M = 2;
survival(S, N, M);
return 0;
}
// This code is contributed by rexomkar
Java
// Java program to find the minimum days on which
// you need to buy food from the shop so that you
// can survive the next S days
import java.io.*;
class GFG {
// function to find the minimum days
static void survival(int S, int N, int M)
{
// If we can not buy at least a week
// supply of food during the first
// week OR We can not buy a day supply
// of food on the first day then we
// can't survive.
if (((N * 6) < (M * 7) && S > 6) || M > N)
System.out.println("No");
else {
// If we can survive then we can
// buy ceil(A/N) times where A is
// total units of food required.
int days = (M * S) / N;
if (((M * S) % N) != 0)
days++;
System.out.println("Yes " + days);
}
}
// Driver code
public static void main(String[] args)
{
int S = 10, N = 16, M = 2;
survival(S, N, M);
}
}
// This code is contributed by vt_m.
Python3
# Python3 program to find the minimum days on
# which you need to buy food from the shop so
# that you can survive the next S days
def survival(S, N, M):
# If we can not buy at least a week
# supply of food during the first week
# OR We can not buy a day supply of food
# on the first day then we can't survive.
if (((N * 6) < (M * 7) and S > 6) or M > N):
print("No")
else:
# If we can survive then we can
# buy ceil(A / N) times where A is
# total units of food required.
days = (M * S) / N
if (((M * S) % N) != 0):
days += 1
print("Yes "),
print(days)
# Driver code
S = 10; N = 16; M = 2
survival(S, N, M)
# This code is contributed by upendra bartwal
C#
// C# program to find the minimum days
// on which you need to buy food from
// the shop so that you can survive
// the next S days
using System;
class GFG {
// function to find the minimum days
static void survival(int S, int N, int M)
{
// If we can not buy at least a week
// supply of food during the first
// week OR We can not buy a day
// supply of food on the first day
// then we can't survive.
if (((N * 6) < (M * 7) && S > 6) || M > N)
Console.Write("No");
else {
// If we can survive then we can
// buy ceil(A/N) times where A is
// total units of food required.
int days = (M * S) / N;
if (((M * S) % N) != 0)
days++;
Console.WriteLine("Yes " + days);
}
}
// Driver code
public static void Main()
{
int S = 10, N = 16, M = 2;
survival(S, N, M);
}
}
// This code is contributed by
// Smitha Dinesh Semwal
PHP
<?php
// PHP program to find the
// minimum days on which
// you need to buy food
// from the shop so that you
// can survive the next S days
// Function to find
// the minimum $days
function survival($S, $N, $M)
{
// If we can not buy at least a week
// supply of food during the first week
// OR We can not buy a day supply of food
// on the first day then we can't survive.
if ((($N * 6) < ($M * 7) &&
$S > 6) || $M >$N)
echo "No";
else
{
// If we can survive then we can
// buy ceil(A/N) times where A is
// total units of food required.
$days = ($M * $S) / $N;
if ((($M * $S) % $N) != 0)
$days++;
echo "Yes " , floor($days) ;
}
}
// Driver code
$S = 10; $N = 16; $M = 2;
survival($S, $N, $M);
// This code is contributed by anuj_67
?>
Javascript
<script>
// JavaScript program to find the minimum days on which
// you need to buy food from the shop so that you
// can survive the next S days
// function to find the minimum days
function survival(S, N, M)
{
// If we can not buy at least a week
// supply of food during the first
// week OR We can not buy a day supply
// of food on the first day then we
// can't survive.
if (((N * 6) < (M * 7) && S > 6) || M > N)
document.write("No");
else {
// If we can survive then we can
// buy ceil(A/N) times where A is
// total units of food required.
let days = (M * S) / N;
if (((M * S) % N) != 0)
days++;
document.write("Yes " + Math.round(days));
}
}
// Driver Code
let S = 10, N = 16, M = 2;
survival(S, N, M);
// This code is contributed by splevel62.
</script>
Producción:
Yes 2
Complejidad de tiempo: O(1)
Complejidad de espacio: O(1)
Otro enfoque:
Verifique si la comida requerida para los días S se puede comprar o no, excluyendo los domingos y tomando todos los demás días para comprar. Si se puede comprar, compre con avidez desde el día inicial hasta que los alimentos adquiridos sean mayores o iguales a los alimentos requeridos para S días.
C++
// C++ program to find the minimum days on which
// you need to buy food from the shop so that you
// can survive the next S days
#include <bits/stdc++.h>
using namespace std;
// function to find the minimum days
int minimumDays(int S, int N, int M)
{
// Food required to survive S days
double req = S * M;
// If buying all possible days except sundays, but can't
// provide the sufficient food. If total can't provide
// then each week also can't provide.
if ((S - S / 7) * N < req) {
return -1;
} // If possible get the number of days.
else {
return ceil(req / N);
}
// Or Simply one line code:
// return ((S-S/7)*N<S*M) ? -1 : ceil(static_cast<double>(S*M)/N);
}
// Driver code
int main()
{
int S = 10, N = 16, M = 2;
int days = minimumDays(S, N, M);
if (days != -1) {
cout << "Yes " << days << endl;
}
else {
cout << "No" << endl;
}
return 0;
}
Producción:
Yes 2
Complejidad de tiempo: O(1)
Complejidad de espacio: O(1)
Publicación traducida automáticamente
Artículo escrito por Gautam Karakoti y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA