Genéricos de Java para codificar de manera eficiente en la programación competitiva

Las plantillas son la base de la programación genérica, que implica escribir código de forma independiente de cualquier tipo en particular. Estas poderosas herramientas se pueden usar para escribir nuestro código de manera efectiva. Algunos trucos geniales que pueden usarse en la programación competitiva se dan a continuación:

Entrada/salida rápida :

Esto utiliza la ventaja de tiempo de BufferedReader y StringTokenizer y la ventaja de los métodos definidos por el usuario para escribir menos y, por lo tanto, una entrada más rápida. A continuación se muestra el código para encontrar la suma de N enteros usando un lector y escritor rápido.

Java

// Java program to illustrate the fast
// input output
import java.io.*;
import java.util.StringTokenizer;
  
public class GFG {
  
    // Driver Code
    public static void main(String[] args)
        throws IOException
    {
  
        // Initialize the reader
        FastReader reader = new FastReader();
  
        // Initialize the writer
        FastWriter writer = new FastWriter();
  
        // Your Code here
  
        // Reads a single integer
        int n = reader.readSingleInt();
  
        // Reads a array of N number
        // in a line
        int a[] = reader.readIntArray(n);
  
        // Prints a string
        writer.writeString("SUM OF :");
  
        // Print the array of number
        // with spaces
        writer.writeIntArrayWithSpaces(a);
  
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += a[i];
        }
  
        // Prints a single number
        writer.writeSingleInteger(sum);
    }
  
    // Fast Reader Class
    public static class FastReader {
  
        // Reader object
        BufferedReader reader;
  
        // Constructor
        public FastReader()
        {
            // Initialize the reader
            reader = new BufferedReader(
                new InputStreamReader(
                    System.in));
        }
  
        // String tokenizer
        StringTokenizer tokenizer;
  
        // Function to read integer
        public int readSingleInt()
            throws IOException
        {
            return Integer.parseInt(
                reader.readLine());
        }
  
        // Function to read a single long
        public long readSingleLong()
            throws IOException
        {
            return Long.parseLong(
                reader.readLine());
        }
  
        // Function to read a array of
        // numsInts integers in 1 line
        public int[] readIntArray(int numInts)
            throws IOException
        {
            int[] nums = new int[numInts];
            tokenizer
                = new StringTokenizer(
                    reader.readLine());
  
            // Input Numbers
            for (int i = 0; i < numInts; i++) {
                nums[i] = Integer.parseInt(
                    tokenizer.nextToken());
            }
            return nums;
        }
  
        // Function to read string
        public String readString()
            throws IOException
        {
            return reader.readLine();
        }
    }
  
    // Fast Writer Class
    public static class FastWriter {
  
        // Writer object
        BufferedWriter writer;
  
        // Constructor
        public FastWriter()
        {
  
            // Initialize the writer
            writer = new BufferedWriter(
                new OutputStreamWriter(
                    System.out));
        }
  
        // Function to write single integer
        public void writeSingleInteger(int i)
            throws IOException
        {
            writer.write(Integer.toString(i));
            writer.newLine();
            writer.flush();
        }
  
        // Function to write a single long
        public void writeSingleLong(long i)
            throws IOException
        {
            writer.write(Long.toString(i));
            writer.newLine();
            writer.flush();
        }
  
        // Function to write a Integer
        // of array with spaces in 1 line
        public void writeIntArrayWithSpaces(
            int[] nums)
            throws IOException
        {
            for (int i = 0; i < nums.length; i++) {
                writer.write(nums[i] + " ");
            }
            writer.newLine();
            writer.flush();
        }
  
        // Function to write a Integer
        // of array without spaces
        // in 1 line
        public void writeIntArrayWithoutSpaces(int[] nums)
            throws IOException
        {
            for (int i = 0;
                 i < nums.length; i++) {
                writer.write(
                    Integer.toString(
                        nums[i]));
            }
            writer.newLine();
            writer.flush();
        }
  
        // Function to write a String
        public void writeString(String s)
            throws IOException
        {
            writer.write(s);
            writer.newLine();
            writer.flush();
        }
    }
}

 
Para cambiar el flujo de entrada y salida según el entorno a archivos de texto o entrada estándar, como se hace normalmente al usar texto sublime u otros IDE, use el siguiente código como plantilla de FastIO.

Java

// Java program to illustrate the
// fast input output
import java.io.*;
import java.util.StringTokenizer;
  
public class GFG {
    public
  
        // Driver Code
        static void main(String[] args) throws IOException
    {
  
        // Initialize the reader
        FastReader reader = new FastReader();
  
        // Initialize the writer
        FastWriter writer = new FastWriter();
  
        // Your Code here
    }
  
    // Fast Reader Class
    public static class FastReader {
  
        // Reader object
        BufferedReader reader;
  
        // Constructor
        public FastReader()
        {
  
            // Initialize the reader
            reader = new BufferedReader(
                new InputStreamReader(
                    System.in));
  
            if (System.getProperty(
                    "ONLINE_JUDGE")
                == null) {
                try {
                    reader = new BufferedReader(
                        new InputStreamReader(
                            new FileInputStream(
                                "input.txt")));
                }
                catch (Exception e) {
                }
            }
        }
  
        // String tokenizer
        StringTokenizer tokenizer;
  
        // Function to read a
        // single integer
        public int readSingleInt()
            throws IOException
        {
            return Integer.parseInt(
                reader.readLine());
        }
  
        // Function to read a
        // single long
        public long readSingleLong()
            throws IOException
        {
            return Long.parseLong(
                reader.readLine());
        }
  
        // Function to read a array
        // of numsInts integers
        // in one line
        public int[] readIntArray(int numInts)
            throws IOException
        {
            int[] nums = new int[numInts];
            tokenizer
                = new StringTokenizer(
                    reader.readLine());
  
            for (int i = 0;
                 i < numInts; i++) {
                nums[i] = Integer.parseInt(
                    tokenizer.nextToken());
            }
            return nums;
        }
  
        // Function to read string
        public String readString()
            throws IOException
        {
            return reader.readLine();
        }
    }
  
    // Fast Writer Class
    public static class FastWriter {
  
        // Writer object
        BufferedWriter writer;
  
        // Constructor
        public FastWriter()
        {
  
            // Initialize the writer
            writer = new BufferedWriter(
                new OutputStreamWriter(
                    System.out));
            if (System.getProperty(
                    "ONLINE_JUDGE")
                == null) {
                try {
                    writer = new BufferedWriter(
                        new OutputStreamWriter(
                            new FileOutputStream(
                                "output.txt")));
                }
                catch (Exception e) {
                }
            }
        }
  
        // Function to write the
        // single integer
        public void writeSingleInteger(int i)
            throws IOException
        {
            writer.write(Integer.toString(i));
            writer.newLine();
            writer.flush();
        }
  
        // Function to write single long
        public void writeSingleLong(long i)
            throws IOException
        {
            writer.write(Long.toString(i));
            writer.newLine();
            writer.flush();
        }
  
        // Function to write a Integer of
        // array with spaces in one line
        public void writeIntArrayWithSpaces(int[] nums)
            throws IOException
        {
            for (int i = 0;
                 i < nums.length; i++) {
                writer.write(nums[i]
                             + " ");
            }
            writer.newLine();
            writer.flush();
        }
  
        // Function to write Integer of
        // array without spaces in 1 line
        public void writeIntArrayWithoutSpaces(int[] nums)
            throws IOException
        {
            for (int i = 0;
                 i < nums.length; i++) {
                writer.write(
                    Integer.toString(
                        nums[i]));
            }
            writer.newLine();
            writer.flush();
        }
  
        // Function to write String
        public void writeString(String s)
            throws IOException
        {
            writer.write(s);
            writer.newLine();
            writer.flush();
        }
    }
}

Nota : para obtener información sobre Entrada/salida rápida en Java, consulte esta publicación .

Funciones comúnmente utilizadas en Programación Competitiva :

A continuación se muestran las funciones que se usan comúnmente durante la programación competitiva , se pueden incluir en el código para evitar pérdidas de tiempo implementándolas durante el concurso. 

Pares en Java :

Los pares se usan comúnmente en la programación competitiva. Es una manera fácil de usar pares en JAVA. A continuación se muestra la implementación del mismo:

