Dados dos números X y d donde X representa el número de subsecuencias no vacías y d representa la diferencia. Genere una array de tamaño N que tenga subsecuencias no vacías iguales a X, donde la diferencia entre el elemento máximo y el elemento mínimo de cada subsecuencia debe ser menor que d.
Restricciones:
1 ≤ N ≤ 500
1 ≤ X ≤ 10 9
Ejemplos:
Input : X = 10, d = 5 Output : 5 50 7 15 6 100 "10" desired subsequences are: [5], [50], [7], [15], [6], [100], [5, 7], [5, 6], [7, 6], [5, 7, 6]. Input : X = 4, d = 10 Output : 10 100 1000 10000 "4" desired subsequences are: [10], [100], [1000], [10000].
Enfoque: se puede ver claramente que si d = 5, entonces la array [1, 7] tendrá solo 2 subsecuencias deseadas ([1] y [7] y no [1, 7]). Entonces, de manera similar, si agregamos muchos 1 y muchos 7 en esa array, tampoco se aceptará ninguna subsecuencia que tenga 1 y 7 juntos. Entonces, los elementos que tienen una diferencia mayor que d siempre formarán conjuntos disjuntos. Por ejemplo, en [1, 5, 9, 9, 12, 13], si d = 2, entonces hay 4 conjuntos disjuntos [1], [5], [9, 9], [12, 13].
El número total de subsecuencias no vacías en una array de tamaño N es igual a 
-1. Por lo tanto, solo necesitamos encontrar la longitud del conjunto disjunto cuyo número total de subsecuencias es menor o igual a X y generar los elementos de ese conjunto disjunto. Si no es igual a X, entonces se debe realizar el mismo paso en X reducido para encontrar el siguiente conjunto disjunto hasta que X se convierta en 0. Para hacer que todos los conjuntos sean disjuntos, una forma es tomar el primer elemento de la array como 1 y luego agregar 1 en 1er conjunto disjunto igual a la longitud de este conjunto disjunto y luego agregar «d» a los elementos en el conjunto disjunto anterior para hacer otro conjunto disjunto y así sucesivamente.
Por ejemplo: X = 25, d = 100
El primer conjunto disjunto tendrá 4 elementos ya que tiene 15 subsecuencias. Entonces, el primer conjunto disjunto será {1, 1, 1, 1}.
Ahora X se convierte en 10 y, por lo tanto, el segundo conjunto disjunto contendrá solo 3 elementos. Así que 2do . disjoint será { 101, 101, 101 } (agregando 100 en 1 para hacerlo disjunto desde el 1er conjunto). Ahora X se convierte en 3 y, por lo tanto, el conjunto disjunto final contendrá dos elementos y el tercer conjunto disjunto será { 201, 201 } (añadiendo nuevamente 100 en 101 para hacerlo disjunto de los dos conjuntos anteriores).
La salida final será [1, 1, 1, 1, 101, 101, 101, 201, 201].
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ Program to output an array having exactly X
// subsequences where difference between maximum
// and minimum element of each subsequence is less
// than d
#include <bits/stdc++.h>
using namespace std;
// This function outputs the desired array.
void printArray(int X, int d, int first_ele)
{
// Iterate till all the disjoint sets are found.
while (X > 0) {
// count_ele the elements in one disjoint
// set. pow_of_two will keep all the
// powers of twos.
int count_ele = 0, pow_of_two = 2;
// Iterate to know the maximum length of
// disjoint set by checking whether X is
// greater than the total number of
// possible not empty sequences of that
// disjoint set.
while (X - pow_of_two + 1 >= 0) {
count_ele++;
pow_of_two *= 2;
}
// now deleting the total subsequences of
// the maximum length disjoint set from X.
X = X - (pow_of_two / 2) + 1;
// outputting the disjoint set having equal
// elements.
for (int j = 0; j < count_ele; j++)
cout << first_ele << " ";
// by adding d, it makes another disjoint
// set of equal elements.
first_ele += d;
}
}
// Driver Code
int main()
{
int d = 100, X = 25;
printArray(X, d, 1);
return 0;
}
Java
// Java Program to output
// an array having exactly
// X subsequences where
// difference between maximum
// and minimum element of
// each subsequence is less
// than d
import java.io.*;
class GFG
{
// This function outputs
// the desired array.
static void printArray(int X, int d,
int first_ele)
{
// Iterate till all the
// disjoint sets are found.
while (X > 0)
{
// count_ele the elements
// in one disjoint set.
// pow_of_two will keep
// all the powers of twos.
int count_ele = 0,
pow_of_two = 2;
// Iterate to know the
// maximum length of
// disjoint set by checking
// whether X is greater than
// the total number of possible
// not empty sequences of that
// disjoint set.
while (X - pow_of_two + 1 >= 0)
{
count_ele++;
pow_of_two *= 2;
}
// now deleting the total
// subsequences of the maximum
// length disjoint set from X.
X = X - (pow_of_two / 2) + 1;
// outputting the disjoint
// set having equal elements.
for (int j = 0;
j < count_ele; j++)
System.out.print(first_ele + " ");
// by adding d, it makes
// another disjoint set
// of equal elements.
first_ele += d;
}
}
// Driver Code
public static void main (String[] args)
{
int d = 100, X = 25;
printArray(X, d, 1);
}
}
// This code is contributed
// by anuj_67.
Python3
# Python 3 Program to output an array having # exactly X subsequences where difference # between maximum and minimum element of each # subsequence is less than d # This function outputs the desired array. def printArray(X, d, first_ele): # Iterate till all the disjoint # sets are found. while (X > 0): # count_ele the elements in one # disjoint set. pow_of_two will # keep all the powers of twos. count_ele, pow_of_two = 0, 2 # Iterate to know the maximum length of # disjoint set by checking whether X is # greater than the total number of # possible not empty sequences of that # disjoint set. while (X - pow_of_two + 1 >= 0): count_ele += 1 pow_of_two *= 2 # now deleting the total subsequences of # the maximum length disjoint set from X. X = X - (pow_of_two / 2) + 1 # outputting the disjoint set having # equal elements. for j in range(count_ele): print(first_ele, end = " ") # by adding d, it makes another # disjoint set of equal elements. first_ele += d # Driver Code if __name__ == '__main__': d, X = 100, 25 printArray(X, d, 1) # This code is contributed by PrinciRaj19992
C#
// C# Program to output
// an array having exactly
// X subsequences where
// difference between maximum
// and minimum element of
// each subsequence is less
// than d
using System;
class GFG
{
// This function outputs
// the desired array.
static void printArray(int X, int d,
int first_ele)
{
// Iterate till all the
// disjoint sets are found.
while (X > 0)
{
// count_ele the elements
// in one disjoint set.
// pow_of_two will keep
// all the powers of twos.
int count_ele = 0,
pow_of_two = 2;
// Iterate to know the
// maximum length of
// disjoint set by checking
// whether X is greater than
// the total number of possible
// not empty sequences of that
// disjoint set.
while (X - pow_of_two + 1 >= 0)
{
count_ele++;
pow_of_two *= 2;
}
// now deleting the total
// subsequences of the maximum
// length disjoint set from X.
X = X - (pow_of_two / 2) + 1;
// outputting the disjoint
// set having equal elements.
for (int j = 0;
j < count_ele; j++)
Console.Write(first_ele + " ");
// by adding d, it makes
// another disjoint set
// of equal elements.
first_ele += d;
}
}
// Driver Code
public static void Main ()
{
int d = 100, X = 25;
printArray(X, d, 1);
}
}
// This code is contributed
// by anuj_67.
PHP
<?php
// PHP Program to output an array
// having exactly X subsequences
// where difference between maximum
// and minimum element of each
// subsequence is less than d
// This function outputs the
// desired array.
function printArray($X, $d,$first_ele)
{
// Iterate till all the disjoint
// sets are found.
while ($X > 0)
{
// count_ele the elements in
// one disjoint set. pow_of_two
// will keep all the powers of twos.
$count_ele = 0;
$pow_of_two = 2;
// Iterate to know the maximum
// length of disjoint set by
// checking whether X is greater
// than the total number of possible
// not empty sequences of that
// disjoint set.
while ($X - $pow_of_two + 1 >= 0)
{
$count_ele++;
$pow_of_two *= 2;
}
// now deleting the total subsequences of
// the maximum length disjoint set from X.
$X = $X - ($pow_of_two / 2) + 1;
// outputting the disjoint set
// having equal elements.
for ($j = 0; $j < $count_ele; $j++)
echo $first_ele , " ";
// by adding d, it makes another
// disjoint set of equal elements.
$first_ele += $d;
}
}
// Driver Code
$d = 100;
$X = 25;
printArray($X, $d, 1);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript Program to output
// an array having exactly
// X subsequences where
// difference between maximum
// and minimum element of
// each subsequence is less
// than d
// This function outputs
// the desired array.
function printArray(X, d, first_ele)
{
// Iterate till all the
// disjoint sets are found.
while (X > 0)
{
// count_ele the elements
// in one disjoint set.
// pow_of_two will keep
// all the powers of twos.
let count_ele = 0,
pow_of_two = 2;
// Iterate to know the
// maximum length of
// disjoint set by checking
// whether X is greater than
// the total number of possible
// not empty sequences of that
// disjoint set.
while (X - pow_of_two + 1 >= 0)
{
count_ele++;
pow_of_two *= 2;
}
// now deleting the total
// subsequences of the maximum
// length disjoint set from X.
X = X - parseInt(pow_of_two / 2, 10) + 1;
// outputting the disjoint
// set having equal elements.
for (let j = 0; j < count_ele; j++)
document.write(first_ele + " ");
// by adding d, it makes
// another disjoint set
// of equal elements.
first_ele += d;
}
}
let d = 100, X = 25;
printArray(X, d, 1);
</script>
1 1 1 1 101 101 101 201 201
Publicación traducida automáticamente
Artículo escrito por pulkitjain_NSIT y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA