Vizualizare sursă pentru „1783 - Find Min”

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

==Date de intrare==
Fișierul de intrare <code>findmin.in</code> conţine pe prima linie <code>N</code>, reprezentând lungimea șirului iar pe a doua linie <code>N</code> numere naturale, reprezentând elementele șirului <code>P</code>.
==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 <code>N</code> numere despărțite prin câte un spațiu, unde al <code>i</code>-lea număr reprezintă răspunsul pentru al <code>i</code>-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==

* <code>1 ≤ N ≤ 1 000 000</code>

* Șirul <code>P</code> este indexat de la <code>1</code>.

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

==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">
#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>