Vizualizare sursă pentru „2197 - taietura”

== Enunt ==

Fiind dat un șir <code>V</code> format din <code>N</code> numere întregi <code>V[1]</code>, …, <code>V[N]</code>, definim o tăietură în poziția <code>pos</code> ca fiind o subsecvență care conține elementul de pe poziția <code>pos</code>. Formal, tăieturile în poziția <code>pos</code> sunt de forma <code>V[k]</code>, <code>V[k+1]</code>, …, <code>V[pos]</code>, …, <code>V[r-1]</code>, <code>V[r]</code> pentru orice <code>k</code>, <code>1 ≤ k ≤ pos</code> și orice <code>r</code>, <code>pos ≤ r ≤ N</code>. Valoarea unei tăieturi este suma tuturor elementelor care fac parte din tăietura respectivă. Definim funcția <code>MulT(pos)</code> ca fiind numărul de tăieturi în poziția <code>pos</code> care au valoarea <code>0</code>.

= Cerința =
Ioana, fiind foarte curioasă din fire, dar și foarte fascinată de această funcție numită <code>MulT</code>, este foarte interesată în a afla rezultatul pentru <code>MulT(i)</code>, unde <code>1 ≤ i ≤ N</code>.

= Date de intrare =
Fișierul de intrare <code>taietura.in</code> conţine pe prima linie un număr natural <code>N</code>, reprezentând numărul de elemente din șirul <code>V</code>. Următoarea linie va conține exact <code>N</code> valori întregi despărțite prin câte un spațiu, și anume elementele șirului <code>V</code>.

= Date de ieșire =
Fișierul de ieșire <code>taietura.out</code> va conţine pe prima linie <code>N</code> numere naturale separate prin câte un spațiu, și anume valorile funcției <code>MulT(i)</code>, unde <code>1 ≤ i ≤ N</code>. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ N ≤ 100 000</code>
* Orice element al șirului <code>V</code> este mai mic sau egal în valoare absolută cu <code>1 000 000 000</code>
* Pentru teste în valoare de <code>20</code> de puncte <code>N ≤ 100</code>
* Pentru teste în valoare de încă <code>20</code> de puncte <code>N ≤ 1000</code>

= Exemplul 1: =
<code>taieturaIN.txt</code>
 3
 0 1 0
<code>taieturaOUT.txt</code>
 1 0 1

=== Explicație ===
Rezultatul pentru <code>MulT(1)</code> este <code>1</code> deoarece există o singură tăietură, și anume <code>(0)</code> care are valoarea <code>0</code>. Pentru <code>MulT(2)</code> rezultatul este <code>0</code> deoarece nu există nicio tăietură aplicată pe poziția <code>2</code> care să aibă valoarea <code>0</code>. Rezultatul pentru <code>MulT(3)</code> este <code>1</code> deoarece există o unică tăietură, si anume <code>(0)</code> care are valoarea <code>0</code>.

== Exemplul 1: ==
<code>taieturaIN.txt</code>
 3
 0 1 0
<code>taieturaOUT.txt</code>
 1 0 1

== Rezolvare ==

<syntaxhighlight lang="python3" line="1">
def verificare_restrictii(N):
    if not (1 <= N <= 100000):
        with open("taieturaOUT.txt", "w") as f_out:
            f_out.write("Datele nu corespund restrictiilor impuse\n")
        return False
    return True

def main():
    with open("taieturaIN.txt", "r") as f_in, open("taieturaOUT.txt", "w") as f_out:
        N = int(f_in.readline().strip())
        if not verificare_restrictii(N):
            return

        V = [0] + list(map(int, f_in.readline().split()))
        if not all(-1000000000 <= v <= 1000000000 for v in V[1:]):
            with open("taieturaOUT.txt", "w") as f_out:
                f_out.write("Datele nu corespund restrictiilor impuse\n")
            return

        partial_sum = [0] * (N + 1)
        for i in range(1, N + 1):
            partial_sum[i] = partial_sum[i - 1] + V[i]

        sums = sorted(set(partial_sum))

        mars = [0] * (N + 1)
        count = [0] * len(sums)

        for i in range(N + 1):
            sum_index = sums.index(partial_sum[i])
            to_the_left = count[sum_index]
            if i < N:
                mars[i + 1] -= to_the_left
            count[sum_index] += 1

        for i in range(N):
            sum_index = sums.index(partial_sum[i])
            count[sum_index] -= 1
            to_the_right = count[sum_index]
            mars[i + 1] += to_the_right

        answer = 0
        for i in range(1, N + 1):
            answer += mars[i]
            f_out.write(f"{answer} ")

if __name__ == "__main__":
    main()

</syntaxhighlight>