Consultas en array con elementos que desaparecen y reaparecen

Dada una array, arr[] de tamaño N . Cada segundo, un número entero desaparece durante N segundos y después de N segundos, vuelve a aparecer en su posición original. Los enteros desaparecen en el orden de izquierda a derecha arr[0], arr[1], …, arr[N – 1] . Después de que desaparecen todos los enteros, comienzan a reaparecer hasta que reaparecen todos los enteros. Una vez que vuelven a aparecer N elementos, el proceso comienza de nuevo. 
Ahora, dadas las consultas Q , cada una consta de dos números enteros t y M . La tarea es determinar el M -ésimo elemento desde la izquierda en t -ésimosegundo. Si la array no existe hasta M, imprima -1 .

Ejemplos: 

Entrada: arr[] = {1, 2, 3, 4, 5}, Q = {{1, 4}, {6, 1}, {3, 5}} 
Salida: 


-1 
En el tiempo, 
t1 – > {2, 3, 4, 5} 
t2 -> {3, 4, 5} 
t3 -> {4, 5} 
t4 -> {5} 
t5 -> {} 
t6 -> {1}

Entrada: arr[] = {5, 4, 3, 4, 5}, Q = {{2, 3}, {100000000, 2}} 
Salida: 

4

Enfoque: el enfoque principal es que se requiere verificar si la array está vacía o llena y eso se puede ver dividiendo el número de vueltas por el tamaño de la array. Si el resto es 0, entonces puede ser cualquiera de los casos (vacío o relleno). 
Por observación se ve que en los turnos impares el arreglo se va reduciendo y en los pares pares el arreglo se expande y usando esta observación se comprobará que M está fuera del índice o dentro del arreglo.
A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to perform the queries
void PerformQueries(vector<int>& a,
                    vector<pair<long long, int> >& vec)
{
 
    vector<int> ans;
 
    // Size of the array with
    // 1-based indexing
    int n = (int)a.size() - 1;
 
    // Number of queries
    int q = (int)vec.size();
 
    // Iterating through the queries
    for (int i = 0; i < q; ++i) {
 
        long long t = vec[i].first;
        int m = vec[i].second;
 
        // If m is more than the
        // size of the array
        if (m > n) {
            ans.push_back(-1);
            continue;
        }
 
        // Count of turns
        int turn = t / n;
 
        // Find the remainder
        int rem = t % n;
 
        // If the remainder is 0 and turn is
        // odd then the array is empty
        if (rem == 0 and turn % 2 == 1) {
            ans.push_back(-1);
            continue;
        }
 
        // If the remainder is 0 and turn is
        // even then array is full and
        // is in its initial state
        if (rem == 0 and turn % 2 == 0) {
            ans.push_back(a[m]);
            continue;
        }
 
        // If the remainder is not 0
        // and the turn is even
        if (turn % 2 == 0) {
 
            // Current size of the array
            int cursize = n - rem;
 
            if (cursize < m) {
                ans.push_back(-1);
                continue;
            }
            ans.push_back(a[m + rem]);
        }
        else {
 
            // Current size of the array
            int cursize = rem;
            if (cursize < m) {
                ans.push_back(-1);
                continue;
            }
            ans.push_back(a[m]);
        }
    }
 
    // Print the result
    for (int i : ans)
        cout << i << "\n";
}
 
// Driver code
int main()
{
 
    // The initial array, -1 is for
    // 1 base indexing
    vector<int> a = { -1, 1, 2, 3, 4, 5 };
 
    // Queries in the form of the pairs of (t, M)
    vector<pair<long long, int> > vec = {
        { 1, 4 },
        { 6, 1 },
        { 3, 5 }
    };
 
    PerformQueries(a, vec);
 
    return 0;
}

Java

// Java implementation of the approach
 
import java.util.*;
 
class GFG
{
 
