2939 - Permutari4

Cerința

O permutare de ordin K este formată din toate numerele 1, 2, …, K nu neapărat în această ordine.

O secvență de lungime L este formată din L elemente ale șirului aflate pe poziții consecutive. Spunem că o secvență de lungime L este permutare de ordin L dacă ea conține toate numerele 1, 2, …, L, nu neapărat în această ordine.

Se dă un șir de N numere naturale nenule , ce reprezintă o permutare de ordin N. Să se calculeze numărul secvențelor din șirul a care au proprietatea că sunt permutări.

Date de intrare

Fișierul de intrare input.txt conține pe prima linie numărul natural N, iar pe a doua linie se află primele N numere naturale nenule, separate prin spațiu. Cele N numere date nu sunt obligatoriu în ordine strict crescătoare.

Date de ieșire

În fișierul de ieșire output.txt se va scrie un singur număr natural reprezentând numărul secvențelor de tip permutare care apar în şirul dat.

Restricții și precizări

• 1 < N ≤ 100.000

Exemplul 1

input.txt:

7

4 2 5 1 3 7 6

output.txt:

3

Explicație:

În şir există 3 secvențe de tip permutare, de lungimi 1, 5 şi 7:

1

4 2 5 1 3

4 2 5 1 3 7 6

Nu există secvențe permutare de lungime 2, 3, 4 sau 6.

Exemplul 2

input.txt:

9999999999999

4 2 5 1 3 7 6

Output:

Input-ul nu convine conditiilor

Rezolvare

<syntaxhighlight lang="python3" line="1"> def verificare(n):

   if not(1<=n<=100000):
       print("Input-ul nu convine conditiilor")
       exit()

f=open("input.txt","r") w=open("output.txt","w")

n=f.readline().split() n=int(n[0]) verificare(n) q={} r=0 v=f.readline().split() for i in range(len(v)):

   q[int(v[i])]=i+1

if 1 not in q:

   q[1]=0

if q[1]!=0:

   r+=1

a=q[1] b=q[1] for i in range(1,len(v)):

   if i not in q:
       q[i]=0
   if q[i]<a:
       a=q[i]
   if q[i]>b:
       b=q[i]
   if b-a+1==i:
       r+=1

w.write(str(r)) w.close() </syntaxhighlight>