Specialiştii chimişti au reuşit crearea în laborator a unei game diversificate de substanţe lichide nemiscibile (care nu se amestecă între ele), de aceeaşi densitate şi de culori diferite.

Acest rezultat a fost utilizat de către specialiştii fizicieni pentru studiul principiului vaselor comunicante. Conform acestui principiu „într-un sistem de vase comunicante nivelul lichidului este acelaşi, indiferent de forma vaselor.“

Experimentele fizicienilor se desfăşoară astfel:

Într-un sistem cu două vase comunicante, gradat identic pe fiecare ramură cu 0, 1, 2, 3,…, fizicienii introduc un număr de n lichide, pe ramura din stânga sau pe ramura din dreapta. Volumele introduse din fiecare lichid, notate cu V_i (1≤i≤n), sunt numere naturale nenule pare astfel încât, la echilibru, orice lichid se va aşeza între două gradaţii de aceeaşi parte a unei ramuri sau pe cele două ramuri ale sistemului de vase comunicante. Lichidele sunt identificate prin intermediul culorii acestora, culori numerotate cu 1, 2, 3, … , n. Introducerea lichidelor în sistemul cu două vase comunicante se face în ordinea crescătoare a numerelor culorilor, începând cu lichidul de culoare 1.

Scopul experimentului este de a determina gradaţia maximă la care se ridică lichidele în sistemul cu două vase comunicante, precum şi între ce gradaţii se găseşte un lichid de culoare x, dintre cele introduse.

De exemplu, dacă în sistemul cu două vase comunicante se introduc n=3 lichide în ordinea: V₁=4 lichid de culoare 1 introdus prin ramura din dreapta (operaţie codificată 4 D), V₂=4 lichid de culoare 2 introdus prin ramura din stânga (operaţie codificată 4 S) şi V₃=2 lichid de culoare 3 introdus prin ramura din stânga (operaţie codificată 2 S) atunci gradaţia maximă la care se ridică nivelul lichidelor în sistemul cu două vase comunicante este 5, iar lichidul de culoare x=2 se găseşte între gradaţiile: 3 pe ramura din stânga (3 S) şi 1 pe ramura din dreapta (1 D), conform figurii alăturate.

Cerinţă

Să se scrie un program care cunoscând numărul n de lichide introduse în sistemul cu două vase comunicante, volumul V_i şi ramura prin care se face introducerea lichidului de culoare i (1≤i≤n), precum şi culoarea x, să calculeze gradaţia maximă la care se ridică lichidele în acest sistem la echilibru şi între ce gradaţii se găseşte lichidul de culoare x.

Date de intrare

Prima linie a fişierului de intrare vase1.in conţine un singur număr natural nenul n, cu semnificaţia de mai sus. Fiecare linie, din următoarele n, conţine câte două valori separate printr-un spaţiu: un număr natural nenul par şi o literă mare, S sau D, reprezentând volumul introdus din lichidul de culoare i, respectiv ramura (S pentru ramura din stânga şi D pentru ramura din dreapta) prin care se face introducerea acestuia. Linia n+2 a fişierului de intrare conţine un singur număr nenul x ce reprezintă culoarea lichidului căutat.

Date de ieșire

Fişierul de ieşire vase1.out va conţine pe prima linie un număr natural nenul ce reprezintă gradaţia maximă la care se ridică lichidele în sistemul de vase comunicante la echilibru. Următoarele două linii vor conţine fiecare câte două valori separate printr-un spaţiu: un număr natural şi o literă mare (S sau D), reprezentând gradaţia şi ramura între care se aşează lichidul căutat.

Restricții și precizări

1 ≤ x ≤ n ≤ 100 000
2 ≤ V_i ≤ 100 000 pentru 1 ≤ i ≤ n
sistemul de vase este gradat în aceleaşi unităţi de măsură în care sunt exprimate volumele de lichid;
dacă lichidul căutat, de culoare x, se aşează pe aceeaşi ramură se va afişa întâi gradaţia superioară şi apoi cea inferioară;
dacă lichidul căutat, de culoare x, se aşează pe ramuri diferite se va afişa întâi gradaţia de pe ramura din stânga şi apoi cea de pe ramura din dreapta;
dacă una dintre gradaţiile între care se situează lichidul căutat, de culoare x, este 0 atunci se consideră că aceasta gradaţie se găseşte pe aceeaşi ramură cu cealaltă gradaţie;
pentru rezolvarea primei cerinţe se acordă 20% din punctaj, iar pentru a doua cerinţă 80% din punctaj.

