Fișierul intrare/ieșire vase.in, vase.out Sursă OJI 2011, clasa a 9-a
Autor Ciprian Cheșcă Adăugată de avatar ReksioCroft Staicu Octavian Florin ReksioCroft
Timp de execuție pe test 0.25 sec Limită de memorie 5120 KB
Scorul tău N/A Dificultate N/A

Vase (clasa a 9-a)

!Are nevoie de evaluator

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 Vi (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: V1=4 lichid de culoare 1 introdus prin ramura din dreapta (operație codificată 4 D), V2=4 lichid de culoare 2 introdus prin ramura din stânga (operație codificată 4 S) și V3=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 Vi ș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 vase.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 vase.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

  • 1 ≤ x ≤ n ≤ 100 000
  • 2 ≤ Vi ≤ 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

vase.in vase.out
3
4 D
4 S
2 S
2
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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii