Recuento de triples (A, B, C) donde A*C es mayor que B*B

Posted on by Rudeus Greyrat

Dados tres enteros A , B y C . La tarea es contar el número de ternas (a, b, c) tales que a * c > b 2 , donde 0 < a <= A , 0 < b <= B y 0 < c <= C .
Ejemplos: 
 

Entrada: A = 3, B = 2, C = 2 
Salida: 6 
Se cuentan los siguientes triples: 
(1, 1, 2), (2, 1, 1), (2, 1, 2), (3, 1, 1), (3, 1, 2) y (3, 2, 2).
Entrada: A = 3, B = 3, C = 3 
Salida: 11 
 

Enfoque ingenuo: 
el enfoque de fuerza bruta es considerar todos los triples posibles (a, b, c) y contar esos triples que satisfacen la restricción a*c > b 2 . 
A continuación se muestra la implementación del enfoque dado. 
 

C++

// C++ implementation
#include <bits/stdc++.h>
using namespace std;
 
// function to return the count
// of the valid triplets
long long countTriplets(int A, int B, int C)
{
    long long ans = 0;
    for (int i = 1; i <= A; i++) {
        for (int j = 1; j <= B; j++) {
            for (int k = 1; k <= C; k++) {
                if (i * k > j * j)
                    ans++;
            }
        }
    }
    return ans;
}
 
// Driver Code
int main()
{
    int A, B, C;
    A = 3, B = 2, C = 2;
 
    // function calling
    cout << countTriplets(A, B, C);
}

Java

// Java implementation of above approach
import java.util.*;
 
