Agafar elements del cim d'un altre Stack en ordre invers X69025

Statement

thehtml

En aquest exercici estendrem la classe Stack afegint un nou mètode anomenat take. Aquest mètode té, com a paràmetres, un altre Stack, i un natural k, i la seva crida té com a efecte que movem els k elements del top de l’altre Stack al top del paràmetre implícit, i en ordre invers.

Més específicament, suposem que un Stack t té contingut [a₁,a₂,…,a_n] (on els elements els representem en ordre des del fons fins el top, i en particular a_n és l’element del top), i que un altre Stack s té contingut [b₁,b₂,…,b_m]. Llavors, una crida t.take(s, k) té com a efecte que t passi a contenir [a₁,…,a_n,b_m,…,b_m−k+1] i s passi a contenir [b₁,…,b_m−k].

Per exemple, si t conté [3,1,5] i s conté [9,4,6,8,2], llavors la crida t.take(s, 3) té com a efecte que t passi a contenir [3,1,5,2,8,6], i que s passi a contenir [9,4].

En el cas particular que k sigui més gran que m, llavors es mouen tots els elements de s a t. És a dir, t passa a contenir [a₁,…,a_n,b_m,…,b₁], i s passa a contenir [].

Per exemple, si t conté [3,1,5] i s conté [9,4,6,8,2], llavors la crida t.take(s, 10) té com a efecte que t passi a contenir [3,1,5,2,8,6,4,9], i que s passi a contenir [].

D’entre els fitxers que s’adjunten en aquest exercici, trobareu stack.hh, a on hi ha una implementació de la classe genèrica Stack. Haureu de buscar dins stack.hh les següents línies:

  // Pre:  Sigui [a1,...,an] el contingut del paràmetre implícit (des del fons fins al cim).
  //       Sigui [b1,...,bm] el contingut de s.
  //       k>=0
  // Post: En el cas en que k>=m, aquest és el resultat:
  //          [a1,...,an,bm,...,b1] és el contingut del paràmetre implícit.
  //          [] és el contingut de s.
  //       En canvi, en el cas k<m, aquest és el resultat:
  //          [a1,...,an,bm,...,b{m-k+1}] és el contingut del paràmetre implícit.
  //          [b1,...,b{m-k}] és el contingut de s.
  // Descomenteu les següents dues linies i implementeu el mètode:
  // void take(Stack<T> &s, int k) {
  // ...
  // }

Descomenteu les linies que s’indiquen i implementeu el mètode.

D’entre els fitxers que s’adjunten a l’exercici també hi ha main.cc (programa principal), i el podeu compilar directament, doncs inclou stack.hh. Només cal que pugeu stack.hh al jutge.

Observació: En aquest exercici es prefereix una solució basada en manegar punters abans que una solució basada en cridar a mètodes primitius de la pròpia classe (push, pop, top). De fet, manegar punters serà més ràpid, i fer-ho d’una altra forma possiblement provocarà que no supereu els jocs de proves privats, quedant-vos així amb la meitat de la nota.

Entrada

L’entrada del programa comença amb una declaració d’unes quantes piles d’strings (s0, s1, ...), i després té una seqüència de comandes sobre les piles declarades. Com que ja us oferim el main.cc, no cal que us preocupeu d’implementar la lectura d’aquestes entrades. Només cal que implementeu la extensió de la classe pila abans esmentada.

Se suposa que la seqüència d’entrada serà correcta (sense pop ni top sobre pila buida), ni farà coses extranyes com cridar a take de la pròpia pila (així que no cal que tracteu aquest cas).

El programa principal que us oferim ja s’encarrega de llegir aquestes entrades i fer les crides als corresponents mètodes de la classe pila. Només cal que feu els canvis abans esmentats.

Sortida

Per a cada comanda d’escriptura sobre la sortida s’escriurà el resultat corresponent. El main.cc que us oferim ja fa això. Només cal que implementeu la extensió de la classe pila abans esmentada.

Observació

Avaluació sobre 10 punts: (Afegiu comentaris si el vostre codi no és prou clar)

Solució lenta: 5 punts.
solució ràpida: 10 punts.

Entenem com a solució ràpida una que és correcta i capaç de superar els jocs de proves públics i privats. Entenem com a solució lenta una que no és ràpida, però és correcta i capaç de superar els jocs de proves públics. Per exemple, una solució que superi tots els jocs de proves però que manegui incorrectament la memòria serà invalidada i tindrà nota 0.

Una solució basada en cridar a mètodes primitius de la pròpia classe possiblement serà lenta i, en cas que no ho sigui, pot tenir una certa penalització en la nota.

Public test cases

Input

