Número de días después de los cuales el tanque se vaciará

Dado un depósito con capacidad C litros que se llena completamente en el arranque. El depósito diario se llena con 1 litro de agua y, en caso de desbordamiento, se tira el agua sobrante. Ahora, en el i-ésimo día, se sacan i litros de agua para beber. Necesitamos averiguar el día en que el tanque se vaciará por primera vez.

Ejemplos:  

Input : Capacity = 5        
        l = 2
Output : 4
At the start of 1st day, water in tank = 5    
and at the end of the 1st day = (5 - 1) = 4
At the start of 2nd day, water in tank = 4 + 2 = 6
but tank capacity is 5 so water = 5
and at the end of the 2nd day = (5 - 2) = 3
At the start of 3rd day, water in tank = 3 + 2 = 5
and at the end of the 3rd day = (5 - 3) = 2
At the start of 4th day, water in tank = 2 + 2 = 4
and at the end of the 4th day = (4 - 4) = 0
    So final answer will be 4

Podemos ver que el tanque estará lleno durante (l + 1) días iniciales porque el agua que se extrae es menor que el agua que se llena. Después de eso, cada día el agua en el tanque se reducirá en 1 litro más y el (l + 1 + i)th día (C – (i)(i + 1) / 2) litro de agua quedará antes de tomar agua potable. 

Ahora necesitamos encontrar un día mínimo (l + 1 + K), en el que incluso después de llenar el tanque por l litros tengamos menos de l de agua en el tanque, es decir, el (l + 1 + K – 1) día el tanque se vacía entonces nuestro objetivo es encontrar el K mínimo tal que, 
C – K(K + 1) / 2 <= l

Podemos resolver la ecuación anterior usando la búsqueda binaria y luego (l + K) será nuestra respuesta. La complejidad temporal total de la solución será O(log C) 

// C/C++ code to find number of days after which
// tank will become empty
#include <bits/stdc++.h>
using namespace std;
 
// Utility method to get sum of first n numbers
int getCumulateSum(int n)
{
    return (n * (n + 1)) / 2;
}
 
// Method returns minimum number of days after
// which tank will become empty
int minDaysToEmpty(int C, int l)
{
    // if water filling is more than capacity then
    // after C days only tank will become empty
    if (C <= l)
        return C;   
 
    // initialize binary search variable
    int lo = 0;
    int hi = 1e4;
    int mid;
 
    // loop until low is less than high
    while (lo < hi) {
        mid = (lo + hi) / 2;
 
        // if cumulate sum is greater than (C - l)
        // then search on left side
        if (getCumulateSum(mid) >= (C - l))
            hi = mid;
         
        // if (C - l) is more then search on
        // right side
        else
            lo = mid + 1;       
    }
 
    // final answer will be obtained by adding
    // l to binary search result
    return (l + lo);
}
 
// Driver code to test above methods
int main()
{
    int C = 5;
    int l = 2;
 
    cout << minDaysToEmpty(C, l) << endl;
    return 0;
}

// Java code to find number of days after which
// tank will become empty
public class Tank_Empty {
     
    // Utility method to get sum of first n numbers
    static int getCumulateSum(int n)
    {
        return (n * (n + 1)) / 2;
    }
      
    // Method returns minimum number of days after
    // which tank will become empty
    static int minDaysToEmpty(int C, int l)
    {
        // if water filling is more than capacity then
        // after C days only tank will become empty
        if (C <= l)
            return C;   
      
        // initialize binary search variable
        int lo = 0;
        int hi = (int)1e4;
        int mid;
      
        // loop until low is less than high
        while (lo < hi) {
             
            mid = (lo + hi) / 2;
      
            // if cumulate sum is greater than (C - l)
            // then search on left side
            if (getCumulateSum(mid) >= (C - l))
                hi = mid;
              
            // if (C - l) is more then search on
            // right side
            else
                lo = mid + 1;       
        }
      
        // final answer will be obtained by adding
        // l to binary search result
        return (l + lo);
    }
      
