Raul: Pagină nouă: Se consideră un şir `x₁`, `x₂`,…, `x_n` format din `n` numere naturale distincte. O secvenţă de număr maxim de elemente vecine în şir, de forma `x_i`, `x_i+1`,…, `x_k-1`, `x_k`, `x_k+1`,…, `x_j` (`1≤i) cu proprietatea că x_i...`


2024-01-31T15:47:15Z
Pagină nouă: Se consideră un şir <code>x<sub>1</sub></code>, <code>x<sub>2</sub></code>,…, <code>x<sub>n</sub></code> format din <code>n</code> numere naturale distincte. O secvenţă de număr maxim de  elemente vecine în şir, de forma <code>x<sub>i</sub></code>, <code>x<sub>i+1</sub></code>,…, <code>x<sub>k-1</sub></code>, <code>x<sub>k</sub></code>, <code>x<sub>k+1</sub></code>,…, <code>x<sub>j</sub></code> (<code>1≤i<k<j≤n</code>) cu proprietatea că <code>x<sub>i</sub>...
New page
Se consideră un şir <code>x<sub>1</sub></code>, <code>x<sub>2</sub></code>,…, <code>x<sub>n</sub></code> format din <code>n</code> numere naturale distincte. O secvenţă de număr maxim de  elemente vecine în şir, de forma <code>x<sub>i</sub></code>, <code>x<sub>i+1</sub></code>,…, <code>x<sub>k-1</sub></code>, <code>x<sub>k</sub></code>, <code>x<sub>k+1</sub></code>,…, <code>x<sub>j</sub></code> (<code>1≤i<k<j≤n</code>) cu proprietatea că <code>x<sub>i</sub> < x<sub>i+1</sub> < ...< x<sub>k-1</sub> < x<sub>k</sub> > x<sub>k+1</sub> > ... > x<sub>j</sub></code>, se numeşte munte cu vârful <code>x<sub>k</sub></code>. Două secvenţe munte au maxim un element comun în şir. O secvenţă munte are cel puţin <code>3</code> elemente. Un exemplu de şir format cu valorile <code>3 4 6 8</code> nu conţine nicio secvenţă munte, iar unul format cu valorile <code>3 4 8 1 2 5 0</code> conţine <code>2</code> secvenţe munte: <code>3 4 8 1</code> şi <code>1 2 5 0</code>.



După determinarea tuturor secvenţelor munte şi a vârfurilor acestora, se elimină din şir vârfurile secvenţelor munte şi procedura continuă repetat cu determinarea noilor secvenţe munte şi a vârfurilor lor din şirul nou obţinut. Procedura se opreşte în momentul în care în şir nu mai există nicio secvenţă munte.



= Cerința =

Scrieţi un program care citeşte numerele <code>n</code>, <code>x<sub>1</sub></code>, <code>x<sub>2</sub></code>, …, <code>x<sub>n</sub></code> şi apoi determină:



a) numărul de secvenţe munte din şirul iniţial;



b) numărul total de secvenţe munte obţinute pornind de la şirul iniţial până la cel care nu mai conţine nicio secvenţă munte;



c) numărul de elemente din şirul final care nu mai conţine secvenţe munte.



= Date de intrare =

Fișierul de intrare <code>munte.in</code> conține pe prima linie numărul <code>n</code>, iar pe următoarea linie numerele naturale  <code>x<sub>1</sub></code>, <code>x<sub>2</sub></code>,…, <code>x<sub>n</sub></code> separate două câte două prin câte un spaţiu.



= Date de ieșire =

Fișierul de ieșire <code>munte.out</code> va conține pe prima linie un număr natural conform cerinţei a), pe a doua linie un număr natural conform cerinţei b), pe a treia linie un număr natural conform cerinţei c).



= Restricții și precizări =



* <code>3 ≤ n ≤ 100</code>

* <code>0 ≤ x<sub>i</sub> ≤ 100000</code>, <code>1 ≤ i ≤ n</code>

* Pentru rezolvarea corectă a cerinţei a)  se obţine <code>20%</code> din punctaj.

* Pentru rezolvarea corectă a cerinţei b)  se obţine <code>40%</code> din punctaj.

* Pentru rezolvarea corectă a cerinţei c)  se obţine <code>40%</code> din punctaj. Pentru testele date se asigură că şirul de numere dat iniţial conţine cel puţin o secvenţă munte.



= Exemplu: =

<code>munte.in</code>

 8

 1 2 5 0 6 9 3 4

<code>munte.out</code>

 2

 4

 4



= Explicație =

a) Sunt două secvenţe munte: <code>1 2 5 0</code> şi <code>0 6 9 3</code>



b) După eliminarea vârfurilor secvenţelor munte, şirul nou este <code>1 2 0 6 3 4</code>. Acest şir conţine <code>2</code> secvenţe munte: <code>1 2 0</code> şi <code>0 6 3</code>. După eliminarea vârfurilor secvenţelor munte, şirul nou este <code>1 0 3 4</code>. Noul şir nu mai conţine nicio secvenţă munte. În total sunt deci <code>4</code> secvenţe.



c) Şirul final care nu mai conţine secvenţe munte <code>1 0 3 4</code> are <code>4</code> elemente



== Încărcare soluție ==



=== Lipește codul aici ===

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

MAX = 1000000



fin = open("munte.in", "r")

fout = open("munte.out", "w")



n = 0

i = 0

j = 0

parcurgere = 0

munti = 0

cati = 0

x = [0] * 110

gasit_munte = False



n = int(fin.readline())

x = list(map(int, fin.readline().split()))



parcurgere = 1

gasit_munte = True

while gasit_munte:

    gasit_munte = False

    cati = 0

    i = 0

    while i < n and x[i] > x[i + 1]:

        i += 1

    while i <= n:

        while i < n and x[i] < x[i + 1]:

            i += 1

        if i < n:

            munti += 1

            cati += 1

            x[i] = MAX

            gasit_munte = True

        while i < n and x[i] > x[i + 1]:

            i += 1

        if i < n and x[i] > x[i - 1]:

            i -= 1

        else:

            if i == n:

                break

    if parcurgere == 1:

        fout.write(str(munti) + '\n')

        parcurgere += 1

    i = 0

    while i < n:

        while x[i] != MAX and i < n:

            i += 1

        for j in range(i, n):

            x[j] = x[j + 1]

    if gasit_munte:

        n -= cati



fout.write(str(munti) + '\n')

fout.write(str(n) + '\n')

fin.close()

fout.close()

</syntaxhighlight>

1046 - Munte - Revision history

Raul: Pagină nouă: Se consideră un şir x1, x2,…, xn format din n numere naturale distincte. O secvenţă de număr maxim de elemente vecine în şir, de forma xi, xi+1,…, xk-1, xk, xk+1,…, xj (1≤i) cu proprietatea că xi...

Raul: Pagină nouă: Se consideră un şir `x₁`, `x₂`,…, `x_n` format din `n` numere naturale distincte. O secvenţă de număr maxim de elemente vecine în şir, de forma `x_i`, `x_i+1`,…, `x_k-1`, `x_k`, `x_k+1`,…, `x_j` (`1≤i) cu proprietatea că x_i...`