Raul: Pagină nouă: Se consideră un şir `x₁`, `x₂`, …, `x_n` de `n` numere naturale distincte, două câte două. Pentru o secvenţă de `k` numere `(x_p, x_p+1, ..., x_p+k-1)`, care începe cu numărul de pe poziţia `p` 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 cres...

2024-02-13T14:57:34Z

Pagină nouă: Se consideră un şir <code>x1</code>, <code>x2</code>, …, <code>xn</code> de <code>n</code> numere naturale distincte, două câte două. Pentru o secvenţă de <code>k</code> numere <code>(xp, xp+1, ..., xp+k-1)</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 cres...

New page

Se consideră un şir <code>x1</code>, <code>x2</code>, …, <code>xn</code> de <code>n</code> numere naturale distincte, două câte două. Pentru o secvenţă de <code>k</code> numere <code>(xp, xp+1, ..., xp+k-1)</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>x1</code>, <code>x2</code>, …, <code>xn</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>x1</code>, <code>x2</code>, …, <code>xn</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>

1075 - Grad 1 - Revision history