Exemplu

vase1.in

vase1.out

5
3 S
1 D

Explicație

Se introduc 3 lichide în sistemul de două vase comunicante:

primul cu volumul 4, se introduce prin dreapta şi are culoarea 1;
al doilea cu volumul 4, se introduce prin stânga şi are culoarea 2;
al treilea cu volumul 2, se introduce prin stânga şi are culoarea 3;

Se caută gradaţiile ce corespund lichidului de culoare 2.

Gradaţia maximă la care ajunge nivelul lichidului este 5.
Lichidul de culoare 2 se aşează între gradaţiile 3 pe ramura din stânga şi 1 pe ramura din dreapta.

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

//prof. Chesca Ciprian - 100 p
#include <fstream>
#define nmax 100001

using namespace std;

struct lichid
{
    long cant;  // cantitatea de substanta;
    char ram;   // ramura pe unde se toarna
    long cul;     //culoarea substantei
};


lichid st[nmax],dr[nmax];
long long vst=0,vdr=0;
ifstream f("vase1.in");
ofstream g("vase1.out");

int main()
{
long long i,n,x,z,mij,l1=0,l2=0,h1,h2,gasit,s=0;
char c,l1r=' ',l2r=' ';
f>>n;

// citesc datele sub forma a 2 stive st si dr si calculez suma totala
for(i=1;i<=n;i++)
{
    f>>x>>c;
    s+=x;
    switch (c)
    {
    case 'S': 
            st[++vst].cant=x;
            st[vst].ram=c;
            st[vst].cul=i;
            break;
    case 'D': 
            dr[++vdr].cant=x;
            dr[vdr].ram=c;
            dr[vdr].cul=i;
            break;
    }       
}   

// culoarea pe care o caut
f>>z;

//calculez punctul de echilibru
mij=s/2;

h1=mij;gasit=0;
while(h1>-mij&&vst>0&&!gasit)
{
    if (st[vst].cul==z) 
            {
            if (h1<0) {l1=-h1;l1r='D';}
                else  {l1=h1;l1r='S';}
            if (h1-st[vst].cant<0) {l2=-(h1-st[vst].cant);l2r='D';} 
                else  {l2=h1-st[vst].cant;l2r='S';}  
            gasit=1;
            }   
    h1-=st[vst--].cant; 
}

h2=mij;
while(h2>-mij&&vdr>0&&!gasit)
{
    if (dr[vdr].cul==z) 
            {
            if (h2<0) {l1=-h2;l1r='S';}
                else  {l1=h2;l1r='D';}
            if (h2-dr[vdr].cant<0) {l2=-(h2-dr[vdr].cant);l2r='S';}
                        else       {l2=h2-dr[vdr].cant;l2r='D';}
            gasit=1;
            }
    h2-=dr[vdr--].cant;
}   

if (l1==0) l1r=l2r;
if (l2==0) l2r=l1r;
        
// scriu rezultatele in fisier
g<<mij<<"\n";
if (l1r=='D'&&l2r=='S')
        {
        g<<l2<<" "<<l2r<<"\n";
        g<<l1<<" "<<l1r<<"\n";
        }
    else
        if (l1r=='S'&&l2r=='D')
                {
                g<<l1<<" "<<l1r<<"\n";
                g<<l2<<" "<<l2r<<"\n";
                }
            else
                if (l1>l2)
                        {
                        g<<l1<<" "<<l1r<<"\n";
                        g<<l2<<" "<<l2r<<"\n";
                        }
                    else
                        {
                        g<<l2<<" "<<l2r<<"\n";
                        g<<l1<<" "<<l1r<<"\n";
                        }

                

f.close();
g.close();
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 #1065 Vase1

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