RebecaBud: Pagină nouă: == Enunt == După o lungă activitate în domeniul instalaţiilor sanitare, Dorel s-a hotărât să investească averea acumulată în acţiuni ale mai multor companii. Astfel, el dispune de o listă cu N companii la care vrea să cumpere acţiuni, în M zile consecutive. În prima zi, suma de bani investită în compania i este s[1][i] = a[i], pentru orice i=1..N, unde valorile a[i] sunt date. Numerele a[1], a[2], …, a[N] reprezintă o permutare a numerelor 1,2,...,N}....

2024-06-03T17:27:52Z

Pagină nouă: == Enunt == După o lungă activitate în domeniul instalaţiilor sanitare, Dorel s-a hotărât să investească averea acumulată în acţiuni ale mai multor companii. Astfel, el dispune de o listă cu N companii la care vrea să cumpere acţiuni, în M zile consecutive. În prima zi, suma de bani investită în compania i este s[1][i] = a[i], pentru orice i=1..N, unde valorile a[i] sunt date. Numerele a[1], a[2], …, a[N] reprezintă o permutare a numerelor 1,2,...,N}....

New page

== Enunt ==
După o lungă activitate în domeniul instalaţiilor sanitare, Dorel s-a hotărât să investească averea acumulată în acţiuni ale mai multor companii. Astfel, el dispune de o listă cu N companii la care vrea să cumpere acţiuni, în M zile consecutive.

În prima zi, suma de bani investită în compania i este s[1][i] = a[i], pentru orice i=1..N, unde valorile a[i] sunt date.

Numerele a[1], a[2], …, a[N] reprezintă o permutare a numerelor 1,2,...,N}.

În ziua a j-a el va investi în compania i o sumă de bani egală cu s[j][i] = s[j-1][a[i]], pentru orice zi j =2..M şi orice companie i = 1..N.
== Cerinţa ==
După finalizarea planului de investiţii, Dorel vrea să realizeze Q statistici referitoare la sumele investite. Fiind date Q seturi de valori zi, zf, cl, cr, el doreşte să afle ce sumă a investit în perioada cuprinsă între zilele zi și zf (inclusiv acestea), la companiile cu numere de ordine cuprinse între cl și cr (inclusiv acestea).
== Date de intrare ==
Pe prima linie a fişierului de intrare investitie.in se află numerele N şi M, separate prin spaţiu. Pe a doua linie se află valorile a[1], a[2], ..., a[N], separate prin spaţiu. Pe a treia linie se află valoarea lui Q. Pe următoarele Q linii se află câte patru valori, zi, zf, cl, cr, separate prin spaţiu.
== Date de ieșire ==
În fişierul de ieşire investitie.out se vor afişa, pe linii diferite, sumele investite corespunzătoare fiecăreia din cele Q statistici din fişierul de intrare.
== Restricţii şi precizări ==
* 1 ≤ N, Q ≤ 100.000
* 1 ≤ M ≤ 1.000.000.000
* 1 ≤ zi ≤ zf ≤ M
* 1 ≤ cl ≤ cr ≤ N
* 0 ≤ cr -cl ≤ 100
* Pentru 10 puncte, M = 1
* Pentru 20 de puncte, 1 ≤ N, M ≤ 100, 1 ≤ Q ≤ 1000
* Pentru 12 puncte, 101 ≤ N , M ≤ 3000
* Pentru 24 de puncte, 1 ≤ N ≤ 50
* Pentru 34 de puncte fără alte restricţii
== Exemplul 1 ==
; investitie.in

8 3
3 1 7 2 6 4 5 8
5
1 1 3 7
1 2 1 4
1 3 2 8
2 3 3 6
3 3 3 3
; investitie.out

24
29
93
24
6
== Explicație ==
Sumele investite în cele trei zile, în acţiuni ale celor opt companii, vor fi:

3 & 1 & 7 & 2 & 6 & 4 & 5 & 8
7 & 3 & 5 & 1 & 4 & 2 & 6 & 8
5 & 7 & 6 & 3 & 2 & 1 & 4 & 8

Prima statistică cere suma investită în prima zi în companiile cu numere de ordine de la 3 la 7. Suma este 7+2+6+4+5=24.
A doua statistică cere suma investită în primele două zile în companiile cu numerele de ordine de la 12 la 4. Suma este (3+1+7+2)+(7+3+5+1)=29.
Similar se calculează celelalte statistici.
<br>

== Rezolvare ==
<syntaxhighlight lang="python" line>
def investition(N, M, a, Q, queries):
investments = [[0] * (N + 1) for _ in range(M + 1)]
for i in range(1, N + 1):
investments[1][i] = a[i - 1]
for j in range(2, M + 1):
for i in range(1, N + 1):
investments[j][i] = investments[j - 1][a[i - 1]]

cumulative_investments = [[0] * (N + 1) for _ in range(M + 1)]
for j in range(1, M + 1):
for i in range(1, N + 1):
cumulative_investments[j][i] = cumulative_investments[j - 1][i] + investments[j][i]

results = []
for query in queries:
zi, zf, cl, cr = query
total_investment = 0
for i in range(cl, cr + 1):
total_investment += cumulative_investments[zf][i] - cumulative_investments[zi - 1][i]
results.append(total_investment)
return results

def main():
N, M = map(int, input().split())
a = list(map(int, input().split()))
Q = int(input())
queries = [list(map(int, input().split())) for _ in range(Q)]

results = investition(N, M, a, Q, queries)
for result in results:
print(result)

if __name__ == "__main__":
main()

</syntaxhighlight>

4115 - Investitie - Revision history