Llista d'activitats X71187
Al final d’aquest enunciat hi podeu trobar un programa a mig fer que haureu de completar. Concretament, hi han dues funcions que estan pendents d’implementar. A continuació us expliquem amb quines dades treballa el programa i què han de fer aquestes funcions.
El programa treballa amb un tipus de dada Activity, que representa una activitat, que inclou el nom de l’activitat (name), l’instant de temps d’inici de l’activitat (t1), i l’instant de temps d’acabament de l’activitat (t2). Per simplificar, t1 i t2 son variables enteres, i el programa sempre treballa amb activitats correctament definides cumplint t1<t2:
struct Activity {
string name;
int t1,t2;
};
El programa també treballa amb un tipus de dada ListActivities, que representa una llista d’activitats:
typedef vector<Activity> ListActivities;
Haureu d’implementar una funció per a verificar que dues activitats son compatibles en temps, és a dir, que no se sol.lapen en temps. En el cas particular en que una de les activitats acaba exactament quan l’altra comença, es consideren compatibles.
bool compatibleActivities(Activity a, Activity b)
A més a més, haureu d’implementar una funció que rep dues activitats i retorna cert si la primera és menor que la segona segons el criteri que descrivim a continuació. Una activitat és menor que una altra si comença estrictament abans que l’altra, o comença alhora que l’altra i acaba estrictament abans, o comença i acaba alhora que l’altra però el seu nom és menor que el nom de l’altra en ordre lexicogràfic.
bool smallerActivity(Activity a, Activity b)
La funció anterior es fa servir des d’un altre lloc del programa per a ordenar totes les activitats.
Completeu el següent codi a mig fer per tal de solucionar l’exercici:
#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
L’entrada consisteix en una llista de comandes per a crear noves activitats, ordenar-les, escriure-les totes, i comprovar si dues d’elles son compatibles. No us n’heu de preocupar massa perquè el main que us donem ja s’encarrega de cridar a les corresponents funcions per a manegar aquestes comandes.
Sortida
La sortida mostra els resultats de les comandes. No us n’heu de preocupar massa perquè el main que us donem ja s’encarrega de cridar a les corresponents funcions per tal de produïr aquesta sortida.
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