Editing 1065 - Vase 1

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 <code>0</code>, <code>1</code>, <code>2</code>, <code>3</code>,…, fizicienii introduc un număr de <code>n</code> lichide, pe ramura din stânga sau pe ramura din dreapta. Volumele introduse din fiecare lichid, notate cu <code>V<sub>i</sub></code> (<code>1≤i≤n</code>), 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 <code>1</code>, <code>2</code>, <code>3</code>, … , <code>n</code>. Introducerea lichidelor în sistemul cu două  vase comunicante se face în ordinea crescătoare a numerelor culorilor, începând cu lichidul de culoare <code>1</code>.

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 <code>x</code>, dintre cele introduse.

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

= Cerinţă =
Să se scrie un program care cunoscând numărul <code>n</code> de lichide introduse în sistemul cu două vase comunicante, volumul <code>V<sub>i</sub></code> şi ramura prin care se face introducerea lichidului de culoare <code>i</code> (<code>1≤i≤n</code>), precum şi culoarea <code>x</code>, 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 <code>x</code>.

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

= Date de ieșire =
Fişierul de ieşire <code>vase1.out</code> 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 (<code>S</code> sau <code>D</code>), reprezentând gradaţia şi ramura între care se aşează lichidul căutat.

= Restricții și precizări =

* <code>1 ≤ x  ≤ n  ≤ 100 000</code>
* <code>2 ≤ V<sub>i</sub> ≤ 100 000</code> pentru <code>1 ≤ i ≤ n</code>
* 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 <code>x</code>, 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 <code>x</code>, 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 <code>x</code>, este <code>0</code> 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: =
<code>vase1.in</code>
 3
 4 D
 4 S
 2 S
 2
<code>vase1.out</code>
 5
 3 S
 1 D

= Explicație =
Se introduc <code>3</code> lichide în sistemul de două vase comunicante:

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

Se caută gradaţiile ce corespund lichidului de culoare <code>2</code>.

Gradaţia maximă la care ajunge nivelul lichidului este <code>5</code>.

Lichidul  de culoare <code>2</code> se aşează între gradaţiile <code>3</code> pe ramura din stânga şi <code>1</code> pe ramura din dreapta.

== Încărcare soluție ==

=== Lipește codul aici ===
<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>