Puoi leggere e provare a risolvere il problema visitando la piattaforma Terry.
Ci viene chiesto in sostanza di trovare, tra tutte le possibili "rotazioni" della ruota della fortuna, qual è quella che produce il costo minore.
Essendo la ruota piuttosto piccola (il valore di è al massimo ) ci basta provare tutte le rotazioni una ad una, e calcolare il costo di ciascuna. Questa soluzione si potrebbe categorizzare quindi come "brute force".
Prendiamo uno dei casi d'esempio forniti dal problema:
7 2 5 3 4
2 4 1 3 7
Senza fare alcuna rotazione, il costo è dato dalla somma dei prodotti tra i numeri della prima riga e quelli della seconda, ovvero: .
Ruotando la ruota di una posizione verso sinistra, otteniamo:
7 2 5 3 4
4 1 3 7 2
Che ha un costo di: .
Ogni volta che proviamo una nuova rotazione confrontiamo la somma con il risultato migliore trovato fino a quel momento e, se troviamo un risultato ancora migliore, lo sovrascriviamo.
Dato che dobbiamo provare tutte le possibili rotazioni (che sono tante quanti sono i numeri nella ruota della fortuna, ovvero ) e dato che per ciascuna rotazione dobbiamo calcolarne il valore (che ci richiederà un altro ciclo for da operazioni per scandire la rotazione specifica che stiamo considerando) possiamo determinare che la complessità della soluzione è .
t = int(input())
for i in range(t):
input()
n = int(input())
v = list(map(int, input().split()))
g = list(map(int, input().split()))
# Salva un valore iniziale sufficientemente grande
risposta = 10**100
for offset in range(n):
somma = 0
for j in range(n):
# Qui sfruttiamo un trucco di Python: gli indici negativi ci
# permettono di leggere l'array dalla fine 😄
somma += v[j] * g[j - offset]
risposta = min(risposta, somma)
print(f"Case #{i + 1}: {risposta}")