    // Function to perform the queries
    static void PerformQueries(int[] a, int[][] vec)
    {
 
        Vector<Integer> ans = new Vector<>();
 
        // Size of the array with
        // 1-based indexing
        int n = (int) a.length - 1;
 
        // Number of queries
        int q = (int) vec.length;
 
        // Iterating through the queries
        for (int i = 0; i < q; ++i)
        {
 
            long t = vec[i][0];
            int m = vec[i][1];
 
            // If m is more than the
            // size of the array
            if (m > n)
            {
                ans.add(-1);
                continue;
            }
 
            // Count of turns
            int turn = (int) (t / n);
 
            // Find the remainder
            int rem = (int) (t % n);
 
            // If the remainder is 0 and turn is
            // odd then the array is empty
            if (rem == 0 && turn % 2 == 1)
            {
                ans.add(-1);
                continue;
            }
 
            // If the remainder is 0 and turn is
            // even then array is full and
            // is in its initial state
            if (rem == 0 && turn % 2 == 0)
            {
                ans.add(a[m]);
                continue;
            }
 
            // If the remainder is not 0
            // and the turn is even
            if (turn % 2 == 0)
            {
 
                // Current size of the array
                int cursize = n - rem;
 
                if (cursize < m)
                {
                    ans.add(-1);
                    continue;
                }
                ans.add(a[m + rem]);
            }
            else
            {
 
                // Current size of the array
                int cursize = rem;
                if (cursize < m)
                {
                    ans.add(-1);
                    continue;
                }
                ans.add(a[m]);
            }
        }
 
        // Print the result
        for (int i : ans)
            System.out.print(i + "\n");
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        // The initial array, -1 is for
        // 1 base indexing
        int[] a = { -1, 1, 2, 3, 4, 5 };
 
        // Queries in the form of the pairs of (t, M)
        int[][] vec = { { 1, 4 }, { 6, 1 }, { 3, 5 } };
 
        PerformQueries(a, vec);
 
    }
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 implementation of the approach
 
# Function to perform the queries
def PerformQueries(a, vec) :
 
    ans = [];
 
    # Size of the array with
    # 1-based indexing
    n = len(a) - 1;
 
    # Number of queries
    q = len(vec);
 
    # Iterating through the queries
    for i in range(q) :
 
        t = vec[i][0];
        m = vec[i][1];
 
        # If m is more than the
        # size of the array
        if (m > n) :
            ans.append(-1);
            continue;
 
        # Count of turns
        turn = t // n;
 
        # Find the remainder
        rem = t % n;
 
        # If the remainder is 0 and turn is
        # odd then the array is empty
        if (rem == 0 and turn % 2 == 1) :
            ans.append(-1);
            continue;
 
        # If the remainder is 0 and turn is
        # even then array is full and
        # is in its initial state
        if (rem == 0 and turn % 2 == 0) :
            ans.append(a[m]);
            continue;
 
        # If the remainder is not 0
        # and the turn is even
        if (turn % 2 == 0) :
 
            # Current size of the array
            cursize = n - rem;
 
            if (cursize < m) :
                ans.append(-1);
                continue;
     
            ans.append(a[m + rem]);
             
        else :
 
            # Current size of the array
            cursize = rem;
             
            if (cursize < m) :
                ans.append(-1);
                continue;
         
            ans.append(a[m]);
 
    # Print the result
    for i in ans :
        print(i) ;
 
# Driver code
if __name__ == "__main__" :
 
    # The initial array, -1 is for
    # 1 base indexing
    a = [ -1, 1, 2, 3, 4, 5 ];
 
    # Queries in the form of the pairs of (t, M)
    vec = [
        [ 1, 4 ],
        [ 6, 1 ],
        [ 3, 5 ]
    ];
 
