Gigel primea de la mama lui, ca temă, o foaie pe care era scris un şir de N numere întregi. Singurul calcul pe care ştia să îl facă până acum era suma tuturor numerelor. Pentru aceasta el plasa N-1 semne de adunare, +, între numerele aflate pe poziţii consecutive în şir şi calcula astfel suma acestor numere. Între timp a crescut şi a învăţat şi operaţia de înmulţire pentru care foloseşte semnul *. Din şirul celor N-1 semne de adunare, îi trece prin minte să înlocuiască K semne + cu K semne *.
Îşi dă seama că tema se complică, deoarece înmulţirile trebuie efectuate înaintea adunărilor, dar nu se dă bătut şi duce calculul până la capăt.

Cerința

Scrieţi un program care să determine valoarea minimă pe care o poate obţine şi valoarea maximă pe care o poate obţine după înlocuirea menţionată.

Date de intrare

Fişierul de intrare optim.in conţine pe prima linie numerele naturale N şi K, separate printr-un spaţiu, reprezentând numărul de numere întregi din şir, respectiv numărul de operaţii de înmulţire ce vor fi efectuate. Pe cea de a doua linie se află N numere întregi separate prin câte un spaţiu, \(x_1, x_2, … x_N\), reprezentând numerele din şir.

Date de ieșire

Fişierul de ieşire optim.out va conţine pe o singură linie, separate printr-un spaţiu, în ordine crescătoare, cele două valori cerute.

Restricții și precizări

2 ≤ N ≤ 30
0 ≤ K ≤ 9; K < N
-8 ≤ x_i ≤ 8, 1 ≤ i ≤ N

Exemplu

optim.in

optim.out

-31 86

Explicație

2 * 0 + 3 * (-1) + 7 * (-4) = -31

2 + 0 + 3 * (-1) * 7 * (-4) = 86.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Optim:

//O(Comb(N,K))
// Se genereaza fiecare posibilitate dar se si calculeaza suma pe parcurs

#include <cstdio>
#define inf 2000000000
#define MAXN 40

using namespace std;


int A[MAXN];
int maxim,minim, N, K,i;

void back(int lv, int k, int aux, int suma)
{
    if (lv == N){
        suma += aux;
        if (suma > maxim) maxim = suma;
        if (suma < minim) minim = suma;
        return;
    }
    if (N - lv - 1 >= k)
        back(lv+1, k, A[lv+2], suma + aux);
    if (k > 0)
        back(lv+1, k-1, aux * A[lv+2], suma);
}

int main()
{
    freopen("optim.in","r",stdin);
    freopen("optim.out", "w",stdout);
    
    scanf("%d %d",&N,&K);
    for (i=1; i<=N; ++i)
        scanf("%d",&A[i]);
    
    --N;
    maxim = -2000000000;
    minim =  2000000000;
    
    back(0, K, A[1], 0);
    
    printf("%d %d\n", minim, maxim);
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1760 Optim

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1760 Optim de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1760 Optim