class GFG
{
 
// function to return the count
// of the valid triplets
static long countTriplets(int A, int B, int C)
{
    long ans = 0;
    for (int i = 1; i <= A; i++)
    {
        for (int j = 1; j <= B; j++)
        {
            for (int k = 1; k <= C; k++)
            {
                if (i * k > j * j)
                    ans++;
            }
        }
    }
    return ans;
}
 
// Driver Code
public static void main (String[] args)
{
    int A = 3, B = 2, C = 2;
 
    // function calling
    System.out.println(countTriplets(A, B, C));
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 implementation for above approach
 
# function to return the count
# of the valid triplets
def countTriplets(A, B, C):
    ans = 0
    for i in range(1, A + 1):
        for j in range(1, B + 1):
            for k in range(1, C + 1):
                if (i * k > j * j):
                    ans += 1
 
    return ans
 
# Driver Code
A = 3
B = 2
C = 2
 
# function calling
print(countTriplets(A, B, C))
 
# This code is contributed by Mohit Kumar

C#

// C# implementation of above approach
using System;
 
class GFG
{
 
// function to return the count
// of the valid triplets
static long countTriplets(int A,
                          int B, int C)
{
    long ans = 0;
    for (int i = 1; i <= A; i++)
    {
        for (int j = 1; j <= B; j++)
        {
            for (int k = 1; k <= C; k++)
            {
                if (i * k > j * j)
                    ans++;
            }
        }
    }
    return ans;
}
 
// Driver Code
public static void Main (String[] args)
{
    int A = 3, B = 2, C = 2;
 
    // function calling
    Console.WriteLine(countTriplets(A, B, C));
}
}
     
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript implementation
 
// function to return the count
// of the valid triplets
function countTriplets(A, B, C)
{
    let ans = 0;
    for (let i = 1; i <= A; i++) {
        for (let j = 1; j <= B; j++) {
            for (let k = 1; k <= C; k++) {
                if (i * k > j * j)
                    ans++;
            }
        }
    }
    return ans;
}
 
// Driver Code
    let A, B, C;
    A = 3, B = 2, C = 2;
 
    // function calling
    document.write(countTriplets(A, B, C));
 
</script>
Producción: 

6

 

Tiempo Complejidad: O(A*B*C) .

Espacio auxiliar: O(1)
Enfoque eficiente: 
Contemos todos los tripletes para un valor dado de b = k para todo k de 1 a B . 
 

  1. Para un b = k dado , necesitamos encontrar todos los a = i y c = j que satisfagan i * j > k 2
  2. Para a = i , encuentre el c = j más pequeño que satisfaga la condición.
    Dado que c = j satisface esta condición, c = j + 1, c = j + 2, … y así sucesivamente, también cumplirán la condición. 
    Entonces podemos contar fácilmente todos los triples en los que a = i y b = k .
  3. Además, si para algunos a = i , c = j es el valor más pequeño tal que se cumple la condición dada, entonces se puede observar que a = j y todo c >= i también satisface la condición. 
    La condición también se cumple con a = j + 1 y c >= i , es decir, todos los valores a >= j yc >= i también satisfacen la condición.
  4. La observación anterior nos ayuda a contar fácilmente todos los triples en los que b = k y a >= j .
  5. Ahora necesitamos contar todos los triples en los que b = k y i < a < j .
  6. Por lo tanto, para un valor dado de b = k , solo necesitamos subir a a = raíz cuadrada de k .

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

C++

// C++ implementation
#include <bits/stdc++.h>
using namespace std;
 
// Counts the number of triplets
// for a given value of b
long long getCount(int A, int B2,
                   int C)
{
    long long count = 0;
 
    // Count all triples in which a = i
    for (int i = 1; i <= A; i++) {
 
        // Smallest value j
        // such that i*j > B2
        long long j = (B2 / i) + 1;
 
        // Count all (i, B2, x)
        // such that x >= j
        if (C >= j)
            count = (count + C - j + 1);
 
        // count all (x, B2, y) such
        // that x >= j this counts
        // all such triples in
        // which a >= j
        if (A >= j && C >= i)
            count = (count
                     + (C - i + 1)
                           * (A - j + 1));
 
        // As all triples with a >= j
        // have been counted reduce
        // A to j - 1.
        if (A >= j)
            A = j - 1;
    }
    return count;
}
 
// Counts the number of triples that
// satisfy the given constraints
long long countTriplets(int A, int B,
                        int C)
{
    long long ans = 0;
    for (int i = 1; i <= B; i++) {
 
        // GetCount of triples in which b = i
        ans = (ans
               + getCount(A, i * i, C));
    }
    return ans;
}
 
// Driver Code
int main()
{
    int A, B, C;
    A = 3, B = 2, C = 2;
 
    // Function calling
    cout << countTriplets(A, B, C);
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Counts the number of triplets
// for a given value of b
static long getCount(int A, int B2, int C)
{
    long count = 0;
 
    // Count all triples in which a = i
    for (int i = 1; i <= A; i++)
    {
 
        // Smallest value j
        // such that i*j > B2
        long j = (B2 / i) + 1;
 
        // Count all (i, B2, x)
        // such that x >= j
        if (C >= j)
            count = (count + C - j + 1);
 
        // count all (x, B2, y) such
        // that x >= j this counts
        // all such triples in
        // which a >= j
        if (A >= j && C >= i)
            count = (count + (C - i + 1) *
                             (A - j + 1));
 
        // As all triples with a >= j
        // have been counted reduce
        // A to j - 1.
        if (A >= j)
            A = (int) (j - 1);
    }
    return count;
}
 
// Counts the number of triples that
// satisfy the given constraints
static long countTriplets(int A, int B, int C)
{
    long ans = 0;
    for (int i = 1; i <= B; i++)
    {
 
        // GetCount of triples in which b = i
        ans = (ans + getCount(A, i * i, C));
    }
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int A, B, C;
    A = 3; B = 2; C = 2;
 
    // Function calling
    System.out.println(countTriplets(A, B, C));
}
}
 
// This code is contributed by Princi Singh

Python3

# Python3 implementation
 
# Counts the number of triplets
# for a given value of b
def getCount(A, B2, C):
     
    count = 0
     
    # Count all triples in which a = i
    i=1
    while(i<A):
         
        # Smallest value j
        # such that i*j > B2
        j = (B2 // i) + 1
        # Count all (i, B2, x)
        # such that x >= j
        if (C >= j):
            count = count + C - j + 1
             
        # count all (x, B2, y) such
        # that x >= j this counts
        # all such triples in
        # which a >= j
        if (A>= j and C >= i):
            count = count+ (C - i + 1)    * (A - j + 1)
             
        # As all triples with a >= j
        # have been counted reduce
        # A to j - 1.
        if (A >= j):
            A = j - 1
        i+=1
     
    return count
 
 
# Counts the number of triples that
# satisfy the given constraints
def countTriplets(A, B, C):
     
    ans = 0
    for i in range(1,B+1):
        # GetCount of triples in which b = i
        ans = (ans+ getCount(A, i * i, C))
     
    return ans
 
 
# Driver Code
 
A = 3
B = 2
C = 2
 
# Function calling
print(countTriplets(A, B, C))
 
# This code is contributed by shubhamsingh10

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;                
     
class GFG
{
 
// Counts the number of triplets
// for a given value of b
static long getCount(int A, int B2, int C)
{
    long count = 0;
 
    // Count all triples in which a = i
    for (int i = 1; i <= A; i++)
    {
 
        // Smallest value j
        // such that i*j > B2
        long j = (B2 / i) + 1;
 
        // Count all (i, B2, x)
        // such that x >= j
        if (C >= j)
            count = (count + C - j + 1);
 
        // count all (x, B2, y) such
        // that x >= j this counts
        // all such triples in
        // which a >= j
        if (A >= j && C >= i)
            count = (count + (C - i + 1) *
                             (A - j + 1));
 
        // As all triples with a >= j
        // have been counted reduce
        // A to j - 1.
        if (A >= j)
            A = (int) (j - 1);
    }
    return count;
}
 
// Counts the number of triples that
// satisfy the given constraints
static long countTriplets(int A, int B, int C)
{
    long ans = 0;
    for (int i = 1; i <= B; i++)
    {
 
        // GetCount of triples in which b = i
        ans = (ans + getCount(A, i * i, C));
    }
    return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
    int A, B, C;
    A = 3; B = 2; C = 2;
 
    // Function calling
    Console.WriteLine(countTriplets(A, B, C));
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
 
// Javascript implementation
 
// Counts the number of triplets
// for a given value of b
function getCount(A, B2, C)
{
    let count = 0;
 
    // Count all triples in which a = i
    for (let i = 1; i <= A; i++) {
 
        // Smallest value j
        // such that i*j > B2
        let j = parseInt(B2 / i) + 1;
 
        // Count all (i, B2, x)
        // such that x >= j
        if (C >= j)
            count = (count + C - j + 1);
 
        // count all (x, B2, y) such
        // that x >= j this counts
        // all such triples in
        // which a >= j
        if (A >= j && C >= i)
            count = (count
                     + (C - i + 1)
                           * (A - j + 1));
 
        // As all triples with a >= j
        // have been counted reduce
        // A to j - 1.
        if (A >= j)
            A = j - 1;
    }
    return count;
}
 
// Counts the number of triples that
// satisfy the given constraints
function countTriplets(A, B, )
{
    let ans = 0;
    for (let i = 1; i <= B; i++) {
 
        // GetCount of triples in which b = i
        ans = (ans
               + getCount(A, i * i, C));
    }
    return ans;
}
 
// Driver Code
    let A, B, C;
    A = 3, B = 2, C = 2;
 
    // Function calling
    document.write(countTriplets(A, B, C));
 
</script>
Producción: 

6

 

Complejidad de tiempo: O(A*B)

Espacio Auxiliar: O(1)
 

Publicación traducida automáticamente

Artículo escrito por KartikArora y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *