Cod sursa(job #1012085)

Utilizator lucianRRuscanu Lucian lucianR Data 17 octombrie 2013 23:48:48
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 4.09 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <algorithm>
#define L_MAX 100001
#define inf -10000000

using namespace std;
ifstream in("expresie2.in");
ofstream out("expresie2.out");

char st[L_MAX];
long int p, nr, c[L_MAX];

long int suma(long int v[], long int k)
{
    int s, minn = inf;
    for(long int q = 0; q < k; q++)
    {
        s = v[q];
        for(long int j = q + 1; j < k; j++)
        {
            s += v[j];
            if(s > minn) minn = s;
        }
    }
    return minn;
}void mergee(int left, int right, int m)
{
    int l = left, r = m + 1, k = 0;
    while(l <= m && r <= right)
        if(v[l] < v[r])
            c[k++] = v[l++];
        else
            c[k++] = v[r++];
    while(l <= m)
            c[k++] = v[l++];
    while(r <= right)
            c[k++] = v[r++];
    for(int i = left; i <= right; i++)
        v[i] = c[i-left];
}

void merge_sort(int left, int right)
{
    int m;
    if(left < right)
    {
        m = (left + right) / 2;
        merge_sort(left, m);
        merge_sort(m+1, right);
        mergee(left, right, m);
    }
}

int main()
{
    ifstream in("algsort.in");
    ofstream out("algsort.out");
    in >> n;
    for(int i = 0; i <= n - 1; i++)
    {
        in >> v[i];
        c[i] = v[i];
    }
    merge_sort(0, n-1);
    for(int i = 0; i <= n - 1; i++)
        out << v[i] << " ";
    in.close();
    out.close();
    return 0;
}
void mergee(long int v[], int left, int right, int m)
{
    int l = left, r = m + 1, k = 0;
    while(l <= m && r <= right)
        if(v[l] < v[r])
            c[k++] = v[l++];
        else
            c[k++] = v[r++];
    while(l <= m)
            c[k++] = v[l++];
    while(r <= right)
            c[k++] = v[r++];
    for(int i = left; i <= right; i++)
        v[i] = c[i-left];
}

void merge_sort(long int v[], int left, int right)
{
    int m;
    if(left < right)
    {
        m = (left + right) / 2;
        merge_sort(v, left, m);
        merge_sort(v, m+1, right);
        mergee(v, left, right, m);
    }
}

long int med(long int v[], long int k)
{
    merge_sort(v, 0, k-1);
    long int m = (k+2)/2;
    if(k % 2 != 0)
        return v[m - 1];
    else return v[m - 2];
}

long int rec()
{
    long int v[L_MAX/2], q = 0;
    while(p < strlen(st))
    {
        if((st[p] >= '1' && st[p] <= '9') || st[p] == '-' || st[p] == ',')
        {
            while(st[p] == ',' || (st[p] >= '1' && st[p] <= '9') || st[p] == '-')
            {
                int minnus = 1;
                if(st[p] == ',')
                    p++;
                long int n=0;
                if(st[p] == '-')
                {
                    p++;
                    minnus = -1;
                }
                if(st[p] >= '1' && st[p] <= '9')
                {
                    nr++;
                    while(st[p] >= '1' && st[p] <= '9')
                        n = n * 10 + (int)st[p++] - '0';
                    v[q++] = n * minnus;
                }
                //cout<<v[q-1]<<endl;
            }
        }
        if(st[p] == '(')
        {
            p++;
            v[q++] = rec();
        }
        if(st[p] == '[')
        {
            p++;
            v[q++] = rec();
        }
        if(st[p] == ')')
        {
            long int aa;
            p++;
            aa=suma(v, q);
            //cout<<aa<<endl;
            return aa;
        }
        if(st[p] == ']')
        {
            long int aa;
            p++;
            aa= med(v, q);
            //cout<<aa<<endl;
            return aa;

        }
    }
    out << nr << '\n';
    long int s=0;
    for(long int i = 0; i < q; i++)
        s += v[i];
    return s;
}

int main()
{
    in.getline(st, L_MAX, '\n');
    /*for(long int i = 0; i < strlen(st); i++)
    {
        if(st[i] >= '1' && st[i] <= '9')
        {
            nr++;
            while(st[i] >= '1' && st[i] <= '9')
                i++;
        }

    }*/
    out << rec();
    in.close();
    out.close();
    return 0;
}