Editing 1075 - Grad 1

Se consideră un şir <code>x<sub>1</sub></code>, <code>x<sub>2</sub></code>, …, <code>x<sub>n</sub></code> de <code>n</code> numere naturale distincte, două câte două. Pentru o secvenţă de <code>k</code> numere <code>(x<sub>p</sub>, x<sub>p+1</sub>, ..., x<sub>p+k-1</sub>)</code>, care începe cu numărul de pe poziţia <code>p</code> din şirul dat, definim gradul său ca fiind numărul de numere din secvenţă, care rămân pe aceleaşi poziţii după ordonarea crescătoare a secvenţei. De exemplu, pentru <code>n=7</code> şi şirul  format din numerele:  <code>1, 5, 7, 4, 6, 2, 9</code>,  secvenţa formată din  numerele <code>7, 4, 6, 2</code> (corespunzătoare lui <code>p=3</code> şi <code>k=4</code>) are gradul egal cu <code>2</code> deoarece, după ordonarea crescătoare a numerelor din secvenţă, aceasta devine <code>2, 4, 6, 7</code>, numerele <code>4</code> şi <code>6</code> rămânând pe aceleaşi poziţii.

= Cerinţă =
Scrieţi un program care citeşte numerele <code>n</code>, <code>k</code>, <code>x<sub>1</sub></code>, <code>x<sub>2</sub></code>, …, <code>x<sub>n</sub></code>, cu semnificaţia din enunţ, şi apoi determină:

a) gradul întregului şir de numere;

b) poziţia primului element din prima secvenţă de lungime <code>k</code> ce are gradul maxim, precum şi gradul acestei secvenţe.

= Date de intrare =
Fișierul de intrare <code>grad1.in</code> conține pe prima linie numerele <code>n</code> şi <code>k</code>, separate printr-un spaţiu, iar pe linia următoare <code>n</code> numere naturale distincte <code>x<sub>1</sub></code>, <code>x<sub>2</sub></code>, …, <code>x<sub>n</sub></code>, corespunzătoare şirului de numere, separate prin câte un spaţiu.

= Date de ieșire =
Fișierul de ieșire <code>grad1.out</code> va conține pe prima linie un număr natural reprezentând gradul întregului şir de numere, iar pe următoarea linie două numere naturale, separate printr-un singur spaţiu, primul număr reprezentând poziţia primului element din prima secvenţă de lungime <code>k</code> ce are grad maxim şi cel de-al doilea număr reprezentând gradul acestei secvenţe.

= Restricții și precizări =

* <code>0 < n < 10001</code>
* <code>0 < k < n+1</code>
* Numerele din şir sunt numere naturale strict mai mici decât <code>32000</code>.
* O secvenţă de numere din şir reprezintă o succesiune de numere din acel şir, aflate pe poziţii consecutive.
* Gradul întregului şir de numere este egal cu gradul secvenţei de <code>n</code> numere care începe cu numărul de pe poziţia <code>1</code> şi conţine toate cele <code>n</code> numere din şir.
* Pentru rezolvarea corectă a subpunctului a)  se obţine 40% din punctaj.
* Pentru rezolvarea corectă a subpunctului b)  se obţine 60% din punctaj.

= Exemplu: =
<code>grad1.in</code>
 7 4
 1 5 7 4 6 2 9
<code>grad1.out</code>
 3
 3 2

= Explicație =
După ordonare, şirul <code>1 5 7 4 6 2 9</code> devine <code>1 2 4 5 6 7 9</code>, pe aceleaşi poziţii rămân <code>1</code>, <code>6</code> şi <code>9</code>, deci gradul întregului şir este <code>3</code>.

Avem patru secvenţe cu câte 4 elemente:

* <code>1 5 7 4</code>, care are gradul <code>1</code>
* <code>5 7 4 6</code>, care are gradul <code>0</code>
* <code>7 4 6 2</code>, care are primul număr pe poziţia <code>3</code> și gradul <code>2</code>.
* <code>4 6 2 9</code>, care are gradul <code>1</code>.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
def read_input(filename):
    with open(filename, 'r') as fin:
        n, k = map(int, fin.readline().split())
        x = [0] + [int(num) for num in fin.readline().split()]
    return n, k, x

def sort_subarray(y, n):
    sorted = False
    while not sorted:
        sorted = True
        for i in range(1, n):
            if y[i] > y[i + 1]:
                y[i], y[i + 1] = y[i + 1], y[i]
                sorted = False

def main():
    n, k, x = read_input("grad1.in")
    y = x.copy()
    sort_subarray(y, n)
    g = sum(1 for i in range(1, n + 1) if x[i] == y[i])
    
    with open("grad1.out", 'w') as fout:
        fout.write(f"{g}\n")
        
        y = x[1:k+1]
        sort_subarray(y, k)
        gmax = sum(1 for i in range(1, k + 1) if x[i] == y[i])
        pmax = 1
        
        for i in range(2, n - k + 2):
            j = 1
            while j <= k and y[j] != x[i - 1]:
                j += 1
            if j <= k:
                y[j] = x[i + k - 1]
                while j > 1 and y[j - 1] > y[j]:
                    y[j], y[j - 1] = y[j - 1], y[j]
                    j -= 1
                while j < k and y[j] > y[j + 1]:
                    y[j], y[j + 1] = y[j + 1], y[j]
                    j += 1
            
            gr = sum(1 for j in range(1, k + 1) if y[j] == x[i + j - 1])
            if gr > gmax:
                gmax = gr
                pmax = i
        
        fout.write(f"{pmax} {gmax}")

if __name__ == "__main__":
    main()
</syntaxhighlight>