Rezolvare completă PbInfo #3276 shopping

Maria este mare amatoare de cumpărături. Ea și-a cumpărat în decursul mai multor zile de la magazinul său preferat N articole de îmbrăcăminte și încălțăminte cu preturile s1, s2, …, sN lei. Iulia, prietena Mariei, observând cumpărăturile, i-a spus:
- Puteai economisi mulți bani. Nu ai văzut promoțiile magazinului? Dacă ai fi cumpărat două produse deodată, cel mai ieftin din cele două l-ai fi cumpărat la jumătate de preț. Iar dacă ai fi cumpărat trei produse deodată, ai fi primit pe cel mai ieftin din cele trei gratuit!
Maria și Iulia s-au decis să afle care ar fi fost suma minimă cheltuită pentru a achiziționa în aceeași ordine cele N produse, dar grupând câte un produs, câte două sau câte trei.

Cerința

Pentru că cele două fete nu se descurcă așa de bine la informatică, ele te roagă să le ajuți să determine care este această sumă minimă.

Date de intrare

Programul citește de la tastatură un număr natural N, iar apoi N numere naturale s1, s2, …, sN separate prin câte un spațiu reprezentând sumele cheltuite pentru fiecare din cele N produse.

Date de ieșire

Programul va afișa pe ecran un singur număr real, care reprezintă suma minimă ce putea fi cheltuită grupând produsele câte unul, câte două sau câte trei. Numărul real se va afișa cu o zecimală.

Restricții și precizări

  • 4 ≤ N ≤ 1000
  • Sumele s1, s2, …, sN sunt numere naturale cuprinse între 1 și 1000

Exemplul 1:

Intrare

4
20 100 50 200

Ieșire

320.0

Explicație

Maria trebuia să cumpere primul produs, cheltuind 20 lei, apoi să cumpere ultimele trei produse împreună cheltuind numai 300 de lei, deoarece produsul de 50 lei îl primea gratuit.

Exemplul 2:

Intrare

5
100 27 15 25 400

Ieșire

538.5

Explicație

Maria trebuia să cumpere primele două produse împreună, cheltuind 113.5 lei, apoi să cumpere ultimele trei produse împreună, cheltuind 425 lei. Suma totală cheltuită ar fi fost 113.5 + 425 = 538.5 lei.

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 shopping:

#include<bits/stdc++.h>
using namespace std;

int a[1001], n;
float c[1001];

float Min2(float x, float y)
{
    return (x < y ? x : y);
}

float Min3(float x, float y, float z)
{
    return Min2(Min2(x,y), z);
}

int main()
{
    int i;
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> a[i];
    /// dp
    c[0] = 0;
    c[1] = a[1];
    c[2] = a[1] + a[2] - Min2(a[1],a[2])/2;
    for (i = 3; i <= n; i++)
        c[i] = Min3(c[i-3]+a[i-2]+a[i-1]+a[i]-Min3(a[i-2],a[i-1],a[i]),
        c[i-2]+a[i-1]+a[i]-Min2(a[i-1],a[i])/2, c[i-1] + a[i]);

    cout << setprecision(1) << fixed << c[n];
    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 #3276 shopping

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3276 shopping 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!