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

Fișierul de ieșire findmin.out va conține pe prima linie 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.

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

-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

Date de intrare gresite!

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 gasire_min(numere):

   sir = []

   for i in range(len(numere)):
       minim = 1_000_001
       for j in range(i):
           if numere[j] < numere[i]:
               if numere[j] < minim:
                   minim = j
       sir.append(f"{minim+1 if minim != 1_000_001 else -1}")

   return " ".join(sir)

def main():

   n = int(input())
   sir_p = [int(x) for x in input().split()]
   if not conditii(n, sir_p):
       return print("Date de intrare gresite!")

   print(gasire_min(sir_p))

if __name__ == "__main__":

   main()

</syntaxhighlight>