1783 - Find Min

Cerința

Se dă un șir P de lungime N cu elemente distincte din mulțimea {1,2..,N}. Pentru fiecare poziție i din șirul P se cere să aflați cea mai mică poziție j, astfel încât P[j] < P[i] și j < i. În caz că o astfel de poziție nu există se consideră -1 ca soluție.

Date de intrare

Fișierul de intrare findmin.in conţine pe prima linie N, reprezentând lungimea șirului iar pe a doua linie N numere naturale, reprezentând elementele șirului P.

Date de ieșire

Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse."

Pe următorul rând se vor afișa N numere despărțite prin câte un spațiu, unde al i-lea număr reprezintă răspunsul pentru al i-lea element din șir.

În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse."

Restricții și precizări

• 1 ≤ N ≤ 1 000 000

• Șirul P este indexat de la 1.

Exemplu 1

Intrare

7

5 6 7 3 1 4 2

Ieșire

Datele de intrare corespund restricțiilor impuse.

-1 1 1 -1 -1 4 5

Explicație

Pentru primele 2 elemente răspunsurile sunt -1 respectiv 1. Pentru al 3-lea element răspunsul e poziția 1(se observă că și P[2] < P[3]). Pentru elementele de pe pozițiile 4 și 5 răspunsurile sunt: -1 și -1. Răspunsul pentru al 6-lea element: poziția 4 (se observa că și P[5] < P[6]). În final, răspunsul pentru ultimul elementul: poziția 5.

Exemplu 2

Intrare

1000001

1 2 3 3 3

Ieșire

Datele de intrare nu corespund restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line="1">

1. 1783 Find Min

def conditii(n, sir_p):

   restrictii = (
       1 <= min(sir_p),
       max(sir_p) <= 1_000_000,
       1 <= n <= 1_000_000,
       len(sir_p) == n
   )

   return all(restrictii)

def findmin(sir_p):

   sir = []

   # Pentru fiecare element din sir_p
   for i in range(len(sir_p)):
       # Căutăm primul element mai mic decât el
       minim = -1
       for j in range(i):
           # Dacă găsim unul...
           if sir_p[j] < sir_p[i]:
               # ...îl salvăm și ne oprim
               minim = j
               break
       # Dacă nu găsim niciunul, minimul rămâne -1
       # Altfel, adăugăm 1 la minim deoarece conform cerinței, indexarea șirului P începe de la 1
       sir.append(f"{minim+1 if minim != -1 else -1}")

   print(" ".join(sir))

if __name__ == "__main__":

   n = int(input())
   sir_p = [int(x) for x in input().split()]
   if not conditii(n, sir_p):
       print("Datele de intrare nu corespund restricțiilor impuse.")
   else:
       print("Datele de intrare corespund restricțiilor impuse.")
       findmin(sir_p)

</syntaxhighlight>