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:
5
1
-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:
5
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)