Danciu: Pagină nouă: Aveți la dispoziție un număr natural nenul `n` și o permutare `a = (a[1], a[2], ..., a[n])` a mulțimii `{1, 2, ..., n}`. = Cerința = Pentru fiecare număr `a[i]` trebuie să determinați câte numere mai mici decât `a[i]` se află la stânga sa, adică în secvența `a[1], a[2], ..., a[i-1]`. = Date de intrare = Programul citește de la tastatură numărul `n`, iar apoi `n` numere...

2024-06-04T07:42:26Z

Pagină nouă: Aveți la dispoziție un număr natural nenul <code>n</code> și o permutare <code>a = (a[1], a[2], ..., a[n])</code> a mulțimii <code>{1, 2, ..., n}</code>. = Cerința = Pentru fiecare număr <code>a[i]</code> trebuie să determinați câte numere mai mici decât <code>a[i]</code> se află la stânga sa, adică în secvența <code>a[1], a[2], ..., a[i-1]</code>. = Date de intrare = Programul citește de la tastatură numărul <code>n</code>, iar apoi <code>n</code> numere...

New page

Aveți la dispoziție un număr natural nenul <code>n</code> și o permutare <code>a = (a[1], a[2], ..., a[n])</code> a mulțimii <code>{1, 2, ..., n}</code>.

= Cerința =
Pentru fiecare număr <code>a[i]</code> trebuie să determinați câte numere mai mici decât <code>a[i]</code> se află la stânga sa, adică în secvența <code>a[1], a[2], ..., a[i-1]</code>.

= Date de intrare =
Programul citește de la tastatură numărul <code>n</code>, iar apoi <code>n</code> numere naturale separate prin spații reprezentând permutarea.

= Date de ieșire =
Programul va afișa pe ecran pentru fiecare <code>i=1..n</code> câte numere mai mici decât <code>a[i]</code> se află la stânga sa.

= Restricții și precizări =

* <code>3 ≤ n ≤ 100.000</code>

= Exemplu: =
Intrare
7
3 1 6 5 2 7 4
Ieșire
0 0 2 2 1 5 3

=== Explicație ===
Sunt <code>0</code> numere mai mici decât <code>3</code> și aflate la stânga lui <code>3</code>.

Sunt <code>0</code> numere mai mici decât <code>1</code> și aflate la stânga lui <code>1</code>

Sunt <code>2</code> numere mai mici decât <code>6</code> și aflate la stânga lui <code>6</code> (acestea sunt primele două numere din șir, adică <code>3</code> și <code>1</code>)

== Rezolvare ==
<syntaxhighlight lang="python3">
def count_smaller(arr):
n = len(arr)
result = [0] * n
bit = [0] * (n + 1)

def update(x, val):
while x <= n:
bit[x] += val
x += x & -x

def query(x):
s = 0
while x > 0:
s += bit[x]
x -= x & -x
return s

for i in range(n - 1, -1, -1):
result[i] = query(arr[i])
update(arr[i], 1)

return result

def main():
n = int(input("Introduceti n: "))
arr = list(map(int, input("Introduceti permutarea: ").split()))

smaller_counts = count_smaller(arr)
for count in smaller_counts:
print(count, end=" ")

if __name__ == "__main__":
main()
</syntaxhighlight>

2725 - Aib - Revision history