Stack<int> s0 , s1 ;
s0 .push( "a" );
s0 .push( "b" );
s0 .push( "c" );
s0 .push( "d" );
s1 .push( "e" );
s1 .push( "f" );
s1 .push( "g" );
s1 .push( "h" );
cout<< s0 <<endl;
cout<< s1 <<endl;
cout<< s0 .size()<<endl;
cout<< s1 .size()<<endl;
cout<< s0 .top()<<endl;
cout<< s1 .top()<<endl;
s0 .take( s1 , 2 )<<endl;
cout<< s0 <<endl;
cout<< s1 <<endl;
cout<< s0 .size()<<endl;
cout<< s1 .size()<<endl;
cout<< s0 .top()<<endl;
cout<< s1 .top()<<endl;
s1 .take( s0 , 3 )<<endl;
cout<< s0 <<endl;
cout<< s1 <<endl;
cout<< s0 .size()<<endl;
cout<< s1 .size()<<endl;
cout<< s0 .top()<<endl;
cout<< s1 .top()<<endl;
s0 .take( s1 , 1 )<<endl;
cout<< s0 <<endl;
cout<< s1 <<endl;
cout<< s0 .size()<<endl;
cout<< s1 .size()<<endl;
cout<< s0 .top()<<endl;
cout<< s1 .top()<<endl;
s1 .take( s0 , 0 )<<endl;
cout<< s0 <<endl;
cout<< s1 <<endl;
cout<< s0 .size()<<endl;
cout<< s1 .size()<<endl;
cout<< s0 .top()<<endl;
cout<< s1 .top()<<endl;
s0 .take( s1 , 4 )<<endl;
cout<< s0 <<endl;
cout<< s1 <<endl;
cout<< s0 .size()<<endl;
cout<< s1 .size()<<endl;
cout<< s0 .top()<<endl;
s1 .take( s0 , 9 )<<endl;
cout<< s0 <<endl;
cout<< s1 <<endl;
cout<< s0 .size()<<endl;
cout<< s1 .size()<<endl;
cout<< s1 .top()<<endl;
s0 .take( s1 , 1000000000 )<<endl;
cout<< s0 <<endl;
cout<< s1 <<endl;
cout<< s0 .size()<<endl;
cout<< s1 .size()<<endl;
cout<< s0 .top()<<endl;

Output

a b c d
e f g h
4
4
d
h
a b c d h g
e f
6
2
g
f
a b c
e f g h d
3
5
c
d
a b c d
e f g h
4
4
d
h
a b c d
e f g h
4
4
d
h
a b c d h g f e

8
0
e

e f g h d c b a
0
8
a
a b c d h g f e

8
0
e

Input

Stack<int> s0 , s1 , s2 ;
cout<< s1 .size()<<endl;
s0 .push( "bd" );
s0 .take( s2 , 1 );
cout<< s1 <<endl;
s1 .take( s2 , 0 );
s1 .push( "adb" );
cout<< s1 .top()<<endl;
s1 .push( "ccc" );
s0 .push( "ad" );
s0 .take( s2 , 0 );
cout<< s2 .size()<<endl;
s2 .push( "dcb" );
s1 .take( s2 , 0 );
s2 .pop();
s1 .push( "bb" );
s0 .push( "bcb" );
s2 .take( s0 , 3 );
cout<< s0 <<endl;
s2 .push( "c" );
s2 .take( s0 , 0 );
s2 .push( "daa" );
s1 .push( "cc" );
cout<< s0 .size()<<endl;
s2 .push( "db" );
s2 .push( "a" );
s2 .push( "ac" );
s0 .push( "ada" );
s0 .push( "bd" );
s2 .take( s1 , 5 );
cout<< s1 <<endl;
cout<< s0 <<endl;
s2 .push( "dd" );
s1 .take( s0 , 2 );
s1 .push( "aba" );
cout<< s2 <<endl;
s2 .push( "b" );
s2 .push( "aa" );
s2 .push( "ac" );
cout<< s0 <<endl;
s2 .pop();
s2 .take( s1 , 3 );
s1 .push( "bad" );
s0 .push( "cd" );
s1 .push( "b" );
s2 .push( "d" );
s0 .take( s1 , 4 );
cout<< s1 .size()<<endl;
s2 .push( "aac" );
cout<< s0 .size()<<endl;
cout<< s0 <<endl;
s0 .push( "dcd" );
s2 .push( "ba" );
s2 .push( "ccb" );
s0 .push( "bdd" );
cout<< s2 .top()<<endl;
s2 .pop();
s2 .push( "c" );
cout<< s2 .size()<<endl;
cout<< s0 .size()<<endl;
s0 .push( "acc" );
cout<< s2 .top()<<endl;
cout<< s0 .size()<<endl;
s2 .take( s1 , 0 );
cout<< s0 <<endl;
s2 .push( "dca" );
s0 .push( "bcb" );
s1 .push( "d" );
s2 .push( "db" );
cout<< s0 <<endl;
cout<< s1 <<endl;
s2 .pop();
s0 .push( "aa" );
s0 .pop();
s0 .pop();
s1 .push( "d" );
cout<< s1 .size()<<endl;
s0 .take( s2 , 14 );
cout<< s0 <<endl;
s0 .push( "b" );
s1 .take( s0 , 11 );
s0 .pop();
cout<< s0 <<endl;
cout<< s1 <<endl;
cout<< s2 <<endl;