    // Driver code to test above methods
    public static void main(String args[])
    {
        int C = 5;
        int l = 2;
      
        System.out.println(minDaysToEmpty(C, l));
    }
}
// This code is contributed by Sumit Ghosh

# Python3 code to find number of days
# after which tank will become empty
 
# Utility method to get
# sum of first n numbers
def getCumulateSum(n):
 
    return int((n * (n + 1)) / 2)
 
 
# Method returns minimum number of days
# after  which tank will become empty
def minDaysToEmpty(C, l):
 
    # if water filling is more than
    # capacity then after C days only
    # tank will become empty
    if (C <= l) : return C
 
    # initialize binary search variable
    lo, hi = 0, 1e4
 
    # loop until low is less than high
    while (lo < hi):
        mid = int((lo + hi) / 2)
 
        # if cumulate sum is greater than (C - l)
        # then search on left side
        if (getCumulateSum(mid) >= (C - l)):
            hi = mid
         
        # if (C - l) is more then
        # search on right side
        else:
            lo = mid + 1   
     
    # Final answer will be obtained by
    # adding l to binary search result
    return (l + lo)
 
# Driver code
C, l = 5, 2
print(minDaysToEmpty(C, l))
 
# This code is contributed by Smitha Dinesh Semwal.

// C# code to find number
// of days after which
// tank will become empty
using System;
 
class GFG
{
     
    // Utility method to get
    // sum of first n numbers
    static int getCumulateSum(int n)
    {
        return (n * (n + 1)) / 2;
    }
     
    // Method returns minimum
    // number of days after
    // which tank will become empty
    static int minDaysToEmpty(int C,
                              int l)
    {
        // if water filling is more
        // than capacity then after
        // C days only tank will
        // become empty
        if (C <= l)
            return C;
     
        // initialize binary
        // search variable
        int lo = 0;
        int hi = (int)1e4;
        int mid;
     
        // loop until low is
        // less than high
        while (lo < hi)
        {
             
            mid = (lo + hi) / 2;
     
            // if cumulate sum is
            // greater than (C - l)
            // then search on left side
            if (getCumulateSum(mid) >= (C - l))
                hi = mid;
             
            // if (C - l) is more then
            // search on right side
            else
                lo = mid + 1;
        }
     
        // final answer will be
        // obtained by adding
        // l to binary search result
        return (l + lo);
    }
     
    // Driver code
    static public void Main ()
    {
        int C = 5;
        int l = 2;
 
        Console.WriteLine(minDaysToEmpty(C, l));
    }
}
 
// This code is contributed by ajit

<script>
 
// Javascript code to find number
// of days after which
// tank will become empty
 
// Utility method to get
// sum of first n numbers
function getCumulateSum(n)
{
    return parseInt((n * (n + 1)) / 2, 10);
}
   
// Method returns minimum
// number of days after
// which tank will become empty
function minDaysToEmpty(C, l)
{
     
    // If water filling is more
    // than capacity then after
    // C days only tank will
    // become empty
    if (C <= l)
        return C;
   
    // Initialize binary
    // search variable
    let lo = 0;
    let hi = 1e4;
    let mid;
   
    // Loop until low is
    // less than high
    while (lo < hi)
    {
        mid = parseInt((lo + hi) / 2, 10);
   
        // If cumulate sum is
        // greater than (C - l)
        // then search on left side
        if (getCumulateSum(mid) >= (C - l))
            hi = mid;
           
        // If (C - l) is more then
        // search on right side
        else
            lo = mid + 1;
    }
   
    // Final answer will be
    // obtained by adding
    // l to binary search result
    return (l + lo);
}
 
// Driver code
let C = 5;
let l = 2;
 
document.write(minDaysToEmpty(C, l));
 
// This code is contributed by rameshtravel07
</script>

Producción: 

4

Solución alternativa: 
se puede resolver matemáticamente con una fórmula simple:

Supongamos que C>L. Sea d la cantidad de días después del L en que el tanque se vacía. Durante ese tiempo, habrá (d-1) recargas y d retiros. 
Por lo tanto, necesitamos resolver esta ecuación: 

