1783 - Find Min

From Bitnami MediaWiki
Revision as of 08:02, 22 March 2023 by Ardelean Alexandru (talk | contribs) (Pagină nouă: ==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 p...)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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>