Output

0

adb
0

0

ada bd
bcb ad bd c daa db a ac cc bb ccc adb dd

0
3
cd b bad
ccb
22
5
c
6
cd b bad dcd bdd acc
cd b bad dcd bdd acc bcb
d
2
cd b bad dcd bdd acc dca c ba aac d bd ada aba aa b dd adb ccc bb
cd b bad dcd bdd acc dca c ba
d d b bb ccc adb dd b aa aba ada bd d
bcb ad bd c daa db a ac cc

Input

Stack<int> s0 , s1 , s2 ;
cout<< s1 .size()<<endl;
s0 .push( "bd" );
s0 .take( s2 , 1 );
cout<< s1 <<endl;
s1 .take( s2 , 0 );
s1 .push( "adb" );
cout<< s1 .top()<<endl;
s1 .push( "ccc" );
s0 .push( "ad" );
s0 .take( s2 , 0 );
cout<< s2 .size()<<endl;
s2 .push( "dcb" );
s1 .take( s2 , 0 );
s2 .pop();
s1 .push( "bb" );
s0 .push( "bcb" );
s2 .take( s0 , 3 );
cout<< s0 <<endl;
s2 .push( "c" );
s2 .take( s0 , 0 );
s2 .push( "daa" );
s1 .push( "cc" );
cout<< s0 .size()<<endl;
s2 .push( "db" );
s2 .push( "a" );
s2 .push( "ac" );
s0 .push( "ada" );
s0 .push( "bd" );
s2 .take( s1 , 5 );
cout<< s1 <<endl;
cout<< s0 <<endl;
s2 .push( "dd" );
s1 .take( s0 , 2 );
s1 .push( "aba" );
cout<< s2 <<endl;
s2 .push( "b" );
s2 .push( "aa" );
s2 .push( "ac" );
cout<< s0 <<endl;
s2 .pop();
s2 .take( s1 , 3 );
s1 .push( "bad" );
s0 .push( "cd" );
s1 .push( "b" );
s2 .push( "d" );
s0 .take( s1 , 4 );
cout<< s1 .size()<<endl;
s2 .push( "aac" );
cout<< s0 .size()<<endl;
cout<< s0 <<endl;
s0 .push( "dcd" );
s2 .push( "ba" );
s2 .push( "ccb" );
s0 .push( "bdd" );
cout<< s2 .top()<<endl;
s2 .pop();
s2 .push( "c" );
cout<< s2 .size()<<endl;
cout<< s0 .size()<<endl;
s0 .push( "acc" );
cout<< s2 .top()<<endl;
cout<< s0 .size()<<endl;
s2 .take( s1 , 0 );
cout<< s0 <<endl;
s2 .push( "dca" );
s0 .push( "bcb" );
s1 .push( "d" );
s2 .push( "db" );
cout<< s0 <<endl;
cout<< s1 <<endl;
s2 .pop();
s0 .push( "aa" );
s0 .pop();
s0 .pop();
s1 .push( "d" );
cout<< s1 .size()<<endl;
s0 .take( s2 , 14 );
cout<< s0 <<endl;
s0 .push( "b" );
s1 .take( s0 , 11 );
s0 .pop();
cout<< s0 <<endl;
cout<< s1 <<endl;
cout<< s2 <<endl;

Output

0

adb
0

0

ada bd
bcb ad bd c daa db a ac cc bb ccc adb dd

0
3
cd b bad
ccb
22
5
c
6
cd b bad dcd bdd acc
cd b bad dcd bdd acc bcb
d
2
cd b bad dcd bdd acc dca c ba aac d bd ada aba aa b dd adb ccc bb
cd b bad dcd bdd acc dca c ba
d d b bb ccc adb dd b aa aba ada bd d
bcb ad bd c daa db a ac cc

Information

Author: PRO2
Language: Catalan
Official solutions: Unknown. This problem is being checked.
User solutions: C++