Saltar al contenido

Reorganice la matriz dada para ordenarla y GCD de elementos a i K . es

Dado un entero positivo Arr[] de longitud yo (2 litros 2000) con elementos de 1 a L en orden desordenado y un número entero k
(1 K 2 * L – 1). A continuación, la tarea es realizar la configuración de Arr[] siguiendo dos condiciones:

Si tal arreglo no existe luego imprime «Imposible».

Necesitamos saber las siguientes dos cosas:

  1. En ese caso es posible una disposición L y R.
  2. Disposición de elementos.

Discutámoslos uno por uno.

  • Para verificar el arreglo es posible o no:-

Tomemos un ejemplo al azar Arr[] = {3, 1, 2}Entonces todos los arreglos posibles de arr[] ser – estar:

Primera cita: arr[] = {1, 2, 3}

MCD0 = MCD(1) = 1
MCD1 = MCD(1, 2)= 1
MCD2 = MCD(1, 2, 3) = 1

Suma total de GCD = 1 + 1 + 1 = 3

segundo esquema: Arr[] = {1, 3, 2}

Suma total de GCD = 1 + 1 + 1 = 3

Tercer arreglo: arr[] = {2, 1, 3}

Suma total de GCD = 2 + 1 + 1 = 4

Cuarto arreglo: arr[] = {2, 3, 1}

Suma total de GCD = 2 + 1 + 1 = 4

Quinto arreglo: arr[] = {3, 1, 2}

Suma total de GCD = 3 + 1 + 1 = 5

Sexto arreglo: arr[] = {3, 2, 1}

Suma total de GCD = 3 + 1 + 1 = 5

Para todos los esquemas anteriores podemos concluir que el Valor mínimo y Valor máximo de suma total de GCD es igual a 3 y 5 respectivamente. Esto nos da la idea de que el arreglo es posible cuando R está en el rango de [L, L+1.., 2*L-1]. En los arreglos anteriores, L = 3 y el valor máximo y mínimo de K es 3 (igual a L) y 5 (igual a 2 * L – 1), respectivamente.

  • Ahora Disposición de elementos (excepto en los casos en que la disposición no es posible):
  1. De la normativa anterior podemos concluir que: cuando K = LEntonces se puede verificar que: contando huellas de 1 a L deberá dar la suma total de GCD igual a K para todos los valores válidos de L y R.
  2. Para el resto de los casos (Cuando L! = R), Tomar primer_elemento como ((K% L) + 1) e imprimirlo. Luego imprime el resto de los elementos. de 1 a L excluyendo first_element (para evitar la duplicación, ya que lo imprimimos al comienzo del arreglo). Vea los ejemplos a continuación para mayor claridad:

Ejemplo 1: Arr[] = {2, 3, 4, 1, 5}, K = 5

L = 5, K = 5, podemos ver que claramente L es igual a R, Luego imprime contando de 1 a L:

Nueva configuración = {1, 2, 3, 4, 5} = GCD0 + GCD1 + GCD2 + GCD3 + GCD4 = 1 + 1 + 1 + 1 + 1 = 5, La suma total de GCD es igual a KPor lo tanto cita satisfecha así como en formato ordenado desde el índice 1 hasta N – 1.

Ejemplo 2: Arr[] = {2, 3, 4, 1, 5}, K = 7

L = 5, K = 7, podemos ver que claramente L no es igual a RDespués primer_elemento = ((K% L) + 1) = ((7 % 5) + 1) = 2 + 1 = 3.

utilidades imprimir primer_elemento Abeja primer índice de regulación y luego cuenta de 1 a L excluyendo primer_elemento

Nueva alineación = {3, 1, 2, 4, 5} = GCD0 + GCD1 + GCD2 + GCD3 + GCD4 = 3 + 1 + 1 + 1 + 1 = 7, La suma total de GCD es igual a KPor eso cita satisfecha así como en formato ordenado del índice 1 a N – 1.