    PerformQueries(a, vec);
 
# This code is contributed by AnkitRai01

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
    // Function to perform the queries
    static void PerformQueries(int[] a, int[,] vec)
    {
 
        List<int> ans = new List<int>();
 
        // Size of the array with
        // 1-based indexing
        int n = (int) a.Length - 1;
 
        // Number of queries
        int q = (int) vec.GetLength(0);
 
        // Iterating through the queries
        for (int i = 0; i < q; ++i)
        {
 
            long t = vec[i, 0];
            int m = vec[i, 1];
 
            // If m is more than the
            // size of the array
            if (m > n)
            {
                ans.Add(-1);
                continue;
            }
 
            // Count of turns
            int turn = (int) (t / n);
 
            // Find the remainder
            int rem = (int) (t % n);
 
            // If the remainder is 0 and turn is
            // odd then the array is empty
            if (rem == 0 && turn % 2 == 1)
            {
                ans.Add(-1);
                continue;
            }
 
            // If the remainder is 0 and turn is
            // even then array is full and
            // is in its initial state
            if (rem == 0 && turn % 2 == 0)
            {
                ans.Add(a[m]);
                continue;
            }
 
            // If the remainder is not 0
            // and the turn is even
            if (turn % 2 == 0)
            {
 
                // Current size of the array
                int cursize = n - rem;
 
                if (cursize < m)
                {
                    ans.Add(-1);
                    continue;
                }
                ans.Add(a[m + rem]);
            }
            else
            {
 
                // Current size of the array
                int cursize = rem;
                if (cursize < m)
                {
                    ans.Add(-1);
                    continue;
                }
                ans.Add(a[m]);
            }
        }
 
        // Print the result
        foreach (int i in ans)
            Console.Write(i + "\n");
    }
 
    // Driver code
    public static void Main(String[] args)
    {
 
        // The initial array, -1 is for
        // 1 base indexing
        int[] a = { -1, 1, 2, 3, 4, 5 };
 
        // Queries in the form of the pairs of (t, M)
        int[,] vec = { { 1, 4 }, { 6, 1 }, { 3, 5 } };
 
        PerformQueries(a, vec);
 
    }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// Javascript implementation of the approach
 
 
// Function to perform the queries
function PerformQueries(a, vec) {
 
    let ans = new Array();
 
    // Size of the array with
    // 1-based indexing
    let n = a.length - 1;
 
    // Number of queries
    let q = vec.length;
 
    // Iterating through the queries
    for (let i = 0; i < q; ++i) {
 
        let t = vec[i][0];
        let m = vec[i][1];
 
        // If m is more than the
        // size of the array
        if (m > n) {
            ans.push(-1);
            continue;
        }
 
        // Count of turns
        let turn = Math.floor(t / n);
 
        // Find the remainder
        let rem = t % n;
 
        // If the remainder is 0 and turn is
        // odd then the array is empty
        if (rem == 0 && turn % 2 == 1) {
            ans.push(-1);
            continue;
        }
 
        // If the remainder is 0 and turn is
        // even then array is full and
        // is in its initial state
        if (rem == 0 && turn % 2 == 0) {
            ans.push(a[m]);
            continue;
        }
 
        // If the remainder is not 0
        // and the turn is even
        if (turn % 2 == 0) {
 
            // Current size of the array
            let cursize = n - rem;
 
            if (cursize < m) {
                ans.push(-1);
                continue;
            }
            ans.push(a[m + rem]);
        }
        else {
 
            // Current size of the array
            let cursize = rem;
            if (cursize < m) {
                ans.push(-1);
                continue;
            }
            ans.push(a[m]);
        }
    }
 
    // Print the result
    for (let i of ans)
        document.write(i + "<br>");
}
 
// Driver code
 
 
// The initial array, -1 is for
// 1 base indexing
let a = [-1, 1, 2, 3, 4, 5];
 
// Queries in the form of the pairs of (t, M)
let vec = [
    [1, 4],
    [6, 1],
    [3, 5]];
 
PerformQueries(a, vec);
</script>
Producción: 

5
1
-1

 

Complejidad temporal: O(q)

Espacio Auxiliar: O(q)

Publicación traducida automáticamente

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