Ho provato a svolgere Bracketswap e ottengo 0/100 perchè tutti i testcase (esclusi quelli di esempio e il 4) sono errati.
La risoluzione ricalca altri esercizi simili sul bilanciamento di parentesi, quindi mi aspetterei almeno qualche testcase corretto.
Non credo sia un errore di lettura dell’input perchè i casi di esempio sono corretti e quello che ha una espressione bilanciata in ingresso la riconosce.
Sarebbe utile avere uno o più esempi di testcase. Se possibile. Grazie.
Se non posti il tuo codice difficile proporti esempi nei quali il tuo codice non va.
Grazie per la risposta.
Il codice è in Pascal, ho messo dei commenti alle righe di codice.
program bracketswap;
const MAXN=1000010;
var
N, R, i,j, h,w, pos, pos1, scambi, lungh: LongInt;
ST:ansistring;
S: array[0..MAXN] of char;
S1: array[-1..MAXN] of char;
idopen, idclose :array[0..MAXN] of longint;
p:char;
begin
assign(input, 'input.txt'); reset(input);
assign(output, 'output.txt'); rewrite(output);
ReadLn(N);
for i:=0 to N-1 do read(S[i]);
readln;
(*uso due array per memorizzare la posizione iniziale delle parentesi aperte e chiuse nella espressione*)
for i:=0 to N-1 do begin idopen[i]:=0; idclose[i]:=0; end;
(*leggo e verifico se è bilanciata e tolgo la parte bilanciata*)
pos1:=-1;
pos:=-1;
h:=0; j:=0; lungh:=N;
while (pos <lungh-1) do
begin
pos:=pos+1;
p:=S[pos];
if p='(' then
begin
pos1:=pos1+1;
S1[pos1]:=p;
idopen[h]:=pos;
h:=h+1;
end
else
if ( p=')') then begin if (pos1>=0) and (S1[pos1]='(') then begin pos1:=pos1-1;h:=h-1; end
else begin pos1:=pos1+1; S1[pos1]:=p; idclose[j]:=pos; j:=j+1;end;
end;
end;
(*quello che rimane sono parentesi non bilanciate metà delle quali chiuse e metà aperte*)
lungh:=pos1+1;
R:=lungh div 2;
(*calcolo il numero di scambi*)
if R mod 2 = 0 then scambi:= R div 2
else scambi:=(R+1) div 2;
writeln (scambi);
w:=0;
while w<scambi do begin writeln(idclose[0+w],' ',idopen[R-1-w]); w:=w+1; end;
end.
Non ci credo, finalmente la mia macchina del tempo funziona!
P.S.
C’è qualche motivo particolare per cui usi Pascal? Sono molto curioso.
3 Mi Piace
Ho fatto una domanda obsoleta ::
Non conosco in modo adeguato il C++ e quindi ho utilizzato il Pascal per me più confortevole.
Ogni tanto leggo con interesse i contenuti di questo forum e provo a svolgere qualche esercizio, ma l’esito di questa sottoposizione non riesco a spiegarlo.
Se la causa di errore è indipendente dal linguaggio di programmazione, ma dipende dalla logica di soluzione, potrebbe essere comunque utile, in caso contrario mi scuso per la domanda.
prova con
16
(()))())))(((()(
Grazie.
Ottengo come output
2
4 15
7 12
Con questi due scambi l’espressione diventa bilanciata.
Ma è corretto?
Non so molto di Pascal ma probabilmente c’è un problema di lettura dei dati: se metto uno spazio all’inizio della riga con le parentesi mi pare che il tuo programma non funzioni mentre il mio programma in C++ funziona. Togliendo lo spazio mi pare funzioni anche i tuo.
Prova a leggere l’intera sequenza di caratteri come stringa (e trimmandola)
prova di nuovo con
16
(()))())))(((()(
C’è uno spazio prima della prima parentesi.
Grazie!
Era effettivamente un errore di lettura dei dati.
Usando TrimLeft(stringa) ha letto correttamente l’input.