0698 - nrpits: Difference between revisions
No edit summary Tag: visualeditor |
|||
Line 1: | Line 1: | ||
== Enunt == | == Enunt == | ||
Se dă un șir de N numere distincte a[1],a[2],..a[N]. Orice secvență a[i],a[i+1],...,a[j-1],a[j], 1 ≤ i + 1 < j ≤ n, pentru care toate valorile a[k], i < k < j, sunt mai mici decât extremitățile a[i] și a[j], o vom numi în continuare “groapă”. | Se dă un șir de <code>N</code> numere distincte <code>a[1],a[2],..a[N]</code>. Orice secvență <code>a[i],a[i+1],...,a[j-1],a[j]</code>, <code>1 ≤ i + 1 < j ≤ n</code>, pentru care toate valorile <code>a[k]</code>, <code>i < k < j</code>, sunt mai mici decât extremitățile <code>a[i]</code> și <code>a[j]</code>, o vom numi în continuare “groapă”. | ||
= Cerința = | |||
Scrieţi un program care va determina numărul “gropilor” din șirul dat. | Scrieţi un program care va determina numărul “gropilor” din șirul dat. | ||
= Date de intrare = | |||
Fișierul de intrare <code>nrpitsIN.txt</code> conţine pe prima linie numărul natural N. Pe linia a doua se află scrise cele N numere naturale ale șirului, separate prin spațiu. | |||
Fișierul de intrare | |||
== | = Date de ieșire = | ||
Fișierul de ieșire <code>nrpitsOUT.txt</code> va conține un singur număr reprezentând numărul de “gropi” ale șirului dat. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse". | |||
= Restricții și precizări = | |||
* <code>2 ≤ N ≤ 1.000.000</code> | |||
* <code>1 ≤ a[i] ≤ 1.000.000</code>, pentru fiecare <code>1 ≤ i ≤ N</code> | |||
* orice “groapă” are cel puțin trei elemente | |||
= Exemplul 1: = | |||
<code>nrpitsIN.txt</code> | |||
12 | |||
12 1 10 3 4 11 5 8 7 9 2 6 | |||
<code>nrpitsOUT.txt</code> | |||
8 | |||
: | = Explicație = | ||
Cele opt “gropi” sunt: | |||
<code>12 1 10</code> | |||
<code>10 3 4</code> | |||
<code>12 1 10 3 4 11</code> | |||
<code>10 3 4 11</code> | |||
<code>11 5 8</code> | |||
<code>8 7 9</code> | |||
<code>9 2 6</code> | |||
<code>11 5 8 7 9</code> | |||
== Exemplul 2: == | |||
<code>nrpitsIN.txt</code> | |||
1000001 | |||
12 1 10 3 4 11 5 8 7 9 2 6 | |||
<code>nrpitsOUT.txt</code> | |||
Datele nu corespund restrictiilor impuse | |||
== Rezolvare == | == Rezolvare == | ||
<syntaxhighlight lang="python3" line="1"> | <syntaxhighlight lang="python3" line="1"> | ||
def verifica_restricții(n, v): | |||
# Verificăm dacă N respectă restricțiile | |||
if not (2 <= n <= 1_000_000): | |||
return False | |||
# Verificăm dacă fiecare element din v respectă restricțiile | |||
for val in v: | |||
if not (1 <= val <= 1_000_000): | |||
return False | |||
return True | |||
def main(): | |||
with open("nrpitsIN.txt", "r") as fin: | |||
n = int(fin.readline()) | |||
v = list(map(int, fin.readline().split())) | |||
# | # Verificăm restricțiile | ||
if not verifica_restricții(n, v): | |||
with open("nrpitsOUT.txt", "w") as fout: | |||
fout.write("Datele nu corespund restrictiilor impuse") | |||
return # Oprim execuția dacă datele nu respectă restricțiile | |||
# Continuăm procesarea datelor deoarece acestea respectă restricțiile | |||
v = [0] + v | |||
st = [-1] * (n + 1) | |||
dr = [-1] * (n + 1) | |||
s = [] | |||
for i in range(1, n + 1): | |||
while s and v[i] > v[s[-1]]: | |||
s.pop() | |||
if s: | |||
st[i] = s[-1] | |||
s.append(i) | |||
d = [] | |||
for i in range(n, 0, -1): | |||
while d and v[i] > v[d[-1]]: | |||
d.pop() | |||
if d: | |||
dr[i] = d[-1] | |||
d.append(i) | |||
ans = sum(1 for i in range(1, n + 1) if st[i] != -1 and dr[i] != -1) | |||
with open("nrpitsOUT.txt", "w") as fout: | |||
fout.write(str(ans)) | |||
if __name__ == "__main__": | |||
main() | |||
</syntaxhighlight> | </syntaxhighlight> |
Latest revision as of 20:01, 23 February 2024
Enunt[edit]
Se dă un șir de N
numere distincte a[1],a[2],..a[N]
. Orice secvență a[i],a[i+1],...,a[j-1],a[j]
, 1 ≤ i + 1 < j ≤ n
, pentru care toate valorile a[k]
, i < k < j
, sunt mai mici decât extremitățile a[i]
și a[j]
, o vom numi în continuare “groapă”.
Cerința[edit]
Scrieţi un program care va determina numărul “gropilor” din șirul dat.
Date de intrare[edit]
Fișierul de intrare nrpitsIN.txt
conţine pe prima linie numărul natural N. Pe linia a doua se află scrise cele N numere naturale ale șirului, separate prin spațiu.
Date de ieșire[edit]
Fișierul de ieșire nrpitsOUT.txt
va conține un singur număr reprezentând numărul de “gropi” ale șirului dat. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".
Restricții și precizări[edit]
2 ≤ N ≤ 1.000.000
1 ≤ a[i] ≤ 1.000.000
, pentru fiecare1 ≤ i ≤ N
- orice “groapă” are cel puțin trei elemente
Exemplul 1:[edit]
nrpitsIN.txt
12 12 1 10 3 4 11 5 8 7 9 2 6
nrpitsOUT.txt
8
Explicație[edit]
Cele opt “gropi” sunt:
12 1 10
10 3 4
12 1 10 3 4 11
10 3 4 11
11 5 8
8 7 9
9 2 6
11 5 8 7 9
Exemplul 2:[edit]
nrpitsIN.txt
1000001 12 1 10 3 4 11 5 8 7 9 2 6
nrpitsOUT.txt
Datele nu corespund restrictiilor impuse
Rezolvare[edit]
<syntaxhighlight lang="python3" line="1"> def verifica_restricții(n, v):
# Verificăm dacă N respectă restricțiile if not (2 <= n <= 1_000_000): return False # Verificăm dacă fiecare element din v respectă restricțiile for val in v: if not (1 <= val <= 1_000_000): return False return True
def main():
with open("nrpitsIN.txt", "r") as fin: n = int(fin.readline()) v = list(map(int, fin.readline().split()))
# Verificăm restricțiile if not verifica_restricții(n, v): with open("nrpitsOUT.txt", "w") as fout: fout.write("Datele nu corespund restrictiilor impuse") return # Oprim execuția dacă datele nu respectă restricțiile
# Continuăm procesarea datelor deoarece acestea respectă restricțiile v = [0] + v st = [-1] * (n + 1) dr = [-1] * (n + 1)
s = [] for i in range(1, n + 1): while s and v[i] > v[s[-1]]: s.pop() if s: st[i] = s[-1] s.append(i)
d = [] for i in range(n, 0, -1): while d and v[i] > v[d[-1]]: d.pop() if d: dr[i] = d[-1] d.append(i)
ans = sum(1 for i in range(1, n + 1) if st[i] != -1 and dr[i] != -1)
with open("nrpitsOUT.txt", "w") as fout: fout.write(str(ans))
if __name__ == "__main__":
main()
</syntaxhighlight>