Dada una array con tamaño N. Puede realizar dos tipos de operaciones en la array dada, como se describe a continuación:
- Elija alguna posición i y j , tal que (i no sea igual a j) , reemplace el valor de a[j] con a[i]*a[j] y elimine el número de la i -ésima celda.
- Elija alguna posición i y elimine el número de la i -ésima celda (Esta operación se puede realizar como máximo una vez y en cualquier momento, no necesariamente al principio).
La tarea es realizar exactamente N-1 operaciones con la array de tal manera que el único número que quede en la array sea el máximo posible. Este número puede ser bastante grande, así que en lugar de imprimirlo, imprima la secuencia de operaciones que conduce a este número máximo.
La salida debe contener exactamente N-1 líneas:
- Si la operación es del primer tipo, imprima 1 ij .
- Si la operación es del segundo tipo, imprima 2 i .
Nota : se considera que la array tiene una indexación basada en 1.
Ejemplos :
Input : a[] = { 5, -2, 0, 1, -3 }
Output : 2 3
1 1 2
1 2 4
1 4 5
Explanation:
Step 1: a[3] is removed.
Step 2: a[2] = a[2]*a[1] = -10; a[1] is removed.
Step 3: a[4] = a[4]*a[2] = -10; a[2] is removed.
Step 4: a[5] = a[5]*a[4] = 30; a[4] is removed.
So, the maximum product is 30.
Input : a[] = { 0, 0, 0, 0 }
Output : 1 1 2
1 2 3
1 3 4
Planteamiento: Hay varios casos en el problema. Sea cntZero el número de ceros en la array y cntNeg el número de elementos negativos . También permita que maxNeg sea la posición del máximo elemento negativo en la array, o -1 si no hay elementos negativos en la array.
Sea la parte de la respuesta el producto de todos los números que estarán en la respuesta y la parte eliminada sea el producto de todos los números que serán eliminados por el segundo tipo de operación.
Los casos son los siguientes:
- El primer caso es cuando cntZero=0 y cntNeg=0 . Entonces la parte de la respuesta es el producto de todos los números de la array. La parte eliminada está vacía.
- El segundo caso es cuando cntNeg es impar. Luego, la parte de la respuesta es el producto de todos los números en la array excepto todos los ceros y a[maxNeg] . La parte eliminada es el producto de todos los ceros y a[maxNeg] .
- El tercer caso es cuando cntNeg es par. Luego, la parte de la respuesta es el producto de todos los números de la array excepto todos los ceros. La parte eliminada es el producto de todos los ceros en la array (tenga cuidado en caso de que cntNeg=0 y cntZero=n ).
A continuación se muestra la implementación de la idea anterior:
C++
// CPP program for maximum possible product
// with given array of numbers
#include <bits/stdc++.h>
using namespace std;
// Function that prints operations in each step
void MaximumProduct(int a[], int n)
{
int cntneg = 0;
int cntzero = 0;
int used[n] = { 0 };
int pos = -1;
// count number of zeros and negative numbers
for (int i = 0; i < n; ++i) {
if (a[i] == 0) {
used[i] = 1;
cntzero++;
}
if (a[i] < 0) {
cntneg++;
// To get negative number which
// is nearest to zero, that is maximum
// negative number
if (pos == -1 || abs(a[pos]) > abs(a[i]))
pos = i;
}
}
// if number of negative number are odd then
// remove negative number at position pos
if (cntneg % 2 == 1)
used[pos] = 1;
// initial condition
if (cntzero == n || (cntzero == n - 1 &&
cntneg == 1)) {
for (int i = 0; i < n - 1; ++i)
cout << 1 << " " << i + 1 << " "
<< i + 2 << endl;
return;
}
int lst = -1;
for (int i = 0; i < n; ++i) {
if (used[i]) {
if (lst != -1)
cout << 1 << " " << lst + 1 << " "
<< i + 1 << endl;
lst = i;
}
}
// perform second type operation
if (lst != -1)
cout << 2 << " " << lst + 1 << endl;
lst = -1;
// for remaining numbers
for (int i = 0; i < n; ++i) {
// if it is not removed yet
if (!used[i]) {
if (lst != -1)
cout << 1 << " " << lst + 1 << " "
<< i + 1 << endl;
lst = i;
}
}
}
// Driver code
int main()
{
int a[] = { 5, -2, 0, 1, -3 };
int n = sizeof(a) / sizeof(a[0]);
MaximumProduct(a, n);
return 0;
}
C
// C program for maximum possible product
// with given array of numbers
#include <stdio.h>
#include <stdlib.h>
// Function that prints operations in each step
void MaximumProduct(int a[], int n)
{
int cntneg = 0;
int cntzero = 0;
int used[n];
//initializing the array as 0
for (int i = 0; i < n; i++)
{
used[i] = 0;
}
int pos = -1;
// count number of zeros and negative numbers
for (int i = 0; i < n; ++i) {
if (a[i] == 0) {
used[i] = 1;
cntzero++;
}
if (a[i] < 0) {
cntneg++;
// To get negative number which
// is nearest to zero, that is maximum
// negative number
if (pos == -1 || abs(a[pos]) > abs(a[i]))
pos = i;
}
}
// if number of negative number are odd then
// remove negative number at position pos
if (cntneg % 2 == 1)
used[pos] = 1;
// initial condition
if (cntzero == n || (cntzero == n - 1 &&
cntneg == 1)) {
for (int i = 0; i < n - 1; ++i)
printf("%d %d %d\n", 1, i + 1, i + 2);
return;
}
int lst = -1;
for (int i = 0; i < n; ++i) {
if (used[i]) {
if (lst != -1)
printf("%d %d %d\n", 1, lst+1, i+1);
lst = i;
}
}
// perform second type operation
if (lst != -1)
printf("%d %d\n", 2, lst + 1);
lst = -1;
// for remaining numbers
for (int i = 0; i < n; ++i) {
// if it is not removed yet
if (!used[i]) {
if (lst != -1)
printf("%d %d %d\n", 1, lst + 1, i+1);
lst = i;
}
}
}
// Driver code
int main()
{
int a[] = { 5, -2, 0, 1, -3 };
int n = sizeof(a) / sizeof(a[0]);
MaximumProduct(a, n);
return 0;
}
// This code is contributed by phalashi.
Java
// Java program for maximum possible product
// with given array of numbers
class GFG {
// Function that prints operations in each step
static void MaximumProduct(int a[], int n) {
int cntneg = 0;
int cntzero = 0;
int used[] = new int[n];
int pos = -1;
// count number of zeros and negative numbers
for (int i = 0; i < n; ++i) {
if (a[i] == 0)
{
used[i] = 1;
cntzero++;
}
if (a[i] < 0) {
cntneg++;
// To get negative number which
// is nearest to zero, that is maximum
// negative number
if (pos == -1 || Math.abs(a[pos]) > Math.abs(a[i])) {
pos = i;
}
}
}
// if number of negative number are odd then
// remove negative number at position pos
if (cntneg % 2 == 1) {
used[pos] = 1;
}
// initial condition
if (cntzero == n || (cntzero == n - 1 && cntneg == 1))
{
for (int i = 0; i < n - 1; ++i) {
System.out.println(1 + " " + (i + 1) + " "
+ (i + 2));
}
return;
}
int lst = -1;
for (int i = 0; i < n; ++i) {
if (used[i] == 1) {
if (lst != -1) {
System.out.println(1 + " " + (lst + 1) + " "
+ (i + 1));
}
lst = i;
}
}
// perform second type operations
if (lst != -1) {
System.out.println(2 + " " + (lst + 1));
}
lst = -1;
// for remaining numbers
for (int i = 0; i < n; ++i)
{
// if it is not removed yet
if (used[i] != 1)
{
if (lst != -1)
{
System.out.println(1 + " " + (lst + 1) + " "
+ (i + 1));
}
lst = i;
}
}
}
// Driver code
public static void main(String[] args)
{
int a[] = {5, -2, 0, 1, -3};
int n = a.length;
MaximumProduct(a, n);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program for maximum possible product # with given array of numbers # Function that prints operations # in each step def MaximumProduct(a, n): cntneg = 0 cntzero = 0 used = [0] * n pos = -1 # count number of zeros and # negative numbers for i in range(n): if (a[i] == 0) : used[i] = 1 cntzero += 1 if (a[i] < 0): cntneg += 1 # To get negative number which # is nearest to zero, that is maximum # negative number if (pos == -1 or abs(a[pos]) > abs(a[i])): pos = i # if number of negative number are odd then # remove negative number at position pos if (cntneg % 2 == 1): used[pos] = 1 # initial condition if (cntzero == n or (cntzero == n - 1 and cntneg == 1)): for i in range(n - 1): print (1, " ", i + 1, " ", i + 2) return lst = -1 for i in range(n) : if (used[i]) : if (lst != -1): print (1, " ", lst + 1, " ", i + 1) lst = i # perform second type operation if (lst != -1): print (2, " ", lst + 1) lst = -1 # for remaining numbers for i in range( n) : # if it is not removed yet if (not used[i]) : if (lst != -1): print (1, " ", lst + 1, " ", i + 1) lst = i # Driver code if __name__ == "__main__": a = [ 5, -2, 0, 1, -3 ] n = len(a) MaximumProduct(a, n) # This code is contributed by ita_c
C#
// C# program for maximum possible product
// with given array of numbers
using System;
class GFG
{
// Function that prints
// operations in each step
static void MaximumProduct(int []a, int n)
{
int cntneg = 0;
int cntzero = 0;
int []used = new int[n];
int pos = -1;
// count number of zeros
// and negative numbers
for (int i = 0; i < n; ++i)
{
if (a[i] == 0)
{
used[i] = 1;
cntzero++;
}
if (a[i] < 0)
{
cntneg++;
// To get negative number which
// is nearest to zero, that is
// maximum negative number
if (pos == -1 || Math.Abs(a[pos]) >
Math.Abs(a[i]))
{
pos = i;
}
}
}
// if number of negative number are odd then
// remove negative number at position pos
if (cntneg % 2 == 1)
{
used[pos] = 1;
}
// initial condition
if (cntzero == n || (cntzero == n - 1 &&
cntneg == 1))
{
for (int i = 0; i < n - 1; ++i)
{
Console.WriteLine(1 + " " + (i + 1) + " "
+ (i + 2));
}
return;
}
int lst = -1;
for (int i = 0; i < n; ++i)
{
if (used[i] == 1)
{
if (lst != -1)
{
Console.WriteLine(1 + " " + (lst + 1) + " "
+ (i + 1));
}
lst = i;
}
}
// perform second type operations
if (lst != -1)
{
Console.WriteLine(2 + " " + (lst + 1));
}
lst = -1;
// for remaining numbers
for (int i = 0; i < n; ++i)
{
// if it is not removed yet
if (used[i] != 1)
{
if (lst != -1)
{
Console.WriteLine(1 + " " + (lst + 1) + " "
+ (i + 1));
}
lst = i;
}
}
}
// Driver code
static public void Main ()
{
int []a = {5, -2, 0, 1, -3};
int n = a.Length;
MaximumProduct(a, n);
}
}
// This code is contributed by ajit
Javascript
<script>
// JavaScript program for maximum possible product
// with given array of numbers
// Function that prints operations in each step
function MaximumProduct(a, n)
{
let cntneg = 0;
let cntzero = 0;
let used = new Uint8Array(n);
let pos = -1;
// count number of zeros and negative numbers
for (let i = 0; i < n; ++i) {
if (a[i] == 0) {
used[i] = 1;
cntzero++;
}
if (a[i] < 0) {
cntneg++;
// To get negative number which
// is nearest to zero, that is maximum
// negative number
if (pos == -1 || Math.abs(a[pos]) > Math.abs(a[i]))
pos = i;
}
}
// if number of negative number are odd then
// remove negative number at position pos
if (cntneg % 2 == 1)
used[pos] = 1;
// initial condition
if (cntzero == n || (cntzero == n - 1 &&
cntneg == 1)) {
for (let i = 0; i < n - 1; ++i)
document.write(1 + " " + (i + 1) + " "
+ (i + 2) + "<br>");
return;
}
let lst = -1;
for (let i = 0; i < n; ++i) {
if (used[i]) {
if (lst != -1)
document.write(1 + " " + (lst + 1) + " "
+ (i + 1) + "<br>");
lst = i;
}
}
// perform second type operation
if (lst != -1)
document.write(2 + " " + (lst + 1) + "<br>");
lst = -1;
// for remaining numbers
for (let i = 0; i < n; ++i) {
// if it is not removed yet
if (!used[i]) {
if (lst != -1)
document.write(1 + " " + (lst + 1) + " "
+ (i + 1) + "<br>");
lst = i;
}
}
}
// Driver code
let a = [ 5, -2, 0, 1, -3 ];
let n = a.length;
MaximumProduct(a, n);
// This code is contributed by Surbhi Tyagi.
</script>
Producción:
2 3 1 1 2 1 2 4 1 4 5
Complejidad de tiempo: O(n), donde n representa el tamaño de la array dada.
Espacio auxiliar: O(n), donde n representa el tamaño de la array dada.
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA