Raul at 17:00, 16 February 2024

2024-02-16T17:00:42Z

← Older revision		Revision as of 17:00, 16 February 2024
Line 46:		Line 46:

	=== Lipește codul aici ===		=== Lipește codul aici ===
	<syntaxhighlight lang="~~python~~">		<syntaxhighlight lang="python2">
	import sys		import sys

Raul: Pagină nouă: Considerăm un şir de numere `a₁`, `a₂`, …, `a_N`. O secvenţă nevidă în acest şir este de forma `a_i`, `a_i+1`, …, `a_j`, unde `i ≤ j`. De exemplu, pentru `N=4` şi şirul `2 3 4 3`, secvenţele nevide sunt: `2`, `2 3`, `2 3 4`, `2 3 4 3`, `3`, `...`


2024-02-16T16:59:34Z
Pagină nouă: Considerăm un şir de numere  <code>a<sub>1</sub></code>, <code>a<sub>2</sub></code>, …, <code>a<sub>N</sub></code>. O secvenţă nevidă în acest şir este de forma <code>a<sub>i</sub></code>, <code>a<sub>i+1</sub></code>, …, <code>a<sub>j</sub></code>, unde <code>i ≤ j</code>. De exemplu, pentru <code>N=4</code> şi şirul <code>2 3 4 3</code>, secvenţele nevide sunt: <code>2</code>, <code>2 3</code>, <code>2 3 4</code>, <code>2 3 4 3</code>, <code>3</code>, <code>...
New page
Considerăm un şir de numere  <code>a<sub>1</sub></code>, <code>a<sub>2</sub></code>, …, <code>a<sub>N</sub></code>. O secvenţă nevidă în acest şir este de forma <code>a<sub>i</sub></code>, <code>a<sub>i+1</sub></code>, …, <code>a<sub>j</sub></code>, unde <code>i ≤ j</code>. De exemplu, pentru <code>N=4</code> şi şirul <code>2 3 4 3</code>, secvenţele nevide sunt: <code>2</code>, <code>2 3</code>, <code>2 3 4</code>, <code>2 3 4 3</code>, <code>3</code>, <code>3 4</code>, <code>3 4 3</code>, <code>4</code>, <code>4 3</code>, <code>3</code>. Definim puterea unui element <code>a<sub>i</sub></code> ca fiind numărul de secvenţe care-l conţin pe <code>a<sub>i</sub></code> şi în care <code>a<sub>i</sub></code> este strict mai mare decât celelalte elemente ale fiecăreia dintre respectivele secvenţe. Astfel în şirul <code>2 3 4 3</code> puterea elementului <code>a<sub>1</sub></code> este <code>1</code> (fiind maxim doar în secvenţa formată din el însuşi), a elementului <code>a<sub>2</sub></code> este <code>2</code> (<code>a<sub>2</sub></code> fiind maxim în secvenţele <code>2 3</code> şi <code>3</code>), a elementului <code>a<sub>3</sub></code> este <code>6</code> (fiind maxim în secvenţele <code>2 3 4</code>, <code>2 3 4 3</code>, <code>3 4</code>, <code>3 4 3</code>, <code>4</code> şi <code>4 3</code>), iar a elementului <code>a<sub>4</sub></code> este <code>1</code>.



= Cerinţe =

Scrieţi un program care determină puterea cea mai mare a unui element din şirul dat, precum şi numărul de elemente din şir care au cea mai mare putere.



= Date de intrare =

Fișierul de intrare <code>maxp.in</code> conține pe prima linie numărul natural <code>N</code>, iar pe a doua linie, în ordine, numerele naturale <code>a<sub>1</sub></code>, <code>a<sub>2</sub></code>, …, <code>a<sub>N</sub></code> separate prin câte un spaţiu.



= Date de ieșire =

Fișierul de ieșire <code>maxp.out</code> va conține pe prima linie un număr natural ce reprezintă puterea cea mai mare a unui element din şirul dat şi pe a doua linie va conţine un număr natural ce reprezintă numărul de elemente din şir care au cea mai mare putere.



= Restricții și precizări =



* <code>2 <= N <= 200.000</code>

* Elementele şirului sunt numere naturale şi au cel mult <code>6</code> cifre



= Exemplul 1 =

<code>maxp.in</code>

 7

 9 3 4 5 1 2 2

<code>maxp.out</code>

 12 

 1



= Explicație =

Elementul <code>5</code> de pe poziţia <code>4</code> este maxim în <code>12</code> secvenţe: 



<code>3 4 5</code>, <code>3 4 5 1</code>, <code>3 4 5 1 2</code>, <code>3 4 5 1 2 2</code>, <code>4 5</code>, 



<code>4 5 1</code>, <code>4 5 1 2</code>, <code>4 5 1 2 2</code>, <code>5</code>, <code>5 1</code>, <code>5 1 2</code>, 



<code>5 1 2 2</code>, deci puterea lui este <code>12</code>. Este singurul element care are această putere, celelalte elemente având puteri mai mici.



= Exemplul 2 =

<code>maxp.in</code>

 6

 1 0 7 7 2 6

<code>maxp.out</code>

 3 

 2



= Explicație =

Elementele din poziţiile <code>3</code> şi <code>4</code> sunt maxime în <code>3</code> secvenţe, deci puterea lor este <code>3</code>. Celelalte elemente au puteri mai mici.



== Încărcare soluție ==



=== Lipește codul aici ===

<syntaxhighlight lang="python">

import sys



inFile = "maxp.intxt"

outFile = "maxp.outtxt"

dim = 200001



a = [0] * dim

st = [0] * dim

dr = [0] * dim

q = [0] * dim

poz = [0] * dim

n = 0



def main():

    global n

    i, k, x, nrsol, p, pmax = 0, 0, 0, 0, 0, 0

    

    #citire

    with open(inFile, 'r') as fin:

        n = int(fin.readline())

        for i in range(1, n+1):

            a[i] = int(fin.readline())

    

    # constructie st

    k = 0

    q[k] = dim + 2

    poz[k] = 0

    st[k] = 0

    for i in range(1, n+1):

        x = a[i]

        while q[k] < x:

            k -= 1

        st[i] = i - poz[k] - 1

        k += 1

        q[k] = x

        poz[k] = i

    

    # constructie dr

    k = 0

    q[k] = dim + 2

    poz[k] = n + 1

    dr[k] = 0

    for i in range(n, 0, -1):

        x = a[i]

        while q[k] < x:

            k -= 1

        dr[i] = poz[k] - i - 1

        k += 1

        q[k] = x

        poz[k] = i



    # calcul

    nrsol = 1

    pmax = (st[1] + 1)

    pmax *= (dr[1] + 1)

    for i in range(2, n+1):

        p = (st[i] + 1)

        p = (p * (dr[i] + 1))

        if p > pmax:

            pmax = p

            nrsol = 1

        elif p == pmax:

            nrsol += 1

    

    with open(outFile, 'w') as fout:

        fout.write(str(pmax) + "\n" + str(nrsol) + "\n")



if __name__ == "__main__":

    main()

</syntaxhighlight>

1057 - Max P - Revision history

Raul at 17:00, 16 February 2024

Raul: Pagină nouă: Considerăm un şir de numere a1, a2, …, aN. O secvenţă nevidă în acest şir este de forma ai, ai+1, …, aj, unde i ≤ j. De exemplu, pentru N=4 şi şirul 2 3 4 3, secvenţele nevide sunt: 2, 2 3, 2 3 4, 2 3 4 3, 3, ...

Raul: Pagină nouă: Considerăm un şir de numere `a₁`, `a₂`, …, `a_N`. O secvenţă nevidă în acest şir este de forma `a_i`, `a_i+1`, …, `a_j`, unde `i ≤ j`. De exemplu, pentru `N=4` şi şirul `2 3 4 3`, secvenţele nevide sunt: `2`, `2 3`, `2 3 4`, `2 3 4 3`, `3`, `...`