Vizualizare sursă pentru „1046 - Munte”

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>