Question

Într-o gară se află un tren cu 2 la puterea n vagoane. Pentru fiecare vagon se cunoaşte numărul de călători care urmează să se urce. Astfel la etapa 1 avem acest tren. La etapa 2 se formează din trenul de la etapa 1 două trenuri, unui cu vagoanele de pe poziţii impare, iar celălalt cu vagoanele de pe poziţii pare. La etapa 3, din fiecare tren de la etapa 2 se formează câte două trenuri: unul cu vagoanele de pe poziţii pare, iar celălalt cu cele de pe poziţii impare şi aşa mai departe. Astfel la etapa k din fiecare tren de la etapa k-1 se construiesc câte două trenuri, unul cu vagoanele de pe poziţii impare, iar celălalt cu vagoanele de pe poziţii pare.

Cerinţă
Să se scrie un program care pentru k dat, determină numărul maxim de călători aflaţi într-unul dintre trenurile etapei k.

Date de intrare
Fişierul de intrare tren.in are pe prima linie numerele naturale n şi k separate printr-un spaţiu. Pe cea de a doua linie se afla n numere naturale separate prin spatii; al i-lea numar de pe linie reprezinta numarul de calatori din vagonul de pe pozitia i (1<=i<=n).

Date de ieşire
Fişierul de ieşire tren.out va conţine pe prima linie numărul cerut.

Restricţii

0 <= n < 11
0 < k < n+2
Numărul de călători din trenul iniţial (etapa 1) este <2000000001.

Exemple
tren.in tren.out
3 3
10 20 30 25 15 5 10 45 70

EXPLICATII:
La etapa 2 avem doua trenuri cu vagoanele date de numarul de calatori:
10 30 15 10
20 25 5 45
La etapa 3 avem 4 trenuri cu vagoanele date de numarul de calatori:
10 15
30 10
20 5
25 45
La aceasta etapa trenul cu numarul maxim de calatori (70) este format din doua vagoane care au fiecare cate 25, respectiv 45 calatori.

Pentru cei inregistrati pe campion.edu.ro este problema tren. Va rog mult in c++ si folosind recursia

Answer 1

Iti dau sursa mea la problema tren. Am trecut si descrierea solutiei pentru a o intelege mai bine. Succes!

/* descriere solutie - tren

Notam cu d numarul de vagoane 2^n si cu x vectorul cu numarul de
calatori din fiecare vagon. x are d componente.
La fiecare etapa se imparte vectorul x in doi vectori x1 si x2 cu d1,
respectiv d2 componente, corespunzatori vagoanelor cu numarul de
ordine par, respectiv impar.
d1 si d2 la fiecare pas, raman puteri ale lui 2.
Daca la un moment dat am ajuns la etapa k, atunci se calculeaza suma
s a elementelor vectorului x (corespunzator numarului de calatori din trenul curent)
si se compara cu max, daca max,s, atunci max:=s.
Initial max este 0.

Valoarea finala a lui max este numarul cautat.

*/
#include<cstdio>
#include<cstring>
int max,s,n,i,j,k,p,a[2050],b[2050];
int main()
{
    freopen ("tren.in" , "r" , stdin);
    freopen ("tren.out" , "w" , stdout);
    scanf("%d %d",&n,&k);
    p=1;
    for (i=1;i<=n;i++) p=p*2;
    for(i=1;i<=p;i++) scanf("%d",&a[i]);
    i=1;
    n=p;
    max=n;
    while (i<k)
    {
        s=0;
        i++;
        j=1;
        while (j<n)
        {
            s++;
            b[s]=a[j];
            j=j+2;
        }
        j=2;
        while (j<=n)
        {
            s++;
            b[s]=a[j];
            j=j+2;
        }
        max=max/2;
        memcpy(a,b,sizeof(b));
        memset(b,0,sizeof(b));
    }
    s=0;
    k=0;
    i=-1*max;
    while (i<=n)
    {
        i=i+max;
        s=0;
        for (j=i+1;j<=i+max;j++) s=s+a[j];
        if (s>k) k=s;
    }
    printf("%d",k);
    return 0;
}