Lista de actividades X71187
Al final de este enunciado podeis encontrar un programa a medio hacer que hay que completar. Concretamente, hay dos funciones que estan pendientes de implementar. A continuación se explica con qué datos trabaja el programa y qué tienen que hacer las funciones.
El programa trabaja con un tipo de datos Activity, que representa una actividad, que incluye el nombre de la actividad (name), el instante de tiempo de inicio de la actividad (t1), y el instante de tiempo de finalización dela actividad (t2). Para simplificar, t1 y t2 son variables enteras, y el programa siempre trabaja con actividades correctamente definidas cumpliendo t1<t2:
struct Activity {
string name;
int t1, t2;
}
El programa también trabaja con un tipo de dato ListActivities, que representa una lista de actividades:
typedef vector<Activity> ListActivities;
Hay que implementar una función para verificar que dos actividades son compatibles en tiempo, es decir, que no se solapan. En el caso particular de que una de las actividades acaba exactamente cuando la otra empieza, se consideran compatibles.
bool compatibleActivities(Activity a, Activity b);
Además, hay que implementar otra función que recibe dos actividades y retorna cierto si la primera es menor que la segunda según el criterio que se describe a continuación. Una actividad es menor que otra si comienza estrictamente antes que la otra, o comienza a la vez que la otra i acaba estrictamente antes, o comienza y acaba a la vez que la otra pero su nombre es menor que el nombre de la otra en orden lexicográfico.
bool smallerActivity(Activity a, Activity b);
La función anterior se utiliza desde otro sitio del programa para ordenar todas las actividades.
Completad, entonces, el siguiente código inacabado para solucionar el ejercicio:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
// Here you can add more includes if you wish.
using namespace std;
struct Activity {
string name;
int t1, t2; // t1<t2 must be satisfied for a correct activity
};
typedef vector<Activity> ListActivities;
// Auxiliary functions (you can add more functions if you wish)
// Pre: The input contains a description of an activity with the format:
//
// name t1 t2
//
// where name is a non-empty string with lowercase letters and t1<t2
// Post: Returns the activity read from the input adapted to the format of struct Activity.
Activity readActivity()
{
Activity a;
cin >> a.name >> a.t1 >> a.t2;
return a;
}
// Pre: listactivities represents a list of correct activities
// Post: Prints all activities from first to last, one per line, and with the format:
//
// name t1 t2
void printActivities(const ListActivities &listactivities)
{
for (int i = 0; i < int(listactivities.size()); i++) {
const Activity &a = listactivities[i];
cout << a.name << " " << a.t1 << " " << a.t2 << endl;
}
}
// Pre: a, b represent correct activities.
// Post: Returns true iff the activities have a compatible timeline,
// i.e. they do not overlap in time.
// Note: if one of them finishes exactly when the other starts, then they are compatible.
bool compatibleActivities(Activity a, Activity b)
{
// Implement this function.
// ...
}
// Pre: a, b represent correct activities.
// Post: Returns true iff one of the following conditions holds:
// - a starts strictly before b.
// - a and b start at the same time but a finishes before b.
// - a and b coincide in start and end time, but a has lexicographically-smaller name than b.
bool smallerActivity(Activity a, Activity b)
{
// Implement this function.
// ...
}
int main()
{
ListActivities listactivities;
string command;
while (cin >> command) {
if (command == "NEW") {
listactivities.push_back(readActivity());
} else if (command == "SORT") {
sort(listactivities.begin(), listactivities.end(), smallerActivity);
} else if (command == "PRINT") {
cout << "Current list activities:" << endl;
printActivities(listactivities);
cout << endl;
} else if (command == "CHECKCOMPATIBLE") {
int i, j;
cin >> i >> j;
string namei = listactivities[i].name;
string namej = listactivities[j].name;
if (compatibleActivities(listactivities[i], listactivities[j]))
cout << "Activities " << namei << " and " << namej << " are compatible" << endl;
else
cout << "Activities " << namei << " and " << namej << " are incompatible" << endl;
cout << endl;
}
}
}
Entrada
La entrada consiste en una lista de comandos para crear nuevas actividades, ordenarlas, escribirlas todas, y comprobar si dos de ellas son compatibles. No hay que preocuparse mucho por el main ya que se da hecho y se encarga de llamar a las funciones para gestionar los comandos.
Salida
La salida muestra los resultados de los comandos. No hay que preocuparse sobre la salida porque el main que se da hecho ya se encarga de llamar a las correspondientes funciones para producir la salida.
Public test cases
Input
NEW biking 169 277 PRINT SORT NEW cinema 224 598 SORT PRINT NEW jogging 108 483 PRINT CHECKCOMPATIBLE 0 1 CHECKCOMPATIBLE 1 2 SORT PRINT NEW gym 24 184 NEW swimming 218 574 CHECKCOMPATIBLE 2 3 PRINT SORT NEW chatting 161 501 SORT NEW climbing 26 510 PRINT NEW reading 207 303 NEW siteseeing 440 561 PRINT NEW strolling 318 385 PRINT SORT PRINT CHECKCOMPATIBLE 1 7 NEW bowling 413 553 NEW boxing 42 253 PRINT NEW writing 77 154 PRINT SORT NEW flirting 84 320 PRINT NEW singing 281 548 CHECKCOMPATIBLE 6 7 PRINT CHECKCOMPATIBLE 4 9 CHECKCOMPATIBLE 1 5 NEW dancing 398 498 CHECKCOMPATIBLE 7 8 NEW shopping 28 58 PRINT CHECKCOMPATIBLE 3 5 CHECKCOMPATIBLE 0 13 SORT NEW cooking 182 530 CHECKCOMPATIBLE 6 14 PRINT NEW praying 54 433 SORT NEW fishing 435 599 PRINT CHECKCOMPATIBLE 9 14 SORT CHECKCOMPATIBLE 0 7 PRINT CHECKCOMPATIBLE 10 19 CHECKCOMPATIBLE 10 17 CHECKCOMPATIBLE 4 19 NEW hunting 380 465 PRINT CHECKCOMPATIBLE 2 4 CHECKCOMPATIBLE 0 17 CHECKCOMPATIBLE 11 13 SORT CHECKCOMPATIBLE 5 16 PRINT CHECKCOMPATIBLE 1 14 CHECKCOMPATIBLE 7 14 CHECKCOMPATIBLE 7 14 CHECKCOMPATIBLE 1 13 CHECKCOMPATIBLE 4 12 CHECKCOMPATIBLE 9 12 CHECKCOMPATIBLE 5 8 CHECKCOMPATIBLE 8 15 CHECKCOMPATIBLE 5 7 CHECKCOMPATIBLE 5 11 CHECKCOMPATIBLE 9 10 CHECKCOMPATIBLE 17 18 CHECKCOMPATIBLE 1 9 CHECKCOMPATIBLE 3 18 CHECKCOMPATIBLE 5 16 CHECKCOMPATIBLE 4 17 CHECKCOMPATIBLE 10 16 CHECKCOMPATIBLE 8 17 CHECKCOMPATIBLE 1 3 CHECKCOMPATIBLE 17 20 CHECKCOMPATIBLE 1 12 CHECKCOMPATIBLE 8 10 CHECKCOMPATIBLE 0 3 CHECKCOMPATIBLE 4 11 CHECKCOMPATIBLE 4 11 CHECKCOMPATIBLE 12 19 CHECKCOMPATIBLE 0 16 CHECKCOMPATIBLE 4 11 CHECKCOMPATIBLE 9 11
Output
Current list activities: biking 169 277 Current list activities: biking 169 277 cinema 224 598 Current list activities: biking 169 277 cinema 224 598 jogging 108 483 Activities biking and cinema are incompatible Activities cinema and jogging are incompatible Current list activities: jogging 108 483 biking 169 277 cinema 224 598 Activities cinema and gym are compatible Current list activities: jogging 108 483 biking 169 277 cinema 224 598 gym 24 184 swimming 218 574 Current list activities: gym 24 184 jogging 108 483 chatting 161 501 biking 169 277 swimming 218 574 cinema 224 598 climbing 26 510 Current list activities: gym 24 184 jogging 108 483 chatting 161 501 biking 169 277 swimming 218 574 cinema 224 598 climbing 26 510 reading 207 303 siteseeing 440 561 Current list activities: gym 24 184 jogging 108 483 chatting 161 501 biking 169 277 swimming 218 574 cinema 224 598 climbing 26 510 reading 207 303 siteseeing 440 561 strolling 318 385 Current list activities: gym 24 184 climbing 26 510 jogging 108 483 chatting 161 501 biking 169 277 reading 207 303 swimming 218 574 cinema 224 598 strolling 318 385 siteseeing 440 561 Activities climbing and cinema are incompatible Current list activities: gym 24 184 climbing 26 510 jogging 108 483 chatting 161 501 biking 169 277 reading 207 303 swimming 218 574 cinema 224 598 strolling 318 385 siteseeing 440 561 bowling 413 553 boxing 42 253 Current list activities: gym 24 184 climbing 26 510 jogging 108 483 chatting 161 501 biking 169 277 reading 207 303 swimming 218 574 cinema 224 598 strolling 318 385 siteseeing 440 561 bowling 413 553 boxing 42 253 writing 77 154 Current list activities: gym 24 184 climbing 26 510 boxing 42 253 writing 77 154 jogging 108 483 chatting 161 501 biking 169 277 reading 207 303 swimming 218 574 cinema 224 598 strolling 318 385 bowling 413 553 siteseeing 440 561 flirting 84 320 Activities biking and reading are incompatible Current list activities: gym 24 184 climbing 26 510 boxing 42 253 writing 77 154 jogging 108 483 chatting 161 501 biking 169 277 reading 207 303 swimming 218 574 cinema 224 598 strolling 318 385 bowling 413 553 siteseeing 440 561 flirting 84 320 singing 281 548 Activities jogging and cinema are incompatible Activities climbing and chatting are incompatible Activities reading and swimming are incompatible Current list activities: gym 24 184 climbing 26 510 boxing 42 253 writing 77 154 jogging 108 483 chatting 161 501 biking 169 277 reading 207 303 swimming 218 574 cinema 224 598 strolling 318 385 bowling 413 553 siteseeing 440 561 flirting 84 320 singing 281 548 dancing 398 498 shopping 28 58 Activities writing and chatting are compatible Activities gym and flirting are incompatible Activities jogging and dancing are incompatible Current list activities: gym 24 184 climbing 26 510 shopping 28 58 boxing 42 253 writing 77 154 flirting 84 320 jogging 108 483 chatting 161 501 biking 169 277 reading 207 303 swimming 218 574 cinema 224 598 singing 281 548 strolling 318 385 dancing 398 498 bowling 413 553 siteseeing 440 561 cooking 182 530 Current list activities: gym 24 184 climbing 26 510 shopping 28 58 boxing 42 253 praying 54 433 writing 77 154 flirting 84 320 jogging 108 483 chatting 161 501 biking 169 277 cooking 182 530 reading 207 303 swimming 218 574 cinema 224 598 singing 281 548 strolling 318 385 dancing 398 498 bowling 413 553 siteseeing 440 561 fishing 435 599 Activities biking and singing are compatible Activities gym and jogging are incompatible Current list activities: gym 24 184 climbing 26 510 shopping 28 58 boxing 42 253 praying 54 433 writing 77 154 flirting 84 320 jogging 108 483 chatting 161 501 biking 169 277 cooking 182 530 reading 207 303 swimming 218 574 cinema 224 598 singing 281 548 strolling 318 385 dancing 398 498 bowling 413 553 fishing 435 599 siteseeing 440 561 Activities cooking and siteseeing are incompatible Activities cooking and bowling are incompatible Activities praying and siteseeing are compatible Current list activities: gym 24 184 climbing 26 510 shopping 28 58 boxing 42 253 praying 54 433 writing 77 154 flirting 84 320 jogging 108 483 chatting 161 501 biking 169 277 cooking 182 530 reading 207 303 swimming 218 574 cinema 224 598 singing 281 548 strolling 318 385 dancing 398 498 bowling 413 553 fishing 435 599 siteseeing 440 561 hunting 380 465 Activities shopping and praying are incompatible Activities gym and bowling are compatible Activities reading and cinema are incompatible Activities writing and hunting are compatible Current list activities: gym 24 184 climbing 26 510 shopping 28 58 boxing 42 253 praying 54 433 writing 77 154 flirting 84 320 jogging 108 483 chatting 161 501 biking 169 277 cooking 182 530 reading 207 303 swimming 218 574 cinema 224 598 singing 281 548 strolling 318 385 hunting 380 465 dancing 398 498 bowling 413 553 fishing 435 599 siteseeing 440 561 Activities climbing and singing are incompatible Activities jogging and singing are incompatible Activities jogging and singing are incompatible Activities climbing and cinema are incompatible Activities praying and swimming are incompatible Activities biking and swimming are incompatible Activities writing and chatting are compatible Activities chatting and strolling are incompatible Activities writing and jogging are incompatible Activities writing and reading are compatible Activities biking and cooking are incompatible Activities dancing and bowling are incompatible Activities climbing and biking are incompatible Activities boxing and bowling are compatible Activities writing and hunting are compatible Activities praying and dancing are incompatible Activities cooking and hunting are incompatible Activities chatting and dancing are incompatible Activities climbing and boxing are incompatible Activities dancing and siteseeing are incompatible Activities climbing and swimming are incompatible Activities chatting and cooking are incompatible Activities gym and boxing are incompatible Activities praying and reading are incompatible Activities praying and reading are incompatible Activities swimming and fishing are incompatible Activities gym and hunting are compatible Activities praying and reading are incompatible Activities biking and reading are incompatible
Input
NEW biking 1 3 PRINT NEW cinema 2 3 CHECKCOMPATIBLE 0 1 PRINT NEW jogging 0 3 NEW gym 1 3 PRINT NEW swimming 2 3 PRINT CHECKCOMPATIBLE 2 3 CHECKCOMPATIBLE 3 4 CHECKCOMPATIBLE 1 4 CHECKCOMPATIBLE 1 3 NEW chatting 0 1 CHECKCOMPATIBLE 0 2 NEW climbing 1 2 NEW reading 0 1 NEW siteseeing 1 2 PRINT NEW strolling 0 1 CHECKCOMPATIBLE 2 7 CHECKCOMPATIBLE 3 6 CHECKCOMPATIBLE 0 7 PRINT CHECKCOMPATIBLE 2 7 CHECKCOMPATIBLE 0 8 SORT NEW bowling 0 1 CHECKCOMPATIBLE 4 10 PRINT NEW boxing 0 1 CHECKCOMPATIBLE 4 7 PRINT CHECKCOMPATIBLE 6 10 NEW writing 1 2 NEW flirting 1 3 SORT PRINT CHECKCOMPATIBLE 3 8 NEW singing 1 2 PRINT CHECKCOMPATIBLE 1 4 NEW dancing 1 3 NEW shopping 1 3 PRINT SORT CHECKCOMPATIBLE 0 3 CHECKCOMPATIBLE 5 11 NEW cooking 2 3 PRINT NEW praying 1 3 CHECKCOMPATIBLE 0 17 NEW fishing 0 3 PRINT SORT CHECKCOMPATIBLE 8 18 PRINT NEW hunting 0 3 SORT PRINT CHECKCOMPATIBLE 4 5 CHECKCOMPATIBLE 3 8 CHECKCOMPATIBLE 7 13 CHECKCOMPATIBLE 14 16 CHECKCOMPATIBLE 8 17 CHECKCOMPATIBLE 15 17 CHECKCOMPATIBLE 18 20 CHECKCOMPATIBLE 4 16 CHECKCOMPATIBLE 0 11 CHECKCOMPATIBLE 4 8 CHECKCOMPATIBLE 2 15 CHECKCOMPATIBLE 15 16 CHECKCOMPATIBLE 2 3 CHECKCOMPATIBLE 1 11 CHECKCOMPATIBLE 4 17 CHECKCOMPATIBLE 8 11 CHECKCOMPATIBLE 9 19 CHECKCOMPATIBLE 11 20 CHECKCOMPATIBLE 11 17 CHECKCOMPATIBLE 10 12 CHECKCOMPATIBLE 6 14 CHECKCOMPATIBLE 6 16 CHECKCOMPATIBLE 2 3 CHECKCOMPATIBLE 1 19 CHECKCOMPATIBLE 16 20 CHECKCOMPATIBLE 5 11 CHECKCOMPATIBLE 1 6 CHECKCOMPATIBLE 4 12 CHECKCOMPATIBLE 0 10 CHECKCOMPATIBLE 8 11 CHECKCOMPATIBLE 0 7 CHECKCOMPATIBLE 9 16 CHECKCOMPATIBLE 10 17 CHECKCOMPATIBLE 2 9 CHECKCOMPATIBLE 2 11 CHECKCOMPATIBLE 4 11 CHECKCOMPATIBLE 5 14 CHECKCOMPATIBLE 19 20 CHECKCOMPATIBLE 1 19
Output
Current list activities: biking 1 3 Activities biking and cinema are incompatible Current list activities: biking 1 3 cinema 2 3 Current list activities: biking 1 3 cinema 2 3 jogging 0 3 gym 1 3 Current list activities: biking 1 3 cinema 2 3 jogging 0 3 gym 1 3 swimming 2 3 Activities jogging and gym are incompatible Activities gym and swimming are incompatible Activities cinema and swimming are incompatible Activities cinema and gym are incompatible Activities biking and jogging are incompatible Current list activities: biking 1 3 cinema 2 3 jogging 0 3 gym 1 3 swimming 2 3 chatting 0 1 climbing 1 2 reading 0 1 siteseeing 1 2 Activities jogging and reading are incompatible Activities gym and climbing are incompatible Activities biking and reading are compatible Current list activities: biking 1 3 cinema 2 3 jogging 0 3 gym 1 3 swimming 2 3 chatting 0 1 climbing 1 2 reading 0 1 siteseeing 1 2 strolling 0 1 Activities jogging and reading are incompatible Activities biking and siteseeing are incompatible Activities climbing and bowling are compatible Current list activities: chatting 0 1 reading 0 1 strolling 0 1 jogging 0 3 climbing 1 2 siteseeing 1 2 biking 1 3 gym 1 3 cinema 2 3 swimming 2 3 bowling 0 1 Activities climbing and gym are incompatible Current list activities: chatting 0 1 reading 0 1 strolling 0 1 jogging 0 3 climbing 1 2 siteseeing 1 2 biking 1 3 gym 1 3 cinema 2 3 swimming 2 3 bowling 0 1 boxing 0 1 Activities biking and bowling are compatible Current list activities: bowling 0 1 boxing 0 1 chatting 0 1 reading 0 1 strolling 0 1 jogging 0 3 climbing 1 2 siteseeing 1 2 writing 1 2 biking 1 3 flirting 1 3 gym 1 3 cinema 2 3 swimming 2 3 Activities reading and writing are compatible Current list activities: bowling 0 1 boxing 0 1 chatting 0 1 reading 0 1 strolling 0 1 jogging 0 3 climbing 1 2 siteseeing 1 2 writing 1 2 biking 1 3 flirting 1 3 gym 1 3 cinema 2 3 swimming 2 3 singing 1 2 Activities boxing and strolling are incompatible Current list activities: bowling 0 1 boxing 0 1 chatting 0 1 reading 0 1 strolling 0 1 jogging 0 3 climbing 1 2 siteseeing 1 2 writing 1 2 biking 1 3 flirting 1 3 gym 1 3 cinema 2 3 swimming 2 3 singing 1 2 dancing 1 3 shopping 1 3 Activities bowling and reading are incompatible Activities jogging and dancing are incompatible Current list activities: bowling 0 1 boxing 0 1 chatting 0 1 reading 0 1 strolling 0 1 jogging 0 3 climbing 1 2 singing 1 2 siteseeing 1 2 writing 1 2 biking 1 3 dancing 1 3 flirting 1 3 gym 1 3 shopping 1 3 cinema 2 3 swimming 2 3 cooking 2 3 Activities bowling and cooking are compatible Current list activities: bowling 0 1 boxing 0 1 chatting 0 1 reading 0 1 strolling 0 1 jogging 0 3 climbing 1 2 singing 1 2 siteseeing 1 2 writing 1 2 biking 1 3 dancing 1 3 flirting 1 3 gym 1 3 shopping 1 3 cinema 2 3 swimming 2 3 cooking 2 3 praying 1 3 fishing 0 3 Activities singing and cooking are compatible Current list activities: bowling 0 1 boxing 0 1 chatting 0 1 reading 0 1 strolling 0 1 fishing 0 3 jogging 0 3 climbing 1 2 singing 1 2 siteseeing 1 2 writing 1 2 biking 1 3 dancing 1 3 flirting 1 3 gym 1 3 praying 1 3 shopping 1 3 cinema 2 3 cooking 2 3 swimming 2 3 Current list activities: bowling 0 1 boxing 0 1 chatting 0 1 reading 0 1 strolling 0 1 fishing 0 3 hunting 0 3 jogging 0 3 climbing 1 2 singing 1 2 siteseeing 1 2 writing 1 2 biking 1 3 dancing 1 3 flirting 1 3 gym 1 3 praying 1 3 shopping 1 3 cinema 2 3 cooking 2 3 swimming 2 3 Activities strolling and fishing are incompatible Activities reading and climbing are compatible Activities jogging and dancing are incompatible Activities flirting and praying are incompatible Activities climbing and shopping are incompatible Activities gym and shopping are incompatible Activities cinema and swimming are incompatible Activities strolling and praying are compatible Activities bowling and writing are compatible Activities strolling and climbing are compatible Activities chatting and gym are compatible Activities gym and praying are incompatible Activities chatting and reading are incompatible Activities boxing and writing are compatible Activities strolling and shopping are compatible Activities climbing and writing are incompatible Activities singing and cooking are compatible Activities writing and swimming are compatible Activities writing and shopping are incompatible Activities siteseeing and biking are incompatible Activities hunting and flirting are incompatible Activities hunting and praying are incompatible Activities chatting and reading are incompatible Activities boxing and cooking are compatible Activities praying and swimming are incompatible Activities fishing and writing are incompatible Activities boxing and hunting are incompatible Activities strolling and biking are compatible Activities bowling and siteseeing are compatible Activities climbing and writing are incompatible Activities bowling and jogging are incompatible Activities singing and praying are incompatible Activities siteseeing and shopping are incompatible Activities chatting and singing are compatible Activities chatting and writing are compatible Activities strolling and writing are compatible Activities fishing and flirting are incompatible Activities cooking and swimming are incompatible Activities boxing and cooking are compatible