F017A. Manipulant dates P76675


Statement
 

pdf   zip

thehtml

Considereu una seqüència de dates ordenada de forma estrictament creixent. (Per exemple, la seqüència podria ser 5/5/2003, 6/5/2003, 1/8/2003.) Volem poder fer les operacions següents:

  • Afegir una data més gran que totes les dates actualment presents a la seqüència. (Per exemple, afegint 12/12/2003 a la seqüència 5/5/2003, 6/5/2003, 1/8/2003, obtindríem la seqüència 5/5/2003, 6/5/2003, 1/8/2003, 12/12/2003.)
  • Esborrar la data més gran de la seqüència. (Per exemple, esborrant el màxim de la seqüència 5/5/2003, 6/5/2003, 1/8/2003, obtindríem la seqüència 5/5/2003, 6/5/2003.)
  • Calcular la distància entre dues dates a i b donades, mesurada com el nombre de passes a la dreta que caldria fer des de a per arribar a b. Tant a com b estan a la seqüència, i compleixen ab. (Per exemple, consultant la distància entre 5/5/2003 i 1/8/2003 a la seqüència 5/5/2003, 6/5/2003, 1/8/2003, obtindríem 2 de resultat.)

Feu un programa que, a partir d’una seqüència de dates inicialment buida, vagi realitzant les operacions demanades. Compte: les tres operacions (afegir, esborrar, i consultar) han de ser eficients. En particular, el codi de les dues primeres hauria de ser minúscul. Per a la tercera, useu dues vegades un algorisme fonamental. La seqüència pot crèixer fins arribar a tenir un màxim de 10000 elements.

Pista

Us suggerim que utilitzeu la definició

struct Data { int dia, mes, any; };

així com una funció

Data data_llegida();

que llegeixi i retorni una data de l’entrada.

Entrada

L’entrada consisteix en una sèrie d’ordres: Si es vol afegir, ve una A seguida d’una data estrictament més gran que totes les dates presents a la seqüència. Si es vol esborrar, ve una E. Teniu la garantia que mai no s’intentarà esborrar d’una seqüència buida. Si es vol consultar, ve una C seguida de dues dates a i b presents a la seqüència, i tals que ab. Tots els dies es troben entre 1 i 31, els mesos entre 1 i 12, i els anys entre 1 i 5000.

Sortida

Per a cada consulta de l’entrada, escriviu una línia amb la distància entre les dues dates.

Public test cases
  • Input

    A 5/5/2003
    A 6/5/2003
    A 1/8/2003
    C 5/5/2003 1/8/2003
    A 12/12/2003
    A 31/12/2003
    A 1/1/2004
    A 10/10/2004
    A 15/11/2009
    A 24/12/2009
    A 12/1/2010
    C 12/12/2003 15/11/2009
    C 24/12/2009 12/1/2010
    C 5/5/2003 12/1/2010
    

    Output

    2
    4
    1
    9
    
  • Input

    
            
                                

    Output

    
            
                                
  • Input

    A 6/6/6
    C 6/6/6 6/6/6
    A 7/7/7
    C 6/6/6 7/7/7
    A 8/8/8
    C 6/6/6 8/8/8
    E
    E
    A 8/8/8
    C 6/6/6 8/8/8
    E
    E
    A 5/5/5
    C 5/5/5 5/5/5
    

    Output

    0
    1
    2
    1
    0
    
  • Information
    Author
    Professorat de P1
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++