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ţă[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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:[edit | edit source]

vase1.in

vase1.out

5
3 S
1 D

Explicație[edit | edit source]

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.

Încărcare soluție[edit | edit source]

Lipește codul aici[edit | edit source]

<syntaxhighlight lang="python" line="1"> import sys

nmax = 100001

class Lichid:

   def __init__(self, cantitate, ramura, culoare):
       self.cant = cantitate
       self.ram = ramura
       self.cul = culoare

st = [None] * nmax dr = [None] * nmax vst = 0 vdr = 0

f = open("vase1.in", "r") g = open("vase1.out", "w")

def main():

   i = 0
   n = 0
   x = 0
   z = 0
   mij = 0
   l1 = 0
   l2 = 0
   h1 = 0
   h2 = 0
   gasit = 0
   s = 0
   l1r = ' '
   l2r = ' '

   n = int(f.readline())

   for i in range(1, n+1):
       line = f.readline().split()
       x = int(line[0])
       c = line[1]
       s += x
       if c == 'S':
           vst += 1
           st[vst] = Lichid(x, c, i)
       elif c == 'D':
           vdr += 1
           dr[vdr] = Lichid(x, c, i)
   
   z = int(f.readline())

   mij = s // 2
   h1 = mij
   gasit = 0

   while h1 > -mij and vst > 0 and not 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
       vst -= 1

   h2 = mij

   while h2 > -mij and vdr > 0 and not 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
       vdr -= 1
   
   if l1 == 0:
       l1r = l2r
   if l2 == 0:
       l2r = l1r

   g.write(str(mij) + "\n")

   if l1r == 'D' and l2r == 'S':
       g.write(str(l2) + " " + l2r + "\n")
       g.write(str(l1) + " " + l1r + "\n")
   elif l1r == 'S' and l2r == 'D':
       g.write(str(l1) + " " + l1r + "\n")
       g.write(str(l2) + " " + l2r + "\n")
   elif l1 > l2:
       g.write(str(l1) + " " + l1r + "\n")
       g.write(str(l2) + " " + l2r + "\n")
   else:
       g.write(str(l2) + " " + l2r + "\n")
       g.write(str(l1) + " " + l1r + "\n")

   f.close()
   g.close()

if __name__ == "__main__":

   main()

</syntaxhighlight>