0694 - Sam - Revision history

RebecaBud: Pagină nouă: == Enunt == Aranjăm primele N numere naturale nenule sub forma unui șir A[1], A[2], ..., A[N]. Fie X[1], X[2],...,X[K] (K ≥ 3), un subșir al șirului A. Numim extrem local al subșirului X termenul din mijlocul unei secvențe de lungime trei din subșir, X[i-1], X[i], X[i+1], cu proprietatea: X[i-1]X[i+1], 1X[i]
2024-06-03T16:51:08Z

Pagină nouă: == Enunt == Aranjăm primele N numere naturale nenule sub forma unui șir A[1], A[2], ..., A[N]. Fie X[1], X[2],...,X[K] (K ≥ 3), un subșir al șirului A. Numim extrem local al subșirului X termenul din mijlocul unei secvențe de lungime trei din subșir, X[i-1], X[i], X[i+1], cu proprietatea: X[i-1]<X[i]>X[i+1], 1<i<K sau X[i-1]>X[i]<X[i+1], 1<i<K. Vom nota cu nrex(X) numărul de extreme locale ale subșirului X. Spunem că un subșir X[1], X[2],...,X[K] (K≥2) al...

New page
== Enunt ==

Aranjăm primele N numere naturale nenule sub forma unui șir A[1], A[2], ..., A[N].

Fie X[1], X[2],...,X[K] (K ≥ 3), un subșir al șirului A. Numim extrem local al subșirului X termenul din mijlocul unei secvențe de lungime trei din subșir, X[i-1], X[i], X[i+1], cu proprietatea: X[i-1]<X[i]>X[i+1], 1<i<K sau X[i-1]>X[i]<X[i+1], 1<i<K.

Vom nota cu nrex(X) numărul de extreme locale ale subșirului X.

Spunem că un subșir X[1], X[2],...,X[K] (K≥2) al șirului A este subșir alternant dacă nrex(X)=K-2, adică exceptând primul și ultimul termen din subșir toți ceilalți termeni sunt extreme locale ale subșirului X.

Dintre toate subșirurile alternante ale șirului A ne interesează cele de lungime maximă pe care le vom numi subșiruri alternante maximale.
== Cerinţa ==
Cunoscând N și tabloul A se cere să se determine restul obținut la împărțirea dintre numărul M al subșirurilor alternante maximale ale tabloului A și numărul 1000003.
== Date de intrare ==
Fișierul de intrare sam.in conţine pe prima linie numărul natural N. Pe linia a doua se găsesc cele N numere ale șirului dat separate prin câte un spațiu.
== Date de ieșire ==
În fişierul de ieşire sam.out se va scrie numărul obţinut ca rest la împărţirea dintre numărul M, având semnificația descrisă mai sus, şi numărul 1000003.
== Restricţii şi precizări ==
* '''3 ≤ N ≤ 100 000'''
== Exemplul 1 ==
; sam.in

7
1 3 5 4 7 6 2
; sam.out

6
== Explicație ==
Șirul dat conține trei extreme locale , valorile 5, 4 și 7. Cele șase subșiruri alternante maximale cu șirul dat sunt: (1 5 4 6 2), (1 5 4 7 2), (1 5 4 7 6), (3 5 4 6 2), (3 5 4 7 2), (3 5 4 7 6)
<br>

== Rezolvare ==
<syntaxhighlight lang="python" line>
def count_alternating_subsequences(N, A):
count = 0

for i in range(1, N - 1):
if (A[i - 1] < A[i] > A[i + 1]) or (A[i - 1] > A[i] < A[i + 1]):
count += 1

return count

def main():
with open("sam.in", "r") as fin:
N = int(fin.readline())
A = list(map(int, fin.readline().split()))

M = count_alternating_subsequences(N, A)

with open("sam.out", "w") as fout:
fout.write(str(M % 1000003))

if name == "main":
main()

</syntaxhighlight>