la suma de todos los retiros es una suma de progresión aritmética, por lo tanto: 

Discriminante = 1+8(CL)>0,porque C>L. 
Saltándonos la raíz negativa, obtenemos la siguiente fórmula: 

Por lo tanto, la respuesta final es: 

 

// C/C++ code to find number of days after which
// tank will become empty
#include <bits/stdc++.h>
using namespace std;
 
// Method returns minimum number of days after
// which tank will become empty
int minDaysToEmpty(int C, int l)
{
    if (l >= C)
        return C;
     
    double eq_root = (std::sqrt(1+8*(C-l)) - 1) / 2;
    return std::ceil(eq_root) + l;
}
 
// Driver code to test above methods
int main()
{
    cout << minDaysToEmpty(5, 2) << endl;
    cout << minDaysToEmpty(6514683, 4965) << endl;
    return 0;
}

// Java code to find number of days
// after which tank will become empty
import java.lang.*;
class GFG {
     
// Method returns minimum number of days
// after which tank will become empty
static int minDaysToEmpty(int C, int l)
{
    if (l >= C) return C;
     
    double eq_root = (Math.sqrt(1 + 8 *
                     (C - l)) - 1) / 2;
    return (int)(Math.ceil(eq_root) + l);
}
 
// Driver code
public static void main(String[] args)
{
    System.out.println(minDaysToEmpty(5, 2));
    System.out.println(minDaysToEmpty(6514683, 4965));
}
}
 
// This code is contributed by Smitha Dinesh Semwal.

# Python3 code to find number of days
# after which tank will become empty
import math
 
# Method returns minimum number of days 
# after which tank will become empty
def minDaysToEmpty(C, l):
 
    if (l >= C): return C
     
    eq_root = (math.sqrt(1 + 8 * (C - l)) - 1) / 2
    return math.ceil(eq_root) + l
 
# Driver code
print(minDaysToEmpty(5, 2))
print(minDaysToEmpty(6514683, 4965))
 
# This code is contributed by Smitha Dinesh Semwal.

// C# code to find number
// of days after which
// tank will become empty
using System;
 
class GFG
{
     
// Method returns minimum
// number of days after
// which tank will become empty
static int minDaysToEmpty(int C,
                          int l)
{
    if (l >= C) return C;
     
    double eq_root = (Math.Sqrt(1 + 8 *
                     (C - l)) - 1) / 2;
    return (int)(Math.Ceiling(eq_root) + l);
}
 
// Driver code
static public void Main ()
{
    Console.WriteLine(minDaysToEmpty(5, 2));
    Console.WriteLine(minDaysToEmpty(6514683,
                                     4965));
}
}
 
// This code is contributed by ajit

<?php
// PHP code to find number
// of days after which
// tank will become empty
 
// Method returns minimum
// number of days after
// which tank will become empty
function minDaysToEmpty($C, $l)
{
    if ($l >= $C)
        return $C;
     
    $eq_root = (int)sqrt(1 + 8 *
                   ($C - $l) - 1) / 2;
    return ceil($eq_root) + $l;
}
 
// Driver code
echo minDaysToEmpty(5, 2), "\n";
echo minDaysToEmpty(6514683,
                    4965), "\n";
 
// This code is contributed
// by akt_mit
?>

<script>
 
// Javascript code to find number
// of days after which
// tank will become empty
 
// Method returns minimum
// number of days after
// which tank will become empty
function minDaysToEmpty(C, l)
{
    if (l >= C) return C;
 
    let eq_root = (Math.sqrt(1 + 8 *
                            (C - l)) - 1) / 2;
    return (Math.ceil(eq_root) + l);
}
 
// Driver code
document.write(minDaysToEmpty(5, 2) + "</br>");
document.write(minDaysToEmpty(6514683, 4965));
 
// This code is contributed by suresh07
 
</script>

Producción : 

4
8573

Gracias a Andrey Khayrutdinov por sugerir esta solución.
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.