Revision as of 17:41, 8 December 2023

Introducere

Prietenul vostru Turing vă cere din nou ajutorul! Acesta își dorește un calculator cuantic pentru a calcula o sumă colosală, imposibilă pentru orice om. Momentan nu dispune de resursele materiale și financiare pentru a lucra la nivel cuantic, așa că vă cere ajutorul!

Cerința

Se dă un șir cu N elemente, numere naturale și un număr natural K. Aveți la dispoziție următoarea operație care se poate folosi de maximum K ori: se aleg doi indici i si j pentru care i % k = j % k (1 ≤ i < j ≤ N) și se interschimbă valorile acestor doi indici.

La final, după toate operațiile, trebuie să alegeți K elemente consecutive, iar suma acestor K elemente reprezinta scorul vostru. Turing trebuie sa obtina suma maximă și vă roagă să-l ajutați!

Date de intrare

Prima linie contine un numar T, reprezentand numarul de teste. Fiecare test contine două linii.

Prima linie conține numerele N și K (1 ≤ K ≤ N ≤ 1000), N fiind numărul de elemente al șirului și K numărul prezentat în cerință.

A doua linie conține N numere întregi A₁, A₂, … , A_n ( 0 ≤ A_i ≤ 1000 ), șirul de N numere naturale.

Date de ieșire

Programul va afișa pe câte un rând nou suma maximă pentru fiecare dintre cele T operații.

Restricții și precizări

1 ≤ T ≤ 1000
1 ≤ K ≤ N ≤ 1000
0 ≤ A[i] ≤ 1000

Exemplu:

Intrare

5
3 2
5 6 0
1 1
7
5 3
7 0 4 0 4
4 2
2 7 3 4
3 3
1000000000 1000000000 999999997

Ieșire

Explicație

În primul caz, putem obține suma maximă 11 dacă alegem A₁, A₂ fără să efectuăm nicio operație.

În al treilea caz, putem obține suma maximă 15 dacă interschimbăm A₁ cu A₄, iar suma finală este alcatuită din elementele A₃, A₄, A₅.

Încărcare soluție

Lipește codul aici

1

import sys

T, N, K = map(int, sys.stdin.readline().split())

A = list(map(int, sys.stdin.readline().split()))

B = [0] * K

for i in range(1, N+1):

    B[i % K] = max(B[i % K], A[i])

ans = sum(B)

print(ans)

@@ Line 1: / Line 1: @@
+= Introducere =
+Prietenul vostru Turing vă cere din nou ajutorul! Acesta își dorește un calculator cuantic pentru a calcula o sumă colosală, imposibilă pentru orice om. Momentan nu dispune de resursele materiale și financiare pentru a lucra la nivel cuantic, așa că vă cere ajutorul!
+= Cerința =
+Se dă un șir cu <code>N</code> elemente, numere naturale și un număr natural <code>K</code>. Aveți la dispoziție următoarea operație care se poate folosi de maximum <code>K</code> ori: se aleg doi indici <code>i</code> si <code>j</code> pentru care <code>i % k = j % k</code> (<code>1 ≤ i < j ≤ N</code>) și se interschimbă valorile acestor doi indici.
+La final, după toate operațiile, trebuie să alegeți <code>K</code> elemente consecutive, iar suma acestor <code>K</code> elemente reprezinta scorul vostru. Turing trebuie sa obtina suma maximă și vă roagă să-l ajutați!
+= Date de intrare =
+Prima linie contine un numar <code>T</code>, reprezentand numarul de teste. Fiecare test contine două linii.
+Prima linie conține numerele <code>N</code> și <code>K</code> (<code>1 ≤ K ≤ N ≤ 1000</code>), <code>N</code> fiind numărul de elemente al șirului și <code>K</code> numărul prezentat în cerință.
+A doua linie conține <code>N</code> numere întregi <code>A<sub>1</sub></code>, <code>A<sub>2</sub></code>, … , <code>A<sub>n</sub></code> ( <code>0 ≤ A<sub>i</sub></code> <code>≤ 1000</code> ), șirul de <code>N</code> numere naturale.
+= Date de ieșire =
+Programul va afișa pe câte un rând nou suma maximă pentru fiecare dintre cele <code>T</code> operații.
+= Restricții și precizări =
+* <code>1 ≤ T ≤ 1000</code>
+* <code>1 ≤ K ≤ N ≤ 1000</code>
+* <code>0 ≤ A[i] ≤ 1000</code>
+= Exemplu: =
+'''Intrare'''
+2
+6 0
+1
+3
+0 4 0 4
+2
+7 3 4
+3
+ 1000000000 1000000000 999999997
+'''Ieșire'''
+ 2999999997
+=== Explicație ===
+În primul caz, putem obține suma maximă <code>11</code> dacă alegem <code>A<sub>1</sub></code>, <code>A<sub>2</sub></code> fără să efectuăm nicio operație.
+În al treilea caz, putem obține suma maximă <code>15</code> dacă interschimbăm <code>A<sub>1</sub></code> cu <code>A<sub>4</sub></code>, iar suma finală este alcatuită din elementele <code>A<sub>3</sub></code>, <code>A<sub>4</sub></code>, <code>A<sub>5</sub></code>.
+== Încărcare soluție ==
+=== Lipește codul aici ===
+ import sys
+ T, N, K = map(int, sys.stdin.readline().split())
+ A = list(map(int, sys.stdin.readline().split()))
+ B = [0] * K
+ for i in range(1, N+1):
+     B[i % K] = max(B[i % K], A[i])
+ ans = sum(B)
+ print(ans)