Java

// Java program to illustrate the
// use Pairs
import java.io.*;
  
class GFG {
  
    // Driver Code
    public static void main(String[] args)
    {
        // Initialize a pair
        Pair<Integer, Integer> x
            = new Pair<Integer, Integer>(1, 2);
  
        // Print pair
        System.out.println(x.first + ", "
                           + x.second);
    }
  
    // Pair class
    static class Pair<A, B> {
        A first;
        B second;
  
        // Constructor
        public Pair(A first, B second)
        {
            this.first = first;
            this.second = second;
        }
    }
}

Exponencial rápido usando mod :

Java

// Function to find x ^ n using p as mod
static long power(long x, long y, long p)
{
  
    // Initialize result
    long res = 1;
  
    // Update x if it is more than or
    // equal to p
    x = x % p;
  
    while (y > 0) {
  
        // If y is odd, multiply x
        // with result
        if (y % 2 == 1)
            res = (res * x) % p;
  
        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
  
    return res;
}

nCr usando el pequeño teorema de Fermat : 

Java

// Function to find x ^ n using p as mod
static long power(long x, long y, long p)
{
  
    // Initialize result
    long res = 1;
  
    // Update x if it is more than or
    // equal to p
    x = x % p;
  
    while (y > 0) {
  
        // If y is odd, multiply x
        // with result
        if (y % 2 == 1)
            res = (res * x) % p;
  
        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
  
    return res;
}
  
// Returns n^(-1) mod p
static long modInverse(long n, long p)
{
    return power(n, p - 2, p);
}
  
// Returns nCr % p using Fermat's
// little theorem.
static long nCrModPFermat(int n, int r, long p)
{
  
    // Base case
    if (r == 0)
        return 1;
  
    // Fill factorial array so that we
    // can find all factorial of r, n
    // and n-r
    long[] fac = new long[n + 1];
    fac[0] = 1;
  
    for (int i = 1; i <= n; i++)
        fac[i] = fac[i - 1] * i % p;
  
    return (fac[n] * modInverse(fac[r], p) % p
            * modInverse(fac[n - r], p) % p)
        % p;
}

Coeficiente binomial :

El coeficiente binomial se usa principalmente para encontrar el valor de [n * (N – 1) *—* (N – K + 1)] / [K * (K – 1) *—-* 1]). A continuación se muestra el programa para implementar el mismo:

Java

// Function to implement the
// binomial coefficient
static long binomialCoeff(long n,
                          long k,
                          long MOD)
{
    long res = 1;
  
    // Since C(n, k) = C(n, n-k)
    if (k > n - k)
        k = n - k;
  
    // Find the value of
    // [n * (n-1) *---* (n-k+1)] / [k * (k-1) *----* 1]
    for (int i = 0; i < k; ++i) {
        res *= (n - i);
        res /= (i + 1);
        res %= MOD;
    }
  
    // Return the result
    return res;
}

Aritmética modular :

Java

const int mod = 1000000007;
  
// Function to implement the modular
// arithmetic addition
private static long modular_add(long a, long b)
{
    return ((a % mod) + (b % mod)) % mod;
}
  
// Function to implement the modular
// arithmetic subtraction
private static long modular_sub(long a, long b)
{
    return ((a % mod) - (b % mod) + mod) % mod;
}
  
// Function to implement the modular
// arithmetic multiplication
private static long modular_mult(long a, long b)
{
    return ((a % mod) * (b % mod)) % mod;
}

Ordenar una array :

Java

// Function to sort an integer array
static void sort(int[] a)
{
    // Stores the element in arraylist
    ArrayList<Integer> l = new ArrayList<>();
    for (int i : a)
        l.add(i);
  
    // Use collection.sort() method
    Collections.sort(l);
  
    // Update the original array
    // with the sorted array elements
    for (int i = 0; i < a.length; i++)
        a[i] = l.get(i);
}

MCD y MCM :

Java

static long lcm(int a, int b)
{
    return (a / gcd(a, b)) * b;
}
  
private static long gcd(long a, long b)
{
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

Publicación traducida automáticamente

Artículo escrito por UtkarshPandey6 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 *