Într-un laborator cibernetic se fac experimente cu roboţi. Pe o bandă de lucru se află aşezate unul lângă altul, N cuburi galbene şi albastre, numeroate în ordine cu valori de la 1 la N. Pentru fiecare cub se cunoaşte latura acestuia, exprimată în centimetri, şi culoarea, codificată prin simbolul g (pentru galben) sau a (pentru albastru). Un robot inteligent este programat să construiască turnuri prin aşezarea cuburilor unul peste altul. El se află în faţa benzii de lucru, analizează fiecare cub în ordine, de la primul la ultimul, şi procedează astfel :

• dacă este primul cub, îl lasă la locul lui pe bandă;
• aşează cubul numerotat cu K peste cubul numerotat cu K-1 doar dacă el are culoarea diferită şi latura mai mică decât cubul K-1. Această operaţie se efectuează în cazul în care cubul K-1 se află deja într-un turn constuit anterior sau dacă el a rămas în poziția inițială. În cazul în care cubul K nu poate fi aşezat peste cubul K-1, el rămâne la locul lui.

Cerința

Ştiind că un turn poate fi format din cel puţin un cub, scrieţi un program care să determine:

Într-un laborator cibernetic se fac experimente cu roboţi. Pe o bandă de lucru se află aşezate unul lângă altul, N cuburi galbene şi albastre, numeroate în ordine cu valori de la 1 la N. Pentru fiecare cub se cunoaşte latura acestuia, exprimată în centimetri, şi culoarea, codificată prin simbolul g (pentru galben) sau a (pentru albastru). Un robot inteligent este programat să construiască turnuri prin aşezarea cuburilor unul peste altul. El se află în faţa benzii de lucru, analizează fiecare cub în ordine, de la primul la ultimul, şi procedează astfel :

• dacă este primul cub, îl lasă la locul lui pe bandă;
• aşează cubul numerotat cu K peste cubul numerotat cu K-1 doar dacă el are culoarea diferită şi latura mai mică decât cubul K-1. Această operaţie se efectuează în cazul în care cubul K-1 se află deja într-un turn constuit anterior sau dacă el a rămas în poziția inițială. În cazul în care cubul K nu poate fi aşezat peste cubul K-1, el rămâne la locul lui.

Cerința

Ştiind că un turn poate fi format din cel puţin un cub, scrieţi un program care să determine:
1. numărul final T al turnurilor de pe bandă şi H, înălţimea celui mai înalt turn care se poate forma, exprimată în centimetri;
2. cel mai mare număr de cuburi Nmax ce pot forma un turn, dacă cele N cuburi ar putea fi rearanjate inițial pe bandă, unul lângă altul.

Date de intrare

Fişierul turnuri1.in conţine:
– pe prima linie un număr natural C care reprezintă numărul cerinţei şi poate fi 1 sau 2.
– pe cea de-a doua linie un număr natural N ce reprezintă numărul cuburilor de pe bandă;
– pe fiecare dintre următoarele N linii, câte un număr natural care reprezintă latura unui cub, urmat de un spaţiu şi simbolul g sau a, pentru codificarea culorii cubului.

Date de ieșire

Fișierul de ieșire turnuri1.out va conţine pentru cerința 1 (C=1) pe prima linie două valori, separate printr-un spațiu, ce reprezintă T și H. Pentru cerința 2 (C=2) fișierul va conține pe prima linie numărul Nmax.

Restricții și precizări

• 1 ≤ N ≤ 10 000 şi 1≤ latura unui cub ≤ 500 000;
• nu există două cuburi cu laturi egale;
• Pentru rezolvarea corectă a primei cerințe se acordă 30 de puncte, pentru rezolvarea corectă a celei de-a doua cerințe se acordă 60 de puncte.
• În concurs s-au acordat 10 din oficiu. Aici se acordă 10 puncte pentru exemplele din enunț.

Exemplul 1:

turnuri1.in

1
6
18 a
13 g
15 a
10 a
8 g
2 a

turnuri1.out

3 31

Explicație

Se va rezolva cerința 1.
Al doilea cub se aşează peste primul şi formează un turn cu înălţimea de 31 de centimetri. Al treilea cub formează singur un turn cu înălţimea 15 centimetri. Ultimele trei cuburi formează un turn cu înălţimea 20 de centimetri. Numărul turnurilor este 3. Înălţimea celui mai înalt turn este de 31 de centimetri.

Exemplul 2:

turnuri1.in

2
6
18 a
13 g
15 a
10 a
8 g
2 a

turnuri1.out

5

Explicație

Se va rezolva cerința 2. O posibilă rearanjare a cuburilor ar fi următoarea:

Primele 5 cuburi formează un turn.

#include <bits/stdc++.h>

using namespace std;

ifstream fin("turnuri1.in");
ofstream fout("turnuri1.out");

int C,n,n1,n2;
long long int nr_turnuri , max_turn;
int v1[10003] , v2[10003] , v3;

void citire()
{   
    int l1,l2,i;
    long long h_turn;
    char cul1,cul2;

    fin>>C>>n;
    fin>>l1>>cul1;
    nr_turnuri=1;h_turn=l1;
    if(cul1=='g') v1[++n1]=l1;
       else v2[++n2]=l1;
    for(i=1; i<=n-1; i++)
    {
        fin>>l2>>cul2;
        if(cul2=='g') v1[++n1]=l2;
           else v2[++n2]=l2;

        if(l2<l1 && cul2!=cul1)
            {h_turn=h_turn+l2;}
        else
            {nr_turnuri++;h_turn=l2;}
        if (h_turn>max_turn) max_turn=h_turn;
        l1=l2;cul1=cul2;
    }
}

bool cmp( int a, int b)
{
    return (a>b);
}

int main()
{
    int i,j,k,p;
    citire();
    if (C==1)
        fout<<nr_turnuri<<' '<<max_turn<<'\n';
    else
    {
        sort(v1+1,v1+1+n1,cmp);
        sort(v2+1,v2+1+n2,cmp);
        v1[n1+1]=500003;
        v2[n2+1]=500002;
        i=1;j=1;k=0;
        if (v1[i]>v2[j])
        {
            ++k;v3=v1[i++];p=1;
        }
        else
        {
            ++k;v3=v2[j++];p=-1;
        }
        while(i<=n1&&j<=n2)
        {
            if(p==1)
            {
                while(j<=n2 && v2[j]>=v3)
                    j++;
                if (j<=n2)
                {++k; v3=v2[j++];p=-p;}
            }
            else
            {
                while(i<=n1 && v1[i]>=v3)
                    i++;
                if(i<=n1)
                {++k;v3=v1[i++];p=-p;}
            }
        }
       if(p==-1)
        for(i;i<=n1;i++)
            if (v1[i]<v3) {++k;v3=v1[i];break;}
       if(p==1)
            for(j;j<=n2;j++)
            if (v2[j]<v3) {++k;v3=v2[j];break;}
       fout<<k<<'\n';
    }
    return 0;
}