Finestrini Terry 2022

Aiuto
1 
#include <bits/stdc++.h>
using namespace std;

int main(){
	
freopen("finestrini_input.txt", "r", stdin);
freopen("outputfinestrini.txt", "w", stdout);

int T;
cin>>T;	

for(int t=1; t<=T; t++){
	int N;
	cin>>N;
	long long int Finestrini[N][2], min[N], salva[N];
	int somma=0;
	
	for(int i=0; i<N; i++){
		for(int j=0; j<2; j++){
			cin>>Finestrini[i][j];
		}
	}
	
	for(int i=0;i<N;i++)
    {
        min[i]=Finestrini[i][0];
    }
    
	
	for(int i=0; i<N; i++)
    { 
        for(int j=0; j<2; j++)
        {                                                    
            if(Finestrini[i][j]<min[i])
            {                          
				min[i]=Finestrini[i][j]; 
			}			
        } 	
    } 
    
    for(int i=0; i<N; i++){
    	if(min[i]==Finestrini[i][0]&&i>1&&min[i-1]==Finestrini[i][0]&&min[i-2]==Finestrini[i][0]){
    		min[i]=Finestrini[i][1];	
		}
		if(min[i]==Finestrini[i][1]&&i>1&&min[i-1]==Finestrini[i][1]&&min[i-2]==Finestrini[i][1]){
    		min[i]=Finestrini[i][0];		
		}
		somma+=min[i];
	}
	


	
	
	
	cout<<"Case #"<<t<<": "<<somma<< endl;      
  } 
  
	
	
	return 0;
}

Buonasera, potreste dirmi gentilmente come mai questo codice non funziona? alternative??

2

A mio parere, il controllo che non ci siano più di tre finestrini aperti sullo stesso lato potrebbe essere la causa del problema, anche se non so se ho capito bene quello che fa il codice. Potresti spiegare a grandi linee che ragionamento stai seguendo?

Piccolo suggerimento (per ottimizzare): questo problema si potrebbe risolvere con un approccio divide et impera in \mathcal{O}(N).

3

Anche secondo me è proprio quello il problema ma matematicamente è corretto e non va nemmeno in overflow o robe varie. Comunque te lo spiego, innanzitutto pongo nel primo ciclo for ogni cella dell’array min uguale al numero della prima colonna (per ogni riga pk i si incrementa) e poi dopo verifica solo se l’altro numero è minore di questo, se lo è, il numero minimo cambia in Finestrini[i][1].

Successivamente ho scritto un check per verificare se il numero minimo fosse uguale al numero Finestrini[i][0] quindi prima colonna e verifica pure i min[i] delle righe precedenti(chiaramente ho messo la condizione i>1 perché altrimenti il codice andrà a verificare celle che vengono prima dello zero).

Se questa condizione è vera allora pongo il minimo numero della riga in questione uguale al numero della seconda colonna. Stessa cosa per l’altra colonna

4

Il ragionamento potrebbe essere giusto, ma la logica è sbagliata.
Nel primo caso di test dell’esempio, min è [1, 1, 4, 1, 2]: la logica degli if fallisce, perché non riesce a distinguere il valore di min da dove “proviene”, per così dire. Non penso che per come l’hai implementato si possa risolvere (con una complessità accettabile – pur non essendoci limiti di tempo).

Immagino che questo esercizio sia mirato ad essere semplice da implementare ma richieda un po’ di ragionamento prima. Infatti, la soluzione è molto più semplice di quello che hai scritto.
Suggerimento per l’implementazione: per ogni passo, calcola tutte le possibili scelte (si riduce tutto a 4 casi!).

Se ti serve una mano, chiedi pure :slight_smile:

5

va bene grazie mille, potresti spiegarti meglio per l’implementazione che non ho ben capito

6

Certamente!
Il problema richiede che ci siano al massimo due finestrini aperti consecutivamente da un lato. Ogni volta dobbiamo puntare ad avere il minor costo. Bisogna quindi provare tutte le combinazioni che rispettino i limiti. Possiamo quindi rappresentare la lista di finestrini aperti con una stringa che indica, per ogni fila, da che lato c’è un finestrino aperto.
Per esempio, se abbiamo quattro file e apriamo i primi due finestrini a destra (R) e gli altri due a sinistra (L), la stringa sarà RRLL.

Con un po’ di calcoli puoi capire che gli unici “stati” che possono essere assunti dal programma sono questi:

  • gli ultimi due finestrini aperti sono LR (in questo caso si possono aprire da entrambi i lati)
  • gli ultimi due finestrini aperti sono RL (in questo caso si possono aprire da entrambi i lati)
  • gli ultimi due finestrini aperti sono RR (in questo caso va aperto L)
  • gli ultimi due finestrini aperti sono LL (in questo caso va aperto R)

Considerato questo, puoi quindi calcolare il valore minimo di ciascuno dei quattro casi e stampare in output il minore.

Suggerimento per l’implementazione: crea quattro variabili, inizializzate a 0, una per caso. Ogni volta che ti viene fornita una coppia di finestrini aggiorni le variabili.
Logica per modificare i valori:

  • al valore di LL devi per forza aggiungere il valore di R

  • al valore di RR devi per forza aggiungere il valore di L

  • al valore di LR devi capire se ti conviene fare LL + R o RL + R (in quanto sono solo gli ultimi due finestrini che ti interessano)

  • al valore di RL devi capire se ti conviene fare RR + L o LR + L (per lo stesso motivo motivo di LR)

7

grazie mille, gentilissimo.

8

Prego, se ti dovesse servire ancora una mano chiedi pure!

P.S. mi sono appena accorto che nella wiki danno una soluzione (in Python) molto simile alla mia, se ti interessa: