summaryrefslogtreecommitdiff
path: root/1_anno/Programmazione_2/exercises/exam_20_07_20
diff options
context:
space:
mode:
Diffstat (limited to '1_anno/Programmazione_2/exercises/exam_20_07_20')
-rw-r--r--1_anno/Programmazione_2/exercises/exam_20_07_20/ex1.cpp39
-rw-r--r--1_anno/Programmazione_2/exercises/exam_20_07_20/ex2.cpp63
-rw-r--r--1_anno/Programmazione_2/exercises/exam_20_07_20/ex3.cpp284
-rw-r--r--1_anno/Programmazione_2/exercises/exam_20_07_20/ex4.cpp293
-rw-r--r--1_anno/Programmazione_2/exercises/exam_20_07_20/ex5.cpp285
5 files changed, 0 insertions, 964 deletions
diff --git a/1_anno/Programmazione_2/exercises/exam_20_07_20/ex1.cpp b/1_anno/Programmazione_2/exercises/exam_20_07_20/ex1.cpp
deleted file mode 100644
index 4f08a74..0000000
--- a/1_anno/Programmazione_2/exercises/exam_20_07_20/ex1.cpp
+++ /dev/null
@@ -1,39 +0,0 @@
-#include<iostream>
-#include<sstream>
-#include<fstream>
-#include<vector>
-
-using namespace std;
-int insertionsort(vector<int>& a, int n) {
- int c = 0;
- for(int i = 1; i < n; ++i) {
- int j = i-1;
- int key = a[i];
- while(j > -1 && a[j] > key) {
- swap(a[j+1], a[j]);
- --j;
- c++;
- }
- a[j+1] = key;
- }
- return c;
-}
-int main() {
- ifstream in("input.txt");
- ofstream out("output.txt");
-
- for(int ts = 0; ts < 100; ++ts) {
- int N;
- in >> N;
- int a, b;
- vector<int> v;
- for(int i = 0; i < N; ++i) {
- in >> a >> b;
- v.push_back(a+b);
- }
- out << insertionsort(v, v.size()) << endl;
- }
- in.close();
- out.close();
- return 0;
-}
diff --git a/1_anno/Programmazione_2/exercises/exam_20_07_20/ex2.cpp b/1_anno/Programmazione_2/exercises/exam_20_07_20/ex2.cpp
deleted file mode 100644
index aed25e4..0000000
--- a/1_anno/Programmazione_2/exercises/exam_20_07_20/ex2.cpp
+++ /dev/null
@@ -1,63 +0,0 @@
-#include<iostream>
-#include<sstream>
-#include<fstream>
-#include<queue>
-
-using namespace std;
-using pi = tuple<int, int, vector<int>>;
-
-class comp {
-public:
- bool operator()(const pi& lhs, const pi& rhs) const {
- auto xl = get<0>(lhs);
- auto yl = get<0>(rhs);
-
- auto il = get<1>(lhs);
- auto jl = get<1>(rhs);
- if(xl == yl)
- return il > jl;
- return xl > yl;
- }
-};
-
-int main() {
- ifstream in("input.txt");
- ofstream out("output.txt");
-
- for(int ts = 0; ts < 100; ++ts) {
- int R, C;
- in >> R >> C;
- vector<vector<int>> v;
- priority_queue<pi, vector<pi>, comp> pq;
- int k;
- for(int i = 0; i < R; ++i) {
- v.push_back(vector<int>{});
- for(int j = 0; j < C; ++j) {
- in >> k;
- v[i].push_back(k);
- }
- }
-
- int index = 0;
- for(auto const& i : v) {
- int s = 0;
- pi qq;
- for(auto const& j : i)
- s += j;
- get<0>(qq) = s;
- get<1>(qq) = index++;
- get<2>(qq) = i;
- pq.push(qq);
- }
- while(!pq.empty()) {
- auto q = pq.top();
- pq.pop();
- for(auto const& i : get<2>(q))
- out << i << ' ';
- }
- out << endl;
- }
- in.close();
- out.close();
- return 0;
-}
diff --git a/1_anno/Programmazione_2/exercises/exam_20_07_20/ex3.cpp b/1_anno/Programmazione_2/exercises/exam_20_07_20/ex3.cpp
deleted file mode 100644
index 71f9c65..0000000
--- a/1_anno/Programmazione_2/exercises/exam_20_07_20/ex3.cpp
+++ /dev/null
@@ -1,284 +0,0 @@
-#include<iostream>
-#include<sstream>
-#include<fstream>
-
-using namespace std;
-
-template<class T>
-struct node {
- T key;
- node<T>* prev;
- node<T>* right;
- node<T>* left;
-};
-
-template<class T>
-class bst {
-public:
- bst() : root{nullptr} , _val{0}{}
-
- ~bst() {
- // TODO
- }
-
- bst<T>* insert(initializer_list<T>&& list) {
- for(auto const& i : list)
- insert(i);
-
- return this;
- }
-
- bst<T>* insert(T k) {
- node<T>* nodus = new node<T>{k, nullptr, nullptr, nullptr};
- node<T>* iter = root;
- node<T>* prev = nullptr;
-
- while(iter) {
- prev = iter;
- iter = (k < iter->key) ? iter->left : iter->right;
- }
-
- nodus->prev = prev;
- if(!prev)
- root = nodus;
- else if(k < prev->key)
- prev->left = nodus;
- else
- prev->right = nodus;
-
- return this;
- }
-
- bst<T>* remove(initializer_list<T>&& list) {
- for(auto const& i : list)
- remove(i);
-
- return this;
- }
-
- bst<T>* remove(T k) {
- node<T>* nodus = search(k);
- if(!nodus) return this;
-
- if(!nodus->left) {
- _transplant(nodus, nodus->right);
- } else if(!nodus->right) {
- _transplant(nodus, nodus->left);
- } else {
- node<T>* iter = _min(nodus->right);
- if(iter->prev != nodus) {
- _transplant(iter, iter->right);
- iter->right = nodus->right;
- iter->right->prev = iter;
- }
- _transplant(nodus, iter);
- iter->left = nodus->left;
- iter->left->prev = iter;
- }
-
- delete nodus;
- return this;
- }
-
- node<T>* min() {
- return _min(root);
- }
-
- node<T>* min(node<T>* nodus) {
- return _min(nodus);
- }
-
- node<T>* max() {
- return _max(root);
- }
-
- node<T>* max(node<T>* nodus) {
- return _max(nodus);
- }
-
- node<T>* search(T k) {
- node<T>* iter = root;
- while(iter && iter->key != k)
- iter = (iter->key > k) ? iter->left : iter->right;
-
- return iter;
- }
-
- node<T>* successor(T k) {
- node<T>* nodus = search(k);
- if(!nodus) return nullptr;
-
- if(nodus->right)
- return min(nodus->right);
-
- node<T>* prev = nodus->prev;
- while(prev && nodus == prev->right) {
- nodus = prev;
- prev = prev->prev;
- }
-
- return prev;
-
- }
- node<T>* predecessor(T k) {
- node<T>* nodus = search(k);
- if(!nodus) return nullptr;
-
- if(nodus->left)
- return max(nodus->left);
-
- node<T>* prev = nodus->prev;
- while(prev && nodus == prev->left) {
- nodus = prev;
- prev = prev->prev;
- }
-
- return prev;
- }
-
- friend ostream& operator<<(ostream& os, bst<T>* tree) {
- tree->_inorder(os, tree->root);
- return os;
- }
- T sol(T k) {
- return _max(search(k))->key;
- }
-private:
- int _val;
- void _transplant(node<T>* u, node<T>* v) {
- if(!u->prev) {
- root = v;
- } else if(u == u->prev->left) {
- u->prev->left = v;
- } else {
- u->prev->right = v;
- }
-
- if(v)
- v->prev = u->prev;
- }
-
- node<T>* _min(node<T>* root) {
- node<T>* iter = root;
- while(iter && iter->left)
- iter = iter->left;
-
- return iter;
- }
-
- node<T>* _max(node<T>* root) {
- node<T>* iter = root;
- while(iter && iter->right)
- iter = iter->right;
-
- return iter;
- }
-
- void _inorder(ostream& os, node<T>* root) {
- if(root) {
- if(root->right && root->left) {
- _val++;
- }
- _inorder(os, root->left);
- os << root->key << ' ';
- _inorder(os, root->right);
- }
- }
-
- void _preorder(ostream& os, node<T>* root) {
- if(root) {
- os << root->key << ' ';
- _inorder(os, root->left);
- _inorder(os, root->right);
- }
- }
-
- void _postorder(ostream& os, node<T>* root) {
- if(root) {
- _inorder(os, root->left);
- _inorder(os, root->right);
- os << root->key << ' ';
- }
- }
- node<T>* root;
-};
-
-int main() {
- ifstream in("input.txt");
- ofstream out("output.txt");
-
- for(int ts = 0; ts < 100; ++ts) {
- string t, comm;
- in >> t;
- int n;
- switch(t.at(0)) {
- case 'd':
- {
- bst<double>* b = new bst<double>{};
- in >> n;
- double k;
- for(int i = 0; i < n; ++i) {
- in >> comm;
- stringstream tcomm(comm);
- int ex= 0;
- while(getline(tcomm, comm, ':')) {
- if(ex == 0) {
- if(comm == "ins")
- ex = 1;
- else
- ex = 2;
- } else {
- if(ex == 1)
- b->insert(stod(comm));
- else
- b->remove(stod(comm));
- ex = 0;
- }
- }
- }
- in >> k;
- cout << b << endl;
- out << b->sol(k) << endl;
-
- delete b;
- break;
- }
- case 'i':
- {
- bst<int>* b = new bst<int>{};
- in >> n;
- int k;
- for(int i = 0; i < n; ++i) {
- in >> comm;
- stringstream tcomm(comm);
- int ex= 0;
- while(getline(tcomm, comm, ':')) {
- if(ex == 0) {
- if(comm == "ins")
- ex = 1;
- else
- ex = 2;
- } else {
- if(ex == 1)
- b->insert(stoi(comm));
- else
- b->remove(stoi(comm));
- ex = 0;
- }
- }
- }
- in >> k;
- cout << b << endl;
- out << b->sol(k) << endl;
-
- delete b;
- break;
- }
- }
- }
-
- in.close();
- out.close();
- return 0;
-}
-
diff --git a/1_anno/Programmazione_2/exercises/exam_20_07_20/ex4.cpp b/1_anno/Programmazione_2/exercises/exam_20_07_20/ex4.cpp
deleted file mode 100644
index e234363..0000000
--- a/1_anno/Programmazione_2/exercises/exam_20_07_20/ex4.cpp
+++ /dev/null
@@ -1,293 +0,0 @@
-#include<iostream>
-#include<sstream>
-#include<fstream>
-
-using namespace std;
-
-template<class T>
-struct node {
- T key;
- node<T>* prev;
- node<T>* right;
- node<T>* left;
-};
-
-template<class T>
-class bst {
-public:
- bst() : root{nullptr} , _val{0}{}
-
- ~bst() {
- // TODO
- }
-
- bst<T>* insert(initializer_list<T>&& list) {
- for(auto const& i : list)
- insert(i);
-
- return this;
- }
-
- bst<T>* insert(T k) {
- node<T>* nodus = new node<T>{k, nullptr, nullptr, nullptr};
- node<T>* iter = root;
- node<T>* prev = nullptr;
-
- while(iter) {
- prev = iter;
- iter = (k < iter->key) ? iter->left : iter->right;
- }
-
- nodus->prev = prev;
- if(!prev)
- root = nodus;
- else if(k < prev->key)
- prev->left = nodus;
- else
- prev->right = nodus;
-
- return this;
- }
-
- bst<T>* remove(initializer_list<T>&& list) {
- for(auto const& i : list)
- remove(i);
-
- return this;
- }
-
- bst<T>* remove(T k) {
- node<T>* nodus = search(k);
- if(!nodus) return this;
-
- if(!nodus->left) {
- _transplant(nodus, nodus->right);
- } else if(!nodus->right) {
- _transplant(nodus, nodus->left);
- } else {
- node<T>* iter = _min(nodus->right);
- if(iter->prev != nodus) {
- _transplant(iter, iter->right);
- iter->right = nodus->right;
- iter->right->prev = iter;
- }
- _transplant(nodus, iter);
- iter->left = nodus->left;
- iter->left->prev = iter;
- }
-
- delete nodus;
- return this;
- }
-
- node<T>* min() {
- return _min(root);
- }
-
- node<T>* min(node<T>* nodus) {
- return _min(nodus);
- }
-
- node<T>* max() {
- return _max(root);
- }
-
- node<T>* max(node<T>* nodus) {
- return _max(nodus);
- }
-
- node<T>* search(T k) {
- node<T>* iter = root;
- while(iter && iter->key != k)
- iter = (iter->key > k) ? iter->left : iter->right;
-
- return iter;
- }
-
- node<T>* successor(T k) {
- node<T>* nodus = search(k);
- if(!nodus) return nullptr;
-
- if(nodus->right)
- return min(nodus->right);
-
- node<T>* prev = nodus->prev;
- while(prev && nodus == prev->right) {
- nodus = prev;
- prev = prev->prev;
- }
-
- return prev;
-
- }
- node<T>* predecessor(T k) {
- node<T>* nodus = search(k);
- if(!nodus) return nullptr;
-
- if(nodus->left)
- return max(nodus->left);
-
- node<T>* prev = nodus->prev;
- while(prev && nodus == prev->left) {
- nodus = prev;
- prev = prev->prev;
- }
-
- return prev;
- }
-
- friend ostream& operator<<(ostream& os, bst<T>* tree) {
- tree->_inorder(os, tree->root);
- return os;
- }
- T sol(T k) {
- auto x = search(k);
- auto m = _max(x)->key;
- auto mnn = _min(x);
- T mn;
- if(mnn->right)
- mn = _min(mnn->right)->key;
- else
- mn = mnn->key;
- cout << m << ' ' << mn << endl;
- return m - mn;
- }
-private:
- int _val;
- void _transplant(node<T>* u, node<T>* v) {
- if(!u->prev) {
- root = v;
- } else if(u == u->prev->left) {
- u->prev->left = v;
- } else {
- u->prev->right = v;
- }
-
- if(v)
- v->prev = u->prev;
- }
-
- node<T>* _min(node<T>* root) {
- node<T>* iter = root;
- while(iter && iter->left)
- iter = iter->left;
-
- return iter;
- }
-
- node<T>* _max(node<T>* root) {
- node<T>* iter = root;
- while(iter && iter->right)
- iter = iter->right;
-
- return iter;
- }
-
- void _inorder(ostream& os, node<T>* root) {
- if(root) {
- if(root->right && root->left) {
- _val++;
- }
- _inorder(os, root->left);
- os << root->key << ' ';
- _inorder(os, root->right);
- }
- }
-
- void _preorder(ostream& os, node<T>* root) {
- if(root) {
- os << root->key << ' ';
- _inorder(os, root->left);
- _inorder(os, root->right);
- }
- }
-
- void _postorder(ostream& os, node<T>* root) {
- if(root) {
- _inorder(os, root->left);
- _inorder(os, root->right);
- os << root->key << ' ';
- }
- }
- node<T>* root;
-};
-
-int main() {
- ifstream in("input.txt");
- ofstream out("output.txt");
-
- for(int ts = 0; ts < 100; ++ts) {
- string t, comm;
- in >> t;
- int n;
- switch(t.at(0)) {
- case 'd':
- {
- bst<double>* b = new bst<double>{};
- in >> n;
- double k;
- for(int i = 0; i < n; ++i) {
- in >> comm;
- stringstream tcomm(comm);
- int ex= 0;
- while(getline(tcomm, comm, ':')) {
- if(ex == 0) {
- if(comm == "ins")
- ex = 1;
- else
- ex = 2;
- } else {
- if(ex == 1)
- b->insert(stod(comm));
- else
- b->remove(stod(comm));
- ex = 0;
- }
- }
- }
- in >> k;
- cout << b << endl;
- out << b->sol(k) << endl;
-
- delete b;
- break;
- }
- case 'i':
- {
- bst<int>* b = new bst<int>{};
- in >> n;
- int k;
- for(int i = 0; i < n; ++i) {
- in >> comm;
- stringstream tcomm(comm);
- int ex= 0;
- while(getline(tcomm, comm, ':')) {
- if(ex == 0) {
- if(comm == "ins")
- ex = 1;
- else
- ex = 2;
- } else {
- if(ex == 1)
- b->insert(stoi(comm));
- else
- b->remove(stoi(comm));
- ex = 0;
- }
- }
- }
- in >> k;
- cout << b << endl;
- out << b->sol(k) << endl;
-
- delete b;
- break;
- }
- }
- }
-
- in.close();
- out.close();
- return 0;
-}
-
diff --git a/1_anno/Programmazione_2/exercises/exam_20_07_20/ex5.cpp b/1_anno/Programmazione_2/exercises/exam_20_07_20/ex5.cpp
deleted file mode 100644
index dd8fc98..0000000
--- a/1_anno/Programmazione_2/exercises/exam_20_07_20/ex5.cpp
+++ /dev/null
@@ -1,285 +0,0 @@
-#include<iostream>
-#include<vector>
-#include<algorithm>
-#include<queue>
-#include<stack>
-#include<fstream>
-#define INF 99999999
-#define W -1
-#define G 0
-#define B 1
-
-using namespace std;
-
-template<class H>
-class graph {
-public:
- graph(int len) : _len{len}, _nodes{0}, _edges{0} {
- _k = new H*[len];
- _adj = new vector<int>[len];
- _colors = new int[len];
- _d = new int[len];
- _f = new int[len];
- _p = new int[len];
-
- for(int i = 0; i < len; ++i) {
- _k[i] = nullptr;
- }
- }
- ~graph() {
- delete[] _k;
- delete[] _adj;
- }
-
- graph<H>* add_node(H x) {
- if(_index(x) > -1) return this;
- if(_nodes == _len) return this;
- _k[_nodes++] = new H(x);
-
- return this;
- }
- graph<H>* add_edge(H u, H v) {
- int i = _index(u);
- int j = _index(v);
- if(i < 0 || j < 0) return this;
-
- if(find(_adj[i].begin(), _adj[i].end(), j) == _adj[i].end()) {
- _adj[i].push_back(j);
- }
- return this;
- }
- void print() {
- for(int i = 0; i < _nodes; ++i) {
- cout << "(" << *_k[i] << ", " << i << "): ";
- for(auto const& j : _adj[i]) {
- cout << "(" << *_k[j] << ", " << j << ") ";
- }
- cout << endl;
- }
- }
- void dfsvisit(int u, bool visited[]) {
- visited[u] = true;
- cout << "(" << *_k[u] << ", " << u << ") ";
- for(auto const& i : _adj[u]) {
- if(!visited[i])
- dfsvisit(i, visited);
- }
- }
- int dfsvisit(int u) {
- int cycle = 0;
- _colors[u] = G;
- _d[u] = _time++;
-
- for(auto const& j : _adj[u]) {
- if(_colors[j] == W)
- cycle |= dfsvisit(j);
- }
-
- _colors[u] = B;
- _stack.push(u);
- _f[u] = _time++;
- return cycle;
- }
- int dfs() {
- int cycle = 0;
- for(int i = 0; i < _nodes; ++i) {
- _colors[i] = W;
- }
- _time = 0;
- for(int i = 0; i < _nodes; ++i) {
- if(_colors[i] == W)
- cycle |= dfsvisit(i);
- else if(_colors[i] == G)
- cycle = 1;
- }
- for(int i = 0; i < _nodes; ++i) {
- cout << "(" << *_k[i] << ", " << i << "): [" << _d[i] << "," << _f[i] << "]" << endl;
- }
- return cycle;
- }
-
- void top_sort() {
- int cycle = dfs();
- if(cycle) {
- cout << "cyclic graph!" << endl;
- return;
- }
- int* s = new int[_nodes];
- for(int i = 0; i < _nodes; ++i) s[i] = i;
- _sort(s, _nodes, _f);
- for(int i = 0; i < _nodes; ++i) {
- cout << "(" << s[i] << ", " << _f[s[i]] << ") ";
- }
-
- }
-
- void bfs(H v) {
- int s = _index(v);
- if(s < 0) return;
-
- for(int i = 0; i < _nodes; ++i) {
- _colors[i] = W;
- _d[i] = INF;
- _p[i] = -1;
- }
- _colors[s] = G;
- _d[s] = 0;
- queue<int> q;
- q.push(s);
- while(!q.empty()) {
- int u = q.front();
- q.pop();
- for(auto const& j : _adj[u]) {
- if(_colors[j] == W) {
- _colors[j] = G;
- _d[j] = _d[u]+1;
- _p[j] = u;
- q.push(j);
- }
- }
- _colors[u] = B;
- }
- for(int i = 0; i < _nodes; ++i) {
- cout << "(" << *_k[i] << ", " << i << "): [" << _d[i] << "]" << endl;
- }
- }
- int ssc() {
- dfs();
- cout << endl << endl;
- bool* visited = new bool[_nodes];
- for(int i = 0; i < _nodes; ++i)
- visited[i] = false;
- int count = 0;
- while(!_stack.empty()) {
- int v = _stack.top();
- _stack.pop();
- if(!visited[v]) {
- dfsvisit(v, visited);
- count++;
- cout << endl;
- }
- }
- delete[] visited;
- return count;
- }
-private:
- graph<H>* _transpose() {
- graph<H>* g = new graph<H>{_len};
- for(int i = 0; i < _nodes; ++i) {
- g->add_node(*_k[i]);
- }
-
- for(int i = 0; i < _nodes; ++i) {
- for(auto const& j : _adj[i]) {
- g->add_edge(j, i);
- }
- }
-
- return g;
- }
- void _sort(int* d, int n, int* s) {
- for(int i = -1; i < n; ++i) {
- int j = i-1;
- while(j > -1 && s[d[j+1]]>s[d[j]]) {
- swap(d[s[j+1]], d[s[j]]);
- --j;
- }
- }
- }
- int _index(H x) {
- for(int i = 0; i < _nodes; ++i)
- if(*_k[i] == x) return i;
-
- return -1;
- }
- stack<int> _stack;
- H** _k;
- vector<int>* _adj;
- int _len, _nodes, _edges;
- int* _colors;
- int _time;
- int* _d;
- int* _f;
- int* _p;
-};
-
-int main() {
- ifstream in("input.txt");
- ofstream out("output.txt");
-
- for(int ts = 0; ts < 100; ++ts) {
- int n, e;
- in >> n>>e;
- string t;
- in >> t;
- char _t;
- switch(t.at(0)){
- case 'd':{
- graph<double>* g = new graph<double>{n};
- double x, y;
- for(int i = 0; i < n; ++i) {
- in >> x;
- g->add_node(x);
- }
- for(int i = 0; i < e; ++i) {
- in >>_t;
- in >> x >> y;
- in >> _t;
- g->add_edge(x, y);
- g->add_edge(y, x);
- }
- g->print();
- cout << endl << endl;
- out << g->ssc()<<endl;
- delete g;
- break;
- }
- case 'i':{
-
- graph<int>* g = new graph<int>{n};
- int x, y;
- for(int i = 0; i < n; ++i) {
- in >> x;
- g->add_node(x);
- }
- for(int i = 0; i < e; ++i) {
- in >>_t;
- in >> x >> y;
- in >> _t;
- g->add_edge(x, y);
- g->add_edge(y, x);
- }
- g->print();
- cout << endl << endl;
- out << g->ssc()<<endl;
- delete g;
- break;
- }
- case 'c': {
-
- graph<char>* g = new graph<char>{n};
- char x, y;
- for(int i = 0; i < n; ++i) {
- in >> x;
- g->add_node(x);
- }
- for(int i = 0; i < e; ++i) {
- in >>_t;
- in >> x >> y;
- in >> _t;
- g->add_edge(x, y);
- g->add_edge(y, x);
- }
- g->print();
- cout << endl << endl;
- out << g->ssc()<<endl;
- delete g;
- break;
- }
- }
- }
- in.close();
- out.close();
- return 0;
-}
-
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-11-10 10:18:00 +0000