summaryrefslogtreecommitdiff
path: root/1_anno/Programmazione_2
diff options
context:
space:
mode:
authorSanto Cariotti <dcariotti24@gmail.com>2020-10-18 18:56:43 +0200
committerSanto Cariotti <dcariotti24@gmail.com>2020-10-20 09:08:52 +0200
commitf279107065146a4940f5e73602a1c3c09e58b31d (patch)
treefd892749637a8b6c5c31ccb80bba04ade76ab87a /1_anno/Programmazione_2
parent4e063e32250312c38d5646840719b62429362b21 (diff)
chore: name of first year folder
Diffstat (limited to '1_anno/Programmazione_2')
-rw-r--r--1_anno/Programmazione_2/algorithms/binarysearch.cc33
-rw-r--r--1_anno/Programmazione_2/algorithms/cbrt.cc37
-rw-r--r--1_anno/Programmazione_2/algorithms/insertionsort.cc42
-rw-r--r--1_anno/Programmazione_2/algorithms/log.cc25
-rw-r--r--1_anno/Programmazione_2/algorithms/mergesort.cc52
-rw-r--r--1_anno/Programmazione_2/algorithms/pow.cc25
-rw-r--r--1_anno/Programmazione_2/algorithms/quicksort.cc38
-rw-r--r--1_anno/Programmazione_2/algorithms/selectionsort.cc46
-rw-r--r--1_anno/Programmazione_2/algorithms/sqrt.cc46
-rw-r--r--1_anno/Programmazione_2/coding_contest/dolcetti.cpp51
-rw-r--r--1_anno/Programmazione_2/coding_contest/gita.cpp46
-rw-r--r--1_anno/Programmazione_2/coding_contest/gribaudo.cpp47
-rw-r--r--1_anno/Programmazione_2/coding_contest/gualtieri.cpp46
-rw-r--r--1_anno/Programmazione_2/coding_contest/ladri.cpp53
-rw-r--r--1_anno/Programmazione_2/coding_contest/pizzini.cpp48
-rw-r--r--1_anno/Programmazione_2/coding_contest/scheletri.cpp56
-rw-r--r--1_anno/Programmazione_2/coding_contest/stazioni.cpp82
-rw-r--r--1_anno/Programmazione_2/coding_contest/tastevin.cpp38
-rw-r--r--1_anno/Programmazione_2/coding_contest/tastevin_paths.cpp67
-rw-r--r--1_anno/Programmazione_2/data_structures/bfs.cc186
-rw-r--r--1_anno/Programmazione_2/data_structures/bst.cc225
-rw-r--r--1_anno/Programmazione_2/data_structures/circle_double_list.cc185
-rw-r--r--1_anno/Programmazione_2/data_structures/circle_list.cc189
-rw-r--r--1_anno/Programmazione_2/data_structures/dfs.cc191
-rw-r--r--1_anno/Programmazione_2/data_structures/graph.cc164
-rw-r--r--1_anno/Programmazione_2/data_structures/graph_stl.cc221
-rw-r--r--1_anno/Programmazione_2/data_structures/list.cc164
-rw-r--r--1_anno/Programmazione_2/data_structures/list_double.cc182
-rw-r--r--1_anno/Programmazione_2/data_structures/matrix-graph.cc81
-rw-r--r--1_anno/Programmazione_2/data_structures/queue.cc72
-rw-r--r--1_anno/Programmazione_2/data_structures/queue_w_array.cc66
-rw-r--r--1_anno/Programmazione_2/data_structures/stack.cc70
-rw-r--r--1_anno/Programmazione_2/data_structures/stack_w_array.cc50
-rw-r--r--1_anno/Programmazione_2/data_structures/top-sort.cc212
-rw-r--r--1_anno/Programmazione_2/exercises/carattere-maggiore.cc40
-rw-r--r--1_anno/Programmazione_2/exercises/dequeue.cc137
-rw-r--r--1_anno/Programmazione_2/exercises/doppioni.cc77
-rw-r--r--1_anno/Programmazione_2/exercises/estremi-uguali.cc32
-rw-r--r--1_anno/Programmazione_2/exercises/even-length.cc27
-rw-r--r--1_anno/Programmazione_2/exercises/exam_08_10_14.cc202
-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
-rw-r--r--1_anno/Programmazione_2/exercises/inizia-con.cc33
-rw-r--r--1_anno/Programmazione_2/exercises/inserimento-coda.cc119
-rw-r--r--1_anno/Programmazione_2/exercises/inserimento-pila.cc116
-rw-r--r--1_anno/Programmazione_2/exercises/matrice-adj.cc151
-rw-r--r--1_anno/Programmazione_2/exercises/minore.cc27
-rw-r--r--1_anno/Programmazione_2/exercises/pop-stack.cc132
-rw-r--r--1_anno/Programmazione_2/exercises/prima-maiuscola.cc30
-rw-r--r--1_anno/Programmazione_2/exercises/ripetute.cc20
-rw-r--r--1_anno/Programmazione_2/exercises/sol-ripetute.cc25
-rw-r--r--1_anno/Programmazione_2/exercises/sottosequenza.cc26
-rw-r--r--1_anno/Programmazione_2/exercises/stringa-inversa.cc26
56 files changed, 5320 insertions, 0 deletions
diff --git a/1_anno/Programmazione_2/algorithms/binarysearch.cc b/1_anno/Programmazione_2/algorithms/binarysearch.cc
new file mode 100644
index 0000000..c9b4cd7
--- /dev/null
+++ b/1_anno/Programmazione_2/algorithms/binarysearch.cc
@@ -0,0 +1,33 @@
+#include<iostream>
+
+using namespace std;
+
+bool bs(int a[], int i, int j, int x) {
+ if(j<i) return false;
+ int mid = i+(j-i)/2;
+ if(a[mid] == x)
+ return true;
+ if(a[mid] > x)
+ return bs(a, i, mid-1, x);
+ return bs(a, mid+1, j, x);
+}
+
+bool bs2(int a[], int i, int j, int x) {
+ while(i <= j) {
+ int mid = i+(j-i)/2;
+ if(a[mid] == x) return true;
+ if(a[mid] < x)
+ i = mid+1;
+ else
+ j = mid-1;
+ }
+ return false;
+}
+
+int main() {
+ int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
+ for(int i = 0; i < 12; ++i)
+ cout << i << ' '<<bs(a, 0, 9, i) << ' ' << bs2(a, 0, 9, i) << endl;
+ return 0;
+}
+
diff --git a/1_anno/Programmazione_2/algorithms/cbrt.cc b/1_anno/Programmazione_2/algorithms/cbrt.cc
new file mode 100644
index 0000000..30c7792
--- /dev/null
+++ b/1_anno/Programmazione_2/algorithms/cbrt.cc
@@ -0,0 +1,37 @@
+#include<iostream>
+
+using namespace std;
+
+int cbrt(int n) {
+ int i = 0;
+ int j = n;
+ int q = (i+j)/2;
+ while(q*q*q != n) {
+ q = (i+j)/2;
+ if(q*q*q < n)
+ i=q;
+ else
+ j=q;
+ }
+ return q;
+}
+
+double cbrt2(int n) {
+ int i = 1;
+ while(i*i*i <= n)
+ ++i;
+ // precision
+
+ --i;
+ while(i*i*i < n)
+ i+=0.000001;
+
+ return i;
+}
+
+int main() {
+ int i;
+ cin >> i;
+ cout << i << ' ' << cbrt(i) << endl;
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/algorithms/insertionsort.cc b/1_anno/Programmazione_2/algorithms/insertionsort.cc
new file mode 100644
index 0000000..9b309d6
--- /dev/null
+++ b/1_anno/Programmazione_2/algorithms/insertionsort.cc
@@ -0,0 +1,42 @@
+#include<iostream>
+
+using namespace std;
+
+void insertionsort(int a[], int n) {
+ 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;
+ }
+ a[j+1] = key;
+ }
+}
+
+void insertionsort_rec(int a[], int n) {
+ if(n < 2) return;
+ insertionsort_rec(a, n-1);
+
+ int key = a[n-1];
+ int j = n-2;
+
+ while(j > -1 && a[j] > key) {
+ swap(a[j+1], a[j]);
+ --j;
+ }
+
+ a[j+1] = key;
+
+}
+
+int main() {
+ int arr[10] = {3, 450, 12, 4, -1, 0, 24, 95, 123, 0};
+ for(int i = 0; i < 10; ++i)
+ cout << *(arr+i) << ' ';
+ cout << endl;
+ insertionsort_rec(arr, 10);
+ for(int i = 0; i < 10; ++i)
+ cout << *(arr+i) << ' ';
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/algorithms/log.cc b/1_anno/Programmazione_2/algorithms/log.cc
new file mode 100644
index 0000000..1e49a2e
--- /dev/null
+++ b/1_anno/Programmazione_2/algorithms/log.cc
@@ -0,0 +1,25 @@
+#include<iostream>
+
+using namespace std;
+
+double log(double n) {
+ if(n <= 2) return 1.0;
+ return 1.0 + log(n/2);
+}
+
+int log2(double n) {
+ int a = 1;
+
+ while(n > 2) {
+ n /= 2;
+ ++a;
+ }
+
+ return a;
+}
+
+int main() {
+ for(int i = 0; i < 25; ++i)
+ cout << i << ' ' << log(i) << ' ' << log2(i) << endl;
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/algorithms/mergesort.cc b/1_anno/Programmazione_2/algorithms/mergesort.cc
new file mode 100644
index 0000000..68d28cb
--- /dev/null
+++ b/1_anno/Programmazione_2/algorithms/mergesort.cc
@@ -0,0 +1,52 @@
+#include<iostream>
+
+using namespace std;
+
+void merge(int A[], int l, int q, int r) {
+ int i = l;
+ int j = q+1;
+ int k = l;
+ int B[r];
+
+ while((i <= q) && (j <= r)) {
+ if(A[i] <= A[j])
+ B[k] = A[i++];
+ else
+ B[k] = A[j++];
+
+ k++;
+ }
+
+ while(i <= q)
+ B[k++] = A[i++];
+
+ while(j <= r)
+ B[k++] = A[j++];
+
+ for(k = l; k <= r; ++k)
+ A[k] = B[k];
+}
+
+void mergesort(int A[], int l, int r) {
+ if(l < r) {
+ int q = (l+r)/2;
+ mergesort(A, l, q);
+ mergesort(A, q+1, r);
+ merge(A, l, q, r);
+ }
+}
+
+
+int main() {
+ int a[] = {7,1,22,3,2,12,27,31,6};
+ for(int i = 0; i < 9; ++i) {
+ cout << a[i] << ' ';
+ }
+ cout << endl;
+ mergesort(a, 0, 8);
+ for(int i = 0; i < 9; ++i) {
+ cout << a[i] << ' ';
+ }
+
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/algorithms/pow.cc b/1_anno/Programmazione_2/algorithms/pow.cc
new file mode 100644
index 0000000..16cf419
--- /dev/null
+++ b/1_anno/Programmazione_2/algorithms/pow.cc
@@ -0,0 +1,25 @@
+#include<iostream>
+
+using namespace std;
+
+int pow(int x, int y) {
+ int a = 1;
+
+ for(int i = 0; i < y; ++i)
+ a*=x;
+
+ return a;
+}
+
+
+int pow2(int x, int y) {
+ if(y < 1) return 1;
+
+ return x*pow(x, y-1);
+}
+
+int main() {
+ cout << pow(2, 5) << endl;
+ cout << pow2(2, 5) << endl;
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/algorithms/quicksort.cc b/1_anno/Programmazione_2/algorithms/quicksort.cc
new file mode 100644
index 0000000..795bd7b
--- /dev/null
+++ b/1_anno/Programmazione_2/algorithms/quicksort.cc
@@ -0,0 +1,38 @@
+#include<iostream>
+
+using namespace std;
+
+int partition(int A[], int l, int r) {
+ int x = A[r];
+ int i = l-1;
+
+ for(int j = l; j < r; ++j) {
+ if(A[j] <= x) {
+ swap(A[++i], A[j]);
+ }
+ }
+ swap(A[++i], A[r]);
+ return i;
+}
+
+void quicksort(int A[], int l, int r) {
+ if(l < r) {
+ int q = partition(A, l, r);
+ quicksort(A, l, q-1);
+ quicksort(A, q+1, r);
+ }
+}
+
+int main() {
+ int a[] = {7,1,22,3,2,12,27,31,6};
+ for(int i = 0; i < 9; ++i) {
+ cout << a[i] << ' ';
+ }
+ cout << endl;
+ quicksort(a, 0, 8);
+ for(int i = 0; i < 9; ++i) {
+ cout << a[i] << ' ';
+ }
+
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/algorithms/selectionsort.cc b/1_anno/Programmazione_2/algorithms/selectionsort.cc
new file mode 100644
index 0000000..57dcc17
--- /dev/null
+++ b/1_anno/Programmazione_2/algorithms/selectionsort.cc
@@ -0,0 +1,46 @@
+#include<iostream>
+#include<algorithm>
+
+using namespace std;
+
+void selectionsort(int a[], int n) {
+ for(int i = 0; i < n-1; ++i) {
+ int min = i;
+ for(int j = i+1; j < n; ++j) {
+ if(a[j] < a[min])
+ min = j;
+ }
+
+ swap(a[min], a[i]);
+ }
+}
+
+int min_i(int a[], int i, int j) {
+ if(i == j) return i;
+
+ int k = min_i(a, i+1, j);
+ return (a[i] < a[k]) ? i : k;
+}
+
+void selectionsort_rec(int* a, int b, int e=0) {
+ if(b == e) return;
+
+ int key = min_i(a, e, b-1);
+ if(key != e)
+ swap(a[key], a[e]);
+
+ selectionsort_rec(a, b, e+1);
+}
+
+int main() {
+ int arr[] = {3,450,12,4,-1,0,24,95,123,0};
+ for(int i = 0; i < 10; ++i) {
+ cout << *(arr+i) << ' ';
+ }
+ cout << endl;
+ selectionsort_rec(arr, 10);
+ for(int i = 0; i < 10; ++i) {
+ cout << *(arr+i) << ' ';
+ }
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/algorithms/sqrt.cc b/1_anno/Programmazione_2/algorithms/sqrt.cc
new file mode 100644
index 0000000..aa6b032
--- /dev/null
+++ b/1_anno/Programmazione_2/algorithms/sqrt.cc
@@ -0,0 +1,46 @@
+#include<iostream>
+
+using namespace std;
+
+double abs(double n) {
+ if(n < 0) return -n;
+
+ return n;
+}
+
+
+double sq(int n) {
+ double x = n;
+ double y = 1;
+ while(x-y > 0.0000001) {
+ x = (x+y)/2;
+ y = n/x;
+ }
+ return x;
+}
+
+double sq2_n(double n, double a) {
+ if(abs(a*a - n) <= 0.000001) {
+ return a;
+ }
+
+ return sq2_n(n, (a+n/a)/2);
+}
+
+double sq2(int n) {
+ return sq2_n(n, n/2);
+}
+
+double sqrt_d(int n) {
+ double x = 1;
+ while(abs(x*x-n)>=0.0000001) {
+ x = ((n/x)+x)/2;
+ }
+ return x;
+}
+
+int main() {
+ cout << sq(81) << endl;
+ cout << sq2(81) << endl;
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/coding_contest/dolcetti.cpp b/1_anno/Programmazione_2/coding_contest/dolcetti.cpp
new file mode 100644
index 0000000..c3409a4
--- /dev/null
+++ b/1_anno/Programmazione_2/coding_contest/dolcetti.cpp
@@ -0,0 +1,51 @@
+#include<iostream>
+#include<fstream>
+#include<queue>
+#include<vector>
+
+using namespace std;
+
+int main() {
+ using tii = tuple<int, int, int>;
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int ts = 0; ts < 100; ++ts) {
+ int N;
+ in >> N;
+
+ priority_queue<tii, vector<tii>> pq;
+ tii qq;
+ for(int i = 0; i < N; ++i) {
+ int e1, e2;
+ in >> e1 >> e2;
+ get<0>(qq) = e1-e2;
+ get<1>(qq) = e1;
+ get<2>(qq) = e2;
+
+ pq.push(qq);
+ }
+
+ int counter = N;
+ int sum{};
+
+ while(counter-- > N/2) {
+ qq = pq.top();
+ sum += get<1>(qq);
+ pq.pop();
+ }
+
+ while(!pq.empty()) {
+ qq = pq.top();
+ sum += get<2>(qq);
+ pq.pop();
+ }
+
+ out << sum << endl;
+ }
+
+ in.close();
+ out.close();
+ return 0;
+}
+
diff --git a/1_anno/Programmazione_2/coding_contest/gita.cpp b/1_anno/Programmazione_2/coding_contest/gita.cpp
new file mode 100644
index 0000000..cbb4910
--- /dev/null
+++ b/1_anno/Programmazione_2/coding_contest/gita.cpp
@@ -0,0 +1,46 @@
+#include<iostream>
+#include<fstream>
+#include<vector>
+#include<map>
+
+using namespace std;
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int c = 0; c < 100; ++c) {
+ int N, L;
+ in >> N >> L;
+ vector<pair<short, int>> students;
+ for(int i = 0; i < N; ++i) {
+ int num;
+ in >> num;
+ students.push_back({num, 0});
+ }
+
+ int index, val;
+ for(int i = 0; i < L; ++i) {
+ in >> index >> val;
+ students[index].second += val;
+ }
+
+ vector<pair<short, int>> errors;
+ short _j{};
+ for(auto const& i : students) {
+ if(i.second < i.first) {
+ errors.push_back({_j, i.first-i.second});
+ }
+ _j++;
+ }
+
+ out << errors.size() << ' ';
+ for(auto const& i : errors) {
+ out << i.first << ' ' << i.second << ' ';
+ }
+ out << endl;
+ }
+ out.close();
+ in.close();
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/coding_contest/gribaudo.cpp b/1_anno/Programmazione_2/coding_contest/gribaudo.cpp
new file mode 100644
index 0000000..39d0e42
--- /dev/null
+++ b/1_anno/Programmazione_2/coding_contest/gribaudo.cpp
@@ -0,0 +1,47 @@
+#include<iostream>
+#include<vector>
+#include<fstream>
+
+using namespace std;
+
+int maxpath(vector<vector<int>>& v) {
+ for(int i = v.size()-2; i >= 0; --i) {
+ for(int j = 0; j <= i; ++j) {
+ if(v[i+1][j] > v[i+1][j+1]) {
+ v[i][j] += v[i+1][j];
+ } else {
+ v[i][j] += v[i+1][j+1];
+ }
+ }
+ }
+
+ return v[0][0];
+}
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int ts = 0; ts < 1; ++ts) {
+ int N;
+ in >> N;
+ vector<vector<int>> triangle;
+
+ for(int i = 0; i < N; ++i) {
+ int e;
+ triangle.push_back(vector<int>{});
+ int j;
+ for(j = 0; j <= i; ++j) {
+ in >> e;
+ triangle[i].push_back(e);
+ }
+ for(; j < N; ++j)
+ triangle[i].push_back(0);
+ }
+ out << maxpath(triangle) << endl;
+ }
+
+ in.close();
+ out.close();
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/coding_contest/gualtieri.cpp b/1_anno/Programmazione_2/coding_contest/gualtieri.cpp
new file mode 100644
index 0000000..f8a0ecf
--- /dev/null
+++ b/1_anno/Programmazione_2/coding_contest/gualtieri.cpp
@@ -0,0 +1,46 @@
+#include<iostream>
+#include<fstream>
+#include<map>
+
+using namespace std;
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int ts = 0; ts < 100; ++ts) {
+ string P{}, L{};
+ in >> P;
+ in >> L;
+ map<char, int> chars;
+
+ for(auto const& c : P) {
+ (chars.find(c) == chars.end()) ? chars[c] = 1 : chars[c]+=1;
+ }
+ int lenn = L.length();
+ int lenp = P.length();
+ int counter{};
+
+ for(int i = 0; i < lenn-lenp+1; ++i) {
+ map<char, int> tmp;
+ bool check{true};
+ for(int j = i; j < i+lenp; ++j) {
+ (tmp.find(L[j]) == tmp.end()) ? tmp[L[j]] = 1 : tmp[L[j]]+=1;
+ }
+ for(auto const &i : tmp) {
+ if(chars[i.first] != tmp[i.first]) {
+ check = false;
+ break;
+ }
+ }
+ if(check)
+ ++counter;
+ }
+ out << counter << endl;
+
+ }
+
+ out.close();
+ in.close();
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/coding_contest/ladri.cpp b/1_anno/Programmazione_2/coding_contest/ladri.cpp
new file mode 100644
index 0000000..04e8e65
--- /dev/null
+++ b/1_anno/Programmazione_2/coding_contest/ladri.cpp
@@ -0,0 +1,53 @@
+#include<iostream>
+#include<fstream>
+#include<vector>
+
+using namespace std;
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(short _ = 0; _ < 100; ++_) {
+ int N, K, M;
+ in >> N >> K >> M;
+ int* path = new int[N+1];
+ int i;
+ for(i = 0; i < N; ++i)
+ in >> path[i];
+
+ path[i] = M;
+ int start = 0;
+ vector<int> values;
+ /* 1 31 33 38 62 69 93 97 98 99 */
+ /* x x x x x x
+ * K = 30
+ */
+ for(int i = 0; i < N+1; ++i) {
+ if(path[i] - start > K) {
+ for(int j = i-1; j >= 0; --j) {
+ if(path[i] - path[j] <= K) {
+ values.push_back(path[j]);
+ start = path[j];
+ i = j;
+ break;
+ }
+ }
+ }
+ }
+
+ // Stampa la path corretta per debug
+ for(auto const& i: values)
+ cout << i << ' ';
+
+ cout << endl;
+ out << values.size() << endl;
+ delete[] path;
+ }
+
+
+ out.close();
+ in.close();
+
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/coding_contest/pizzini.cpp b/1_anno/Programmazione_2/coding_contest/pizzini.cpp
new file mode 100644
index 0000000..4fcb4ab
--- /dev/null
+++ b/1_anno/Programmazione_2/coding_contest/pizzini.cpp
@@ -0,0 +1,48 @@
+#include<iostream>
+#include<fstream>
+#include<vector>
+
+using namespace std;
+
+void get_fib(vector<int> &v, int N) {
+ int a = v.at(0);
+ int b = v.at(1);
+ while(b <= N) {
+ a += b;
+ v.push_back(a);
+ swap(a, b);
+ }
+ v.pop_back();
+}
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(short _ = 0; _ < 100; ++_) {
+ int N;
+ in >> N;
+ vector<int> fib {1, 2};
+ get_fib(fib, N);
+ vector<int> seq(fib.size(), 0);
+
+ int sum{};
+ for(int i = fib.size()-1; i >= 0; --i) {
+ if(fib.at(i) + sum > N) continue;
+
+ sum += fib.at(i);
+ seq[i] = 1;
+ }
+
+
+ for(auto const& i : seq)
+ out << i;
+
+ out << endl;
+ }
+
+ out.close();
+ in.close();
+
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/coding_contest/scheletri.cpp b/1_anno/Programmazione_2/coding_contest/scheletri.cpp
new file mode 100644
index 0000000..2389d25
--- /dev/null
+++ b/1_anno/Programmazione_2/coding_contest/scheletri.cpp
@@ -0,0 +1,56 @@
+#include<iostream>
+#include<fstream>
+#include<vector>
+#include<algorithm>
+
+using namespace std;
+
+int find_i(int index, vector<int> cms) {
+ for(int i = index; i < cms.size(); ++i) {
+ if(cms.at(i) != 0)
+ return i;
+ }
+
+ return 0;
+}
+
+int find_j(int index, vector<int> cms) {
+ for(int j = index; j < cms.size()-1; ++j) {
+ if(cms.at(j+1) == 0)
+ return j+1;
+ }
+
+ return cms.size();
+}
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ short N;
+ for(int __c = 0; __c < 100; ++__c) {
+ in >> N;
+ vector<int> cms;
+ int el;
+ for(short i = 0; i < N; ++i) {
+ in >> el;
+ cms.push_back(el);
+ }
+
+ int counter{};
+ int i{}, j{};
+ while(count_if(begin(cms), end(cms), [](int num) { return num == 0; } ) != cms.size() ) {
+ i = find_i(i, cms);
+ j = find_j(i, cms);
+ for(int ii = i; ii < j; ++ii) {
+ --cms[ii];
+ }
+ ++counter;
+ }
+ out << counter << endl;
+ }
+
+ out.close();
+ in.close();
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/coding_contest/stazioni.cpp b/1_anno/Programmazione_2/coding_contest/stazioni.cpp
new file mode 100644
index 0000000..29ede44
--- /dev/null
+++ b/1_anno/Programmazione_2/coding_contest/stazioni.cpp
@@ -0,0 +1,82 @@
+#include<iostream>
+#include<fstream>
+#include<algorithm>
+#include<vector>
+
+using namespace std;
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int ts = 0; ts < 1; ++ts) {
+ int N, S;
+ in >> N >> S;
+ vector<long> st;
+ vector<vector<long>> paths;
+ vector<vector<long>> paths2;
+ vector<vector<long>> paths3;
+
+ int e;
+ for(int i = 0; i < N; ++i) {
+ in >> e;
+ st.push_back(e);
+ }
+
+ int index{};
+ for(int i = 0; i < N-S+1; ++i) {
+ for(int j = 0; j < N; ++j) {
+ paths.push_back(vector<long>{});
+ paths[index].push_back(i);
+ for(int k = j; paths[index].size() < S; ++k) {
+ int t = (k == N) ? 0 : k;
+ if(k > N) break;
+ paths[index].push_back(t);
+ }
+ sort(begin(paths[index]), end(paths[index]));
+ if(paths[index].size() == S)
+ paths2.push_back(paths[index]);
+ ++index;
+ }
+ }
+ for(int i = 0; i < paths2.size(); ++i) {
+ bool check{true};
+ if(paths2[i].size() != S) continue;
+ for(int j = 0; j < paths2[i].size()-1; ++j) {
+ if(paths2[i].at(j) == paths2[i].at(j+1)) {
+ check = false;
+ break;
+ }
+ }
+ if(check)
+ paths3.push_back(paths2[i]);
+ }
+
+ for(auto const& i : paths3) {
+ for(auto const& j : i)
+ cout << st[j] << ' ';
+
+ cout << endl;
+ }
+ cout << endl;
+
+ int major{};
+ for(int i = 0; i < paths3.size(); ++i) {
+ vector<long> diffs;
+ for(int j = 0; j < paths3[i].size()-1; ++j) {
+ int p1 = st[paths3[i][j+1]];
+ int p2 = st[paths3[i][j]];
+ diffs.push_back(p1 - p2);
+ }
+ int miner = *min_element(begin(diffs), end(diffs));
+ if(miner > major)
+ major = miner;
+ }
+ cout << ts << ' ' << major << endl;
+ out << major << endl;
+ }
+
+ in.close();
+ out.close();
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/coding_contest/tastevin.cpp b/1_anno/Programmazione_2/coding_contest/tastevin.cpp
new file mode 100644
index 0000000..301ebcf
--- /dev/null
+++ b/1_anno/Programmazione_2/coding_contest/tastevin.cpp
@@ -0,0 +1,38 @@
+#include<iostream>
+#include<fstream>
+#include<vector>
+#include<algorithm>
+
+using namespace std;
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int ts = 0; ts < 100; ++ts) {
+ int N;
+ in >> N;
+ vector<int> arr(N);
+ for(int i = 0; i < N; ++i) {
+ in >> arr.at(i);
+ }
+
+ vector<int> paths(N, 1);
+
+ for(int i = N-2; i >= 0; --i) {
+ int mx = 0;
+ for(int j = i+2; j < N; ++j) {
+ if(mx < paths[j] && arr[j] >= arr[i]) {
+ mx = paths[j];
+ }
+ }
+ paths[i] += mx;
+ }
+
+ out << *max_element(begin(paths), end(paths)) << '\n';
+ }
+
+ in.close();
+ out.close();
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/coding_contest/tastevin_paths.cpp b/1_anno/Programmazione_2/coding_contest/tastevin_paths.cpp
new file mode 100644
index 0000000..eb7da54
--- /dev/null
+++ b/1_anno/Programmazione_2/coding_contest/tastevin_paths.cpp
@@ -0,0 +1,67 @@
+// It prints all possible paths
+
+#include<iostream>
+#include<fstream>
+#include<vector>
+
+using namespace std;
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int ts = 0; ts < 100; ++ts) {
+ int N;
+ in >> N;
+ vector<int> arr;
+ int e;
+ for(int i = 0; i < N; ++i) {
+ in >> e;
+ arr.push_back(e);
+ }
+
+ int max_value{};
+ int value;
+
+ for(int i = 0; i < N; ++i) {
+ vector<int> tmp;
+ tmp.push_back(i);
+ value = arr[i];
+ for(int j = i+2; j < N; ++j) {
+ if(arr[j] >= value) {
+ tmp.push_back(j);
+ value = arr[j];
+ ++j;
+ }
+ }
+ while(!tmp.empty()) {
+ if(tmp.size() > max_value) {
+ for(auto const&i : tmp) {
+ cout << i << ' ';
+ }
+ cout << endl;
+ max_value = tmp.size();
+ }
+ int k = tmp.back();
+ tmp.pop_back();
+ if(tmp.size() > 0)
+ value = arr[tmp.back()];
+ else
+ value = arr[k];
+ for(int j = k+1; j < N; ++j) {
+ if(arr[j] >= value) {
+ value = arr[j];
+ tmp.push_back(j);
+ ++j;
+ }
+ }
+ }
+ }
+
+ out << max_value << '\n';
+ }
+
+ in.close();
+ out.close();
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/data_structures/bfs.cc b/1_anno/Programmazione_2/data_structures/bfs.cc
new file mode 100644
index 0000000..2b4efbd
--- /dev/null
+++ b/1_anno/Programmazione_2/data_structures/bfs.cc
@@ -0,0 +1,186 @@
+#include<iostream>
+#include<vector>
+#include<queue>
+#define W -1
+#define G 0
+#define B 1
+
+using namespace std;
+
+template<class H>
+class node {
+public:
+ explicit node(H key, node<H>* next) : _key{key}, _next(next) {}
+ const H& key() const { return _key; }
+ H& key() { return _key; }
+ const node<H>*& next() const { return _next; }
+ node<H>*& next() { return _next; }
+private:
+ H _key;
+ node<H>* _next;
+};
+
+template<class H>
+class list {
+public:
+ list() : _head{nullptr} {}
+ ~list() {
+ while(_head) {
+ auto tmp = _head;
+ _head = _head->next();
+ delete tmp;
+ }
+ }
+ list<H>* push(H val) {
+ auto iter = _head;
+ while(iter && iter->next())
+ iter = iter->next();
+
+ if(!iter)
+ _head = new node<H>{val, nullptr};
+ else
+ iter->next() = new node<H>{val, nullptr};
+
+ return this;
+ }
+ void print() {
+ auto iter = _head;
+ while(iter) {
+ cout << iter->key() << ' ';
+ iter = iter->next();
+ }
+ }
+ vector<H> as_vector() {
+ vector<H> v;
+ auto iter = _head;
+ while(iter) {
+ v.push_back(iter->key());
+ iter = iter->next();
+ }
+ return v;
+ }
+ node<H>* search(H val) {
+ auto iter = _head;
+ while(iter && iter->key() != val) {
+ iter = iter->next();
+ }
+
+ return iter;
+ }
+private:
+ node<H>* _head;
+};
+
+template<class H>
+class graph {
+public:
+
+private:
+ int _len, _nodes, _edges;
+ int* _parents;
+ int* _distances;
+ H** _k; // it works like a dictionary, it saves the keys
+ list<int>** _adj;
+ int _index(H val) {
+ for(int i = 0; i < _nodes; ++i)
+ if(*_k[i] == val) return i;
+
+ return -1;
+ }
+public:
+ graph(int len) : _len{len}, _nodes{0}, _edges{0} {
+ _k = new H*[len];
+ _adj = new list<int>*[_len];
+ _parents = new int[_len];
+ _distances = new int[_len];
+ for(int i = 0; i < _len; ++i) {
+ _k[i] = nullptr;
+ _adj[i] = new list<int>{};
+ }
+ }
+
+ graph<H>* add_node(H k) {
+ if(_nodes == _len) return this;
+ if(_index(k) >= 0) return this; // node is already there
+
+ _k[_nodes++] = new H(k);
+
+ return this;
+ }
+
+ void bfs(int s) {
+ int colors[_len];
+ queue<int> q;
+
+ for(int i = 0; i < _nodes; ++i) {
+ colors[i] = W;
+ _parents[i] = -1;
+ _distances[i] = 999999999;
+ }
+ q.push(s);
+ colors[s] = G;
+ _distances[s] = 0;
+ while(!q.empty()) {
+ int x = q.front();
+ q.pop();
+ for(auto const& j : _adj[x]->as_vector()) {
+ if(colors[j] == W) {
+ colors[j] = G;
+ q.push(j);
+ _parents[j] = x;
+ _distances[j] = _distances[x] + 1;
+ }
+ }
+ colors[x] = B;
+ }
+
+ for(int i = 0; i < _nodes; ++i) {
+ cout << "[" << i << "]->";
+ if(_distances[i]==999999999) cout << "inf." << endl;
+ else cout << _distances[i] << endl;
+ }
+ }
+
+ void bfs(H x) {
+ int s = _index(x);
+ if(s != -1)
+ bfs(s);
+ }
+
+ graph<H>* add_edge(H x, H y) {
+ int i = _index(x);
+ int j = _index(y);
+ if(i < 0 || j < 0) return this;
+
+ if(!_adj[i]->search(j)) {
+ _adj[i]->push(j);
+ _edges++;
+ }
+
+ return this;
+ }
+
+ void print() {
+ for(int i = 0; i < _nodes; ++i) {
+ cout << "(" << i << ", " << *_k[i] << "): ";
+ for(auto const& j : _adj[i]->as_vector())
+ cout << "(" << j << ", " << *_k[j] << "), ";
+ cout << '\n';
+ }
+ }
+};
+
+
+int main() {
+ graph<string>* g = new graph<string>(5);
+ g->add_node("hello")->add_node("greg")->add_node("yes");
+ g->add_node("nop")->add_node("ok");
+ g->add_edge("hello", "ok");
+ g->add_edge("ok", "yes")->add_edge("yes", "ok")->add_edge("yes", "yes");
+ g->add_edge("yes", "nop");
+ g->print();
+ g->bfs("hello");
+
+ delete g;
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/data_structures/bst.cc b/1_anno/Programmazione_2/data_structures/bst.cc
new file mode 100644
index 0000000..9223e04
--- /dev/null
+++ b/1_anno/Programmazione_2/data_structures/bst.cc
@@ -0,0 +1,225 @@
+#include<iostream>
+
+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} {}
+
+ ~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->_preorder(os, tree->root);
+ return os;
+ }
+private:
+ 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) {
+ _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() {
+ bst<int>* b = new bst<int>{};
+
+ // b->insert(12)->insert(5)->insert(18)->insert(2)->insert(9);
+ // b->insert(15)->insert(13)->insert(17)->insert(19);
+
+ b->insert({12, 5, 18, 2, 9, 15, 13, 17, 19});
+ cout << b << endl;
+ cout << (b->search(5) != nullptr) << endl;
+ cout << (b->search(1) != nullptr) << endl;
+ cout << b->max()->key << ' ' << b->min()->key << endl;
+ for(auto const& i : {12, 9, 14, 18}) {
+ auto elem = b->successor(i);
+ if(elem)
+ cout << "(" << i << ", " << elem->key << ") ";
+ }
+ cout << endl;
+
+ for(auto const& i : {9, 2, 5, 15, 18, 12, 19}) {
+ auto elem = b->predecessor(i);
+ if(elem)
+ cout << "(" << i << ", " << elem->key << ") ";
+ }
+ cout << endl;
+ b->remove({5, 12});
+ cout << b << endl;
+
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/data_structures/circle_double_list.cc b/1_anno/Programmazione_2/data_structures/circle_double_list.cc
new file mode 100644
index 0000000..f162e57
--- /dev/null
+++ b/1_anno/Programmazione_2/data_structures/circle_double_list.cc
@@ -0,0 +1,185 @@
+#include<iostream>
+
+using namespace std;
+
+template<typename T>
+struct node {
+ T value;
+ node* prev;
+ node* next;
+};
+
+
+template<typename T>
+class list {
+public:
+ list() : _head{nullptr} {}
+
+ ~list() {
+ node<T>* iter = _head;
+ while(iter->next != _head) {
+ node<T>* tmp = iter;
+ delete tmp;
+ iter = iter->next;
+ }
+ node<T>* tmp = iter;
+ delete tmp;
+ }
+
+ list* push_front(T val) {
+ auto elem = _last();
+ if(!_head) {
+ _head = new node<T>{val, nullptr, nullptr};
+ _head->prev = _head->next = _head;
+ } else {
+ _head = new node<T>{val, elem, _head};
+ elem->next = _head->next->prev = _head;
+ }
+
+ return this;
+ }
+
+ list* push_back(T val) {
+ if(!_head) return this->push_front(val);
+
+ auto last_e = _last();
+ last_e->next = new node<T>{val, last_e, _head};
+ _head->prev = last_e->next;
+
+ return this;
+ }
+
+ list* push_after_value(T val, T newval) {
+ node<T>* iter = _search(val);
+ if(iter) {
+ node<T>* nod = new node<T>{newval, iter, iter->next};
+ iter->next = nod;
+ nod->next->prev = nod;
+ }
+
+ return this;
+ }
+
+ list* push_before_value(T val, T newval) {
+ node<T>* elem = _search(val);
+ if(!elem) return this;
+
+ node<T>* iter = _head;
+
+ if(iter->value == val)
+ return this->push_front(newval);
+
+ while(iter->next != elem)
+ iter = iter->next;
+
+ node<T>* nod = new node<T>{newval, iter, iter->next};
+ iter->next = nod;
+ nod->next->prev = nod;
+
+ return this;
+ }
+
+ list* pop(int val) {
+ node<T>* elem = _search(val);
+ if(!elem) return this;
+
+ if(elem == _head) return this->pop_front();
+
+ node<T>* iter = elem->prev;
+ node<T>* temp = iter->next;
+ iter->next = iter->next->next;
+ iter->next->prev = iter;
+ delete temp;
+
+ return this;
+ }
+
+ list* pop_front() {
+ if(!_head)
+ return this;
+
+ auto last_e = _last();
+ node<T>* elem = _head;
+ _head = _head->next;
+ _head->prev = last_e;
+ last_e->next = _head;
+ delete elem;
+
+ return this;
+ }
+
+ list* pop_back() {
+ if(!_head)
+ return this;
+
+ auto last_e = _last();
+
+ if(last_e == _head) {
+ delete _head;
+ _head = nullptr;
+ } else {
+ auto iter = last_e->prev;
+ delete iter->next;
+ iter->next = _head;
+ _head->prev = iter;
+ }
+
+ return this;
+ }
+
+ void print() {
+ node<T>* iter = _head;
+ while(iter != nullptr) {
+ cout << iter->value << ' ';
+ cout << "[[ " << iter->prev->value << ", ";
+ cout << iter->next->value << " ]], ";
+ iter = iter->next;
+ if(iter == _head) break;
+ }
+ }
+private:
+ node<T>* _last() {
+ node<T>* iter = _head;
+ while(iter && iter->next != _head) {
+ iter = iter->next;
+ }
+
+ return iter;
+ }
+
+ node<T>* _search(T val) {
+ node<T>* iter = _head;
+ if(iter->value == val) return iter;
+
+ while(iter && iter->value != val) {
+ iter = iter->next;
+ if(iter == _head) return nullptr;
+ }
+
+ return iter;
+ }
+
+ node<T>* _head;
+};
+
+int main() {
+ list<int>* l = new list<int>{};
+ l->push_front(2);
+ l->push_back(1)->push_back(3);
+ l->push_front(5)->push_front(9);
+ l->push_back(0)->push_back(6);
+ l->print(); cout << '\n';
+ l->push_after_value(7, -2);
+ l->push_before_value(9, 10);
+ l->print(); cout << '\n';
+ l->pop_front();
+ l->pop_front();
+ l->pop_back();
+ l->pop_front();
+ l->print(); cout << '\n';
+ l->pop(2);
+ l->print(); cout << '\n';
+
+ delete l;
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/data_structures/circle_list.cc b/1_anno/Programmazione_2/data_structures/circle_list.cc
new file mode 100644
index 0000000..2143ac1
--- /dev/null
+++ b/1_anno/Programmazione_2/data_structures/circle_list.cc
@@ -0,0 +1,189 @@
+#include<iostream>
+
+using namespace std;
+
+template<typename T>
+struct node {
+ T value;
+ node* next;
+};
+
+
+template<typename T>
+class list {
+public:
+ list() : _head{nullptr} {}
+
+ ~list() {
+ node<T>* iter = _head;
+ while(iter->next != _head) {
+ node<T>* tmp = iter;
+ delete tmp;
+ iter = iter->next;
+ }
+ node<T>* tmp = iter;
+ delete tmp;
+ }
+
+ list* push_front(T val) {
+ auto elem = _last();
+ _head = new node<T>{val, _head};
+ if(!elem)
+ elem = _head;
+
+ elem->next = _head;
+
+ return this;
+ }
+
+ list* push_back(T val) {
+ if(!_head) return this->push_front(val);
+
+ auto last_e = _last();
+ last_e->next = new node<T>{val, _head};
+
+ return this;
+ }
+
+ list* push_after_value(T val, T newval) {
+ node<T>* iter = _search(val);
+ if(iter)
+ iter->next = new node<T>{newval, iter->next};
+
+ return this;
+ }
+
+ list* push_before_value(T val, T newval) {
+ node<T>* elem = _search(val);
+ if(!elem) return this;
+
+ node<T>* iter = _head;
+
+ if(iter->value == val)
+ return this->push_front(newval);
+
+ while(iter->next != elem)
+ iter = iter->next;
+
+ iter->next = new node<T>{newval, iter->next};
+
+ return this;
+ }
+
+ list* pop(int val) {
+ node<T>* elem = _search(val);
+ if(!elem) return this;
+
+ node<T>* iter = _head;
+ if(iter == elem) return this->pop_front();
+
+ while(iter->next != elem)
+ iter = iter->next;
+
+ node<T>* temp = iter->next;
+ iter->next = iter->next->next;
+ delete temp;
+
+ return this;
+ }
+
+ list* pop_front() {
+ if(!_head)
+ return this;
+
+ auto last_e = _last();
+
+ if(last_e == _head) {
+ delete _head;
+ _head = nullptr;
+ } else {
+ node<T>* elem = _head;
+ _head = _head->next;
+ last_e->next = _head;
+ delete elem;
+ }
+
+ return this;
+ }
+
+ list* pop_back() {
+ if(!_head)
+ return this;
+
+ node<T>* iter = _head;
+ auto last_e = _last();
+
+ if(last_e == _head) {
+ delete iter;
+ _head = nullptr;
+ } else {
+ while(iter->next != last_e) {
+ iter = iter->next;
+ }
+
+ delete iter->next;
+ iter->next = _head;
+ }
+
+ return this;
+ }
+
+ void print() {
+ node<T>* iter = _head;
+ while(iter) {
+ cout << iter->value << ' ';
+ iter = iter->next;
+ if(iter == _head) break;
+ }
+ }
+private:
+ node<T>* _last() {
+ node<T>* iter = _head;
+ while(iter && iter->next != _head) {
+ iter = iter->next;
+ }
+
+ return iter;
+ }
+
+ node<T>* _search(T val) {
+ node<T>* iter = _head;
+ if(iter->value == val) return iter;
+
+ while(iter && iter->value != val) {
+ iter = iter->next;
+ if(iter == _head) return nullptr;
+ }
+
+ return iter;
+ }
+
+ node<T>* _head;
+};
+
+int main() {
+ list<int>* l = new list<int>{};
+ l->push_before_value(4, 1);
+ l->push_back(4);
+ l->push_back(1);
+ l->push_back(0);
+ l->push_front(2);
+ l->print(); cout << endl;
+ l->pop_back();
+ l->print(); cout << endl;
+ l->pop_front();
+ l->print(); cout << endl;
+ l->pop_back();
+ l->print(); cout << endl;
+ l->push_front(3);
+ l->print(); cout << endl;
+ l->push_after_value(4, 7);
+ l->print(); cout << endl;
+ l->push_before_value(3, 5);
+ l->print(); cout << endl;
+ l->pop(5);
+ l->print(); cout << endl;
+
+ delete l;
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/data_structures/dfs.cc b/1_anno/Programmazione_2/data_structures/dfs.cc
new file mode 100644
index 0000000..744f153
--- /dev/null
+++ b/1_anno/Programmazione_2/data_structures/dfs.cc
@@ -0,0 +1,191 @@
+#include<iostream>
+#include<vector>
+#include<queue>
+#define W -1
+#define G 0
+#define B 1
+
+using namespace std;
+
+template<class H>
+class node {
+public:
+ explicit node(H key, node<H>* next) : _key{key}, _next(next) {}
+ const H& key() const { return _key; }
+ H& key() { return _key; }
+ const node<H>*& next() const { return _next; }
+ node<H>*& next() { return _next; }
+private:
+ H _key;
+ node<H>* _next;
+};
+
+template<class H>
+class list {
+public:
+ list() : _head{nullptr} {}
+ ~list() {
+ while(_head) {
+ auto tmp = _head;
+ _head = _head->next();
+ delete tmp;
+ }
+ }
+ list<H>* push(H val) {
+ auto iter = _head;
+ while(iter && iter->next())
+ iter = iter->next();
+
+ if(!iter)
+ _head = new node<H>{val, nullptr};
+ else
+ iter->next() = new node<H>{val, nullptr};
+
+ return this;
+ }
+ void print() {
+ auto iter = _head;
+ while(iter) {
+ cout << iter->key() << ' ';
+ iter = iter->next();
+ }
+ }
+ vector<H> as_vector() {
+ vector<H> v;
+ auto iter = _head;
+ while(iter) {
+ v.push_back(iter->key());
+ iter = iter->next();
+ }
+ return v;
+ }
+ node<H>* search(H val) {
+ auto iter = _head;
+ while(iter && iter->key() != val) {
+ iter = iter->next();
+ }
+
+ return iter;
+ }
+private:
+ node<H>* _head;
+};
+
+template<class H>
+class graph {
+private:
+ int _len, _nodes, _edges;
+ int* _parents;
+ int* _radixes;
+ int* _distances;
+ int* _finishes;
+ int* _colors;
+ int _time;
+ int _current;
+ H** _k; // it works like a dictionary, it saves the keys
+ list<int>** _adj;
+ int _index(H val) {
+ for(int i = 0; i < _nodes; ++i)
+ if(*_k[i] == val) return i;
+
+ return -1;
+ }
+ void _dfsvisit(int u) {
+ _colors[u] = G;
+ _distances[u] = _time++;
+ _radixes[u] = _current;
+ for(auto const& v : _adj[u]->as_vector()) {
+ if(_colors[v] == W) {
+ _parents[v] = u;
+ _dfsvisit(v);
+ }
+ }
+ _colors[u] = B;
+ _finishes[u] = _time++;
+ }
+public:
+ graph(int len) : _len{len}, _nodes{0}, _edges{0} {
+ _k = new H*[len];
+ _adj = new list<int>*[_len];
+ _parents = new int[_len];
+ _radixes = new int[_len];
+ _distances = new int[_len];
+ _finishes = new int[_len];
+ _colors = new int[_len];
+ for(int i = 0; i < _len; ++i) {
+ _k[i] = nullptr;
+ _adj[i] = new list<int>{};
+ }
+ }
+
+ graph<H>* add_node(H k) {
+ if(_nodes == _len) return this;
+ if(_index(k) >= 0) return this; // node is already there
+
+ _k[_nodes++] = new H(k);
+
+ return this;
+ }
+
+
+ void dfs() {
+ _time = 0;
+ for(int i = 0; i < _nodes; ++i) {
+ _colors[i] = W;
+ _parents[i] = -1;
+ }
+
+ for(int i = 0; i < _nodes; ++i) {
+ if(_colors[i] == W) {
+ _current = i;
+ _dfsvisit(i);
+ }
+ }
+ for(int i = 0; i < _nodes; ++i) {
+ cout << *_k[i] << "(" << _distances[i]+1 << ',' << _finishes[i]+1 << ")" << endl;
+ }
+ }
+
+ graph<H>* add_edge(H x, H y) {
+ int i = _index(x);
+ int j = _index(y);
+ if(i < 0 || j < 0) return this;
+
+ if(!_adj[i]->search(j)) {
+ _adj[i]->push(j);
+ _edges++;
+ }
+
+ return this;
+ }
+
+ void print() {
+ for(int i = 0; i < _nodes; ++i) {
+ cout << "(" << i << ", " << *_k[i] << "): ";
+ for(auto const& j : _adj[i]->as_vector())
+ cout << "(" << j << ", " << *_k[j] << "), ";
+ cout << '\n';
+ }
+ }
+};
+
+
+int main() {
+ graph<char>* g = new graph<char>(6);
+ g->add_node('u')->add_node('v')->add_node('x')->add_node('y');
+ g->add_node('w')->add_node('z');
+ g->add_edge('u', 'v');
+ g->add_edge('u', 'x');
+ g->add_edge('x', 'v');
+ g->add_edge('y', 'x');
+ g->add_edge('v', 'y');
+ g->add_edge('w', 'y');
+ g->add_edge('w', 'z');
+ g->add_edge('z', 'z');
+
+ g->print();
+ g->dfs();
+
+ delete g;
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/data_structures/graph.cc b/1_anno/Programmazione_2/data_structures/graph.cc
new file mode 100644
index 0000000..12837be
--- /dev/null
+++ b/1_anno/Programmazione_2/data_structures/graph.cc
@@ -0,0 +1,164 @@
+#include<iostream>
+#include<vector>
+
+using namespace std;
+
+template<class H>
+class node {
+public:
+ explicit node(H key, node<H>* next) : _key{key}, _next(next) {}
+ const H& key() const { return _key; }
+ H& key() { return _key; }
+ const node<H>*& next() const { return _next; }
+ node<H>*& next() { return _next; }
+private:
+ H _key;
+ node<H>* _next;
+};
+
+template<class H>
+class list {
+public:
+ list() : _head{nullptr} {}
+ ~list() {
+ while(_head) {
+ auto tmp = _head;
+ _head = _head->next();
+ delete tmp;
+ }
+ }
+ list<H>* push(H val) {
+ auto iter = _head;
+ while(iter && iter->next())
+ iter = iter->next();
+
+ if(!iter)
+ _head = new node<H>{val, nullptr};
+ else
+ iter->next() = new node<H>{val, nullptr};
+
+ return this;
+ }
+ list<H>* pop(H val) {
+ auto elem = search(val);
+ if(!elem)
+ return this;
+
+ auto iter = _head;
+ // This is the case when head is the element we want to pop
+ if(iter == elem) {
+ delete _head;
+ _head = nullptr;
+ return this;
+ }
+
+ while(iter && iter->next() != elem)
+ iter = iter->next();
+
+ auto tmp = iter->next();
+ if(iter->next()->next()) {
+ iter->next() = iter->next()->next();
+ } else { // the element we want to pop is the tail
+ iter->next() = nullptr;
+ }
+ delete tmp;
+
+ return this;
+ }
+ void print() {
+ auto iter = _head;
+ while(iter) {
+ cout << iter->key() << ' ';
+ iter = iter->next();
+ }
+ }
+ vector<H> as_vector() {
+ vector<H> v;
+ auto iter = _head;
+ while(iter) {
+ v.push_back(iter->key());
+ iter = iter->next();
+ }
+ return v;
+ }
+ node<H>* search(H val) {
+ auto iter = _head;
+ while(iter && iter->key() != val) {
+ iter = iter->next();
+ }
+
+ return iter;
+ }
+private:
+ node<H>* _head;
+};
+
+template<class H>
+class graph {
+public:
+
+private:
+ int _len, _nodes, _edges;
+ H **_k;
+ list<int> **_adj;
+ int _index(H val) {
+ for(int i = 0; i < _nodes; ++i)
+ if(*_k[i] == val) return i;
+
+ return -1;
+ }
+public:
+ graph(int len) : _len{len}, _nodes{0}, _edges{0} {
+ _k = new H*[len];
+ _adj = new list<int>*[_len];
+ for(int i = 0; i < _len; ++i) {
+ _k[i] = nullptr;
+ _adj[i] = new list<int>{};
+ }
+ }
+
+ graph<H>* add_node(H k) {
+ if(_nodes == _len) return this;
+ if(_index(k) >= 0) return this; // node is already there
+
+ _k[_nodes++] = new H(k);
+
+ return this;
+ }
+
+ graph<H>* add_edge(H x, H y) {
+ int i = _index(x);
+ int j = _index(y);
+ if(i < 0 || j < 0) return this;
+
+ if(!_adj[i]->search(j)) {
+ _adj[i]->push(j);
+ _edges++;
+ }
+
+ return this;
+ }
+
+ void print() {
+ for(int i = 0; i < _nodes; ++i) {
+ cout << "(" << i << ", " << *_k[i] << "): ";
+ for(auto const& j : _adj[i]->as_vector())
+ cout << "(" << j << ", " << *_k[j] << "), ";
+ cout << '\n';
+ }
+ }
+};
+
+
+int main() {
+ graph<string>* g = new graph<string>(5);
+ g->add_node("hello")->add_node("greg")->add_node("yes");
+ g->add_node("nop")->add_node("ok");
+ g->add_edge("hello", "ok");
+ g->add_edge("ok", "yes")->add_edge("yes", "ok")->add_edge("yes", "yes");
+ g->add_edge("yes", "nop");
+ g->print();
+
+ delete g;
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/data_structures/graph_stl.cc b/1_anno/Programmazione_2/data_structures/graph_stl.cc
new file mode 100644
index 0000000..5381747
--- /dev/null
+++ b/1_anno/Programmazione_2/data_structures/graph_stl.cc
@@ -0,0 +1,221 @@
+#include<iostream>
+#include<vector>
+#include<algorithm>
+#include<queue>
+#include<stack>
+#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;
+ }
+ }
+ void ssc() {
+ dfs();
+ cout << endl << endl;
+ auto gr = _transpose();
+ bool* visited = new bool[_nodes];
+ for(int i = 0; i < _nodes; ++i)
+ visited[i] = false;
+
+ while(!_stack.empty()) {
+ int v = _stack.top();
+ _stack.pop();
+ if(!visited[v]) {
+ gr->dfsvisit(v, visited);
+ cout << endl;
+ }
+ }
+ delete[] visited;
+ }
+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() {
+ graph<int>* g = new graph<int>{5};
+ for(auto const& i : {0, 1, 2, 3, 4})
+ g->add_node(i);
+ g->add_edge(1, 0);
+ g->add_edge(2, 1);
+ g->add_edge(0, 2);
+ g->add_edge(0, 3);
+ g->add_edge(3, 4);
+ //g->print();
+ cout << endl;
+ //g->top_sort();
+ g->ssc();
+ cout << endl;
+ //g->bfs(0);
+ delete g;
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/data_structures/list.cc b/1_anno/Programmazione_2/data_structures/list.cc
new file mode 100644
index 0000000..8ddcbf9
--- /dev/null
+++ b/1_anno/Programmazione_2/data_structures/list.cc
@@ -0,0 +1,164 @@
+#include<iostream>
+
+using namespace std;
+
+template<typename T>
+struct node {
+ T value;
+ node* next;
+};
+
+
+template<typename T>
+class list {
+public:
+ list() : _head{nullptr} {}
+
+ ~list() {
+ while(_head) {
+ node<T>* tmp = _head->next;
+ delete tmp;
+ _head = tmp;
+ }
+ }
+
+ list* push_front(T val) {
+ _head = new node<T>{val, _head};
+
+ return this;
+ }
+
+ list* push_back(T val) {
+ if(!_head) return this->push_front(val);
+
+ node<T>* iter = _head;
+ while(iter->next) {
+ iter = iter->next;
+ }
+ iter->next = new node<T>{val, nullptr};
+
+ return this;
+ }
+
+ list* push_after_value(T val, T newval) {
+ node<T>* iter = _search(val);
+ if(iter)
+ iter->next = new node<T>{newval, iter->next};
+
+ return this;
+ }
+
+ list* push_before_value(T val, T newval) {
+ node<T>* elem = _search(val);
+ if(!elem) return this;
+
+ node<T>* iter = _head;
+
+ if(iter->value == val)
+ return this->push_front(newval);
+
+ while(iter->next != elem)
+ iter = iter->next;
+
+ iter->next = new node<T>{newval, iter->next};
+
+ return this;
+ }
+
+ list* pop(int val) {
+ node<T>* elem = _search(val);
+ if(!elem) return this;
+
+ node<T>* iter = _head;
+ if(iter == elem) return this->pop_front();
+
+ while(iter->next != elem)
+ iter = iter->next;
+
+ node<T>* temp = iter->next;
+ iter->next = iter->next->next;
+ delete temp;
+
+ return this;
+ }
+
+ list* pop_front() {
+ if(!_head)
+ return this;
+
+ node<T>* elem = _head;
+ _head = _head->next;
+ delete elem;
+
+ return this;
+ }
+
+ list* pop_back() {
+ if(!_head)
+ return this;
+
+ node<T>* iter = _head;
+
+ while(iter->next && iter->next->next) {
+ iter = iter->next;
+ }
+
+ if(!iter->next) {
+ delete iter;
+ _head = nullptr;
+ } else if(iter->next->next) {
+ delete iter->next->next;
+ } else {
+ delete iter->next;
+ }
+
+ iter->next = nullptr;
+
+ return this;
+ }
+
+ void print() {
+ node<T>* iter = _head;
+ while(iter) {
+ cout << iter->value << ' ';
+ iter = iter->next;
+ }
+ }
+private:
+ node<T>* _search(T value) {
+ node<T>* iter = _head;
+ while(iter && iter->value != value)
+ iter = iter->next;
+
+ return iter;
+ }
+
+ node<T>* _head;
+};
+
+int main() {
+ list<int>* l = new list<int>{};
+ l->push_front(2)->push_front(1);
+ l->print(); cout << endl;
+ l->push_back(5);
+ l->print(); cout << endl;
+ l->push_back(10)->push_back(15);
+ l->print(); cout << endl;
+ l->push_after_value(5, 6);
+ l->print(); cout << endl;
+ l->push_before_value(5, 4);
+ l->print(); cout << endl;
+ l->push_before_value(4, 3);
+ l->print(); cout << endl;
+ l->pop_back();
+ l->print(); cout << endl;
+ l->pop_front();
+ l->print(); cout << endl;
+ l->push_front(1);
+ l->print(); cout << endl;
+ l->pop(1);
+ l->print(); cout << endl;
+
+ delete l;
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/data_structures/list_double.cc b/1_anno/Programmazione_2/data_structures/list_double.cc
new file mode 100644
index 0000000..fa0af26
--- /dev/null
+++ b/1_anno/Programmazione_2/data_structures/list_double.cc
@@ -0,0 +1,182 @@
+#include<iostream>
+
+using namespace std;
+
+template<typename T>
+struct node {
+ T value;
+ node* prev;
+ node* next;
+};
+
+
+template<typename T>
+class list {
+public:
+ list() : _head{nullptr} {}
+
+ ~list() {
+ while(_head != nullptr) {
+ node<T>* tmp = _head->next;
+ delete tmp;
+ _head = tmp;
+ }
+ }
+
+ list* push_front(T val) {
+ if(!_head) {
+ _head = new node<T>{val, nullptr, nullptr};
+ } else {
+ _head = new node<T>{val, nullptr, _head};
+ _head->next->prev = _head;
+ }
+
+ return this;
+ }
+
+ list* push_back(T val) {
+ if(!_head) return this->push_front(val);
+
+ node<T>* iter = _head;
+ while(iter->next) {
+ iter = iter->next;
+ }
+ iter->next = new node<T>{val, iter, nullptr};
+
+ return this;
+ }
+
+ list* push_after_value(T val, T newval) {
+ node<T>* elem = _search(val);
+ if(elem) {
+ node<T>* nod = new node<T>{newval, elem, elem->next};
+ elem->next = nod;
+ nod->next->prev = nod;
+ }
+
+ return this;
+ }
+
+ list* push_before_value(T val, T newval) {
+ node<T>* elem = _search(val);
+ if(!elem) return this;
+
+ node<T>* iter = _head;
+
+ if(iter->value == val)
+ return this->push_front(newval);
+
+ while(iter->next != elem)
+ iter = iter->next;
+
+ node<T>* nod = new node<T>{newval, iter, iter->next};
+ iter->next = nod;
+ nod->next->prev = nod;
+
+ return this;
+ }
+
+ list* pop(int val) {
+ node<T>* elem = _search(val);
+ if(!elem) return this;
+
+ if(elem == _head) return this->pop_front();
+
+ node<T>* iter = elem->prev;
+ node<T>* temp = iter->next;
+ iter->next = iter->next->next;
+ iter->next->prev = iter;
+ delete temp;
+
+ return this;
+ }
+
+ list* pop_front() {
+ if(!_head)
+ return this;
+
+ node<T>* elem = _head;
+ _head = _head->next;
+ _head->prev = nullptr;
+ delete elem;
+
+ return this;
+ }
+
+ list* pop_back() {
+ if(!_head)
+ return this;
+
+ node<T>* iter = _last()->prev;
+
+ if(iter->next == nullptr) {
+ delete iter;
+ _head = nullptr;
+ } else if(iter->next->next) {
+ delete iter->next->next;
+ } else {
+ delete iter->next;
+ }
+
+ iter->next = nullptr;
+
+ return this;
+ }
+
+ void print() {
+ node<T>* iter = _head;
+ while(iter) {
+ cout << iter->value << ' ';
+ cout << "[[ " << (iter->prev!=nullptr ? iter->prev->value : -1) << ", ";
+ cout << (iter->next!=nullptr ? iter->next->value : -1) << " ]], ";
+ iter = iter->next;
+ }
+ }
+private:
+ node<T>* _last() {
+ node<T>* iter = _head;
+ while(iter->next) {
+ iter = iter->next;
+ }
+
+ return iter;
+ }
+
+ node<T>* _search(T value) {
+ node<T>* iter = _head;
+ while(iter && iter->value != value)
+ iter = iter->next;
+
+ return iter;
+ }
+
+ node<T>* _head;
+};
+
+int main() {
+ list<int>* l = new list<int>{};
+ l->push_front(2)->push_front(1);
+ l->print(); cout << endl;
+ l->push_back(5);
+ l->print(); cout << endl;
+ l->push_back(10)->push_back(15);
+ l->print(); cout << endl;
+ l->push_after_value(5, 6);
+ l->print(); cout << endl;
+ l->push_after_value(5, 7);
+ l->print(); cout << endl;
+ l->push_before_value(5, 4);
+ l->print(); cout << endl;
+ l->push_before_value(5, 3);
+ l->print(); cout << endl;
+ l->pop_back();
+ l->print(); cout << endl;
+ l->pop_front();
+ l->print(); cout << endl;
+ l->pop(2);
+ l->print(); cout << endl;
+
+ delete l;
+
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/data_structures/matrix-graph.cc b/1_anno/Programmazione_2/data_structures/matrix-graph.cc
new file mode 100644
index 0000000..a644ec1
--- /dev/null
+++ b/1_anno/Programmazione_2/data_structures/matrix-graph.cc
@@ -0,0 +1,81 @@
+#include<iostream>
+#include<list>
+
+using namespace std;
+
+template<class H>
+class matrix_graph {
+public:
+ ~matrix_graph() {
+ delete[] _m;
+ delete[] _k;
+ }
+ matrix_graph(int len) : _len{len}, _nodes{0}, _edges{0} {
+ _m = new int*[len];
+ _k = new H*[len];
+ for(int i = 0; i < len; ++i) {
+ _m[i] = new int[len];
+ _k[i] = nullptr;
+ for(int j = 0; j < len; ++j)
+ _m[i][j] = 0;
+ }
+ }
+
+ matrix_graph<H>* add_node(H k) {
+ if(_len == _nodes) return this; // no more space for new nodes
+ if(_index(k) > -1) return this; // nodes already exists
+
+ _k[_nodes++] = new H(k);
+
+ return this;
+ }
+
+ matrix_graph<H>* add_edge(H x, H y) {
+ int i = _index(x);
+ int j = _index(y);
+ if(i < 0 || j < 0) return this;
+ if(!_m[i][j]) {
+ _m[i][j] = 1;
+ _edges++;
+ }
+ return this;
+ }
+ void print() {
+ for(int i = 0; i < _len; ++i) {
+ cout << i << ' ' << *_k[i] << ": ";
+ for(int j = 0; j < _len; ++j) {
+ if(_m[i][j])
+ cout << *_k[j] << ' ';
+ }
+ cout << '\n';
+ }
+ cout << endl;
+ for(int i = 0; i < _len; ++i) {
+ for(int j = 0; j < _len; ++j) {
+ cout << _m[i][j] << ' ';
+ }
+ cout << '\n';
+ }
+ }
+private:
+ int _len, _nodes, _edges;
+ int** _m;
+ H** _k;
+ int _index(H x) {
+ for(int i = 0; i < _nodes; ++i)
+ if(*_k[i] == x) return i;
+ return -1;
+ }
+};
+
+int main() {
+ matrix_graph<string>* g = new matrix_graph<string>(5);
+ g->add_node("hello")->add_node("greg")->add_node("yes");
+ g->add_node("nop")->add_node("ok");
+ g->add_edge("hello", "ok");
+ g->add_edge("ok", "yes")->add_edge("yes", "ok")->add_edge("yes", "yes");
+ g->add_edge("yes", "nop");
+ g->print();
+ delete g;
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/data_structures/queue.cc b/1_anno/Programmazione_2/data_structures/queue.cc
new file mode 100644
index 0000000..8398459
--- /dev/null
+++ b/1_anno/Programmazione_2/data_structures/queue.cc
@@ -0,0 +1,72 @@
+#include<iostream>
+
+using namespace std;
+
+template<typename T>
+struct node {
+ T value;
+ node<T>* next;
+};
+
+template<class T>
+class queue {
+public:
+ queue() : _head{nullptr} {}
+
+ ~queue() {
+ auto iter = _head;
+ while(iter) {
+ delete iter;
+ iter = iter->next;
+ }
+ }
+
+ queue<T>* enqueue(T val) {
+
+ if(!_head) {
+ _head = new node<T>{val, nullptr};
+ _tail = _head;
+ } else {
+ _tail->next = new node<T>{val, nullptr};
+ _tail = _tail->next;
+ }
+
+ return this;
+ }
+
+ node<T>* dequeue() {
+ if(!_head) return nullptr;
+ auto iter = _head;
+ delete _head;
+ _head = iter->next;
+ return iter;
+ }
+
+ void print() {
+ auto iter = _head;
+ while(iter) {
+ cout << iter->value << ' ';
+ iter = iter->next;
+ }
+ cout << endl;
+ }
+private:
+ node<T>* _head;
+ node<T>* _tail;
+};
+
+int main() {
+ queue<int>* q = new queue<int>();
+
+ q->dequeue();
+ q->enqueue(4)->enqueue(2)->enqueue(8);
+ q->print();
+ auto e = q->dequeue();
+ if(e)
+ cout << e->value << endl;
+ q->enqueue(1);
+ q->print();
+
+ delete q;
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/data_structures/queue_w_array.cc b/1_anno/Programmazione_2/data_structures/queue_w_array.cc
new file mode 100644
index 0000000..fb92d68
--- /dev/null
+++ b/1_anno/Programmazione_2/data_structures/queue_w_array.cc
@@ -0,0 +1,66 @@
+#include<iostream>
+
+using namespace std;
+
+template<class H>
+class queue {
+public:
+ queue(int n) : _size{n}, _counter{0}, _head{0}, _tail{0} {
+ _arr = new H[n];
+ }
+ ~queue() {
+ delete _arr;
+ }
+ bool is_empty() {
+ return _counter == 0;
+ }
+ bool is_full() {
+ return _counter == _size;
+ }
+
+ queue<H>* enqueue(H x) {
+ if(!is_full()) {
+ _arr[_tail] = x;
+ if(_tail == _size-1)
+ _tail = 0;
+ else
+ ++_tail;
+ _counter++;
+ }
+
+ return this;
+ }
+ H dequeue() {
+ if(is_empty()) return -1;
+ H x = _arr[_head];
+
+ if(_head == _size-1)
+ _head = 0;
+ else
+ ++_head;
+
+ _counter--;
+ return x;
+ }
+private:
+ H* _arr;
+ int _size;
+ short _counter;
+ short _head;
+ short _tail;
+};
+
+int main() {
+ queue<int>* q = new queue<int>{4};
+ q->enqueue(5)->enqueue(13)->enqueue(3);
+ cout << q->dequeue() << '\n';
+ q->enqueue(4)->enqueue(6)->enqueue(7);
+ q->dequeue();
+ q->enqueue(7);
+
+ for(int i = 0; i < 6; ++i) {
+ cout << q->dequeue() << ' ';
+ }
+ delete q;
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/data_structures/stack.cc b/1_anno/Programmazione_2/data_structures/stack.cc
new file mode 100644
index 0000000..ffff780
--- /dev/null
+++ b/1_anno/Programmazione_2/data_structures/stack.cc
@@ -0,0 +1,70 @@
+#include<iostream>
+
+using namespace std;
+
+template<typename T>
+struct node {
+ T value;
+ node<T>* next;
+};
+
+template<class T>
+class stack {
+public:
+ stack() : _head{nullptr} {}
+
+ ~stack() {
+ auto iter = _head;
+ while(iter) {
+ delete iter;
+ iter = iter->next;
+ }
+ }
+
+ stack<T>* push(T val) {
+
+ if(!_head) {
+ _head = new node<T>{val, nullptr};
+ } else {
+ _head = new node<T>{val, _head};
+ }
+
+ return this;
+ }
+
+ node<T>* pop() {
+ if(!_head) return nullptr;
+ node<T>* elem = _head;
+ delete _head;
+ _head = elem->next;
+
+ return elem;
+ }
+
+ void print() {
+ auto iter = _head;
+ while(iter) {
+ cout << iter->value << ' ';
+ iter = iter->next;
+ }
+ cout << endl;
+ }
+private:
+ node<T>* _head;
+};
+
+int main() {
+ stack<int>* s = new stack<int>();
+
+ s->pop();
+ s->push(4)->push(2)->push(8);
+ s->print();
+ auto e = s->pop();
+ if(e)
+ cout << e->value << endl;
+ s->push(1);
+ s->print();
+
+ delete s;
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/data_structures/stack_w_array.cc b/1_anno/Programmazione_2/data_structures/stack_w_array.cc
new file mode 100644
index 0000000..c20db90
--- /dev/null
+++ b/1_anno/Programmazione_2/data_structures/stack_w_array.cc
@@ -0,0 +1,50 @@
+#include<iostream>
+
+using namespace std;
+
+template<class H>
+class stack {
+public:
+ stack(int n) : _size{n}, _top{-1} {
+ _arr = new H[n];
+ }
+ ~stack() {
+ delete _arr;
+ }
+ bool is_empty() {
+ return _top == -1;
+ }
+ bool is_full() {
+ return _top == _size-1;
+ }
+ stack<H>* push(H x) {
+ if(!is_full()) {
+ _arr[++_top] = x;
+ }
+ return this;
+ }
+ H pop() {
+ if(is_empty())
+ return -1;
+ _top--;
+ return _arr[_top+1];
+ }
+private:
+ int _size;
+ H* _arr;
+ short _top;
+};
+
+int main() {
+ stack<int>* s = new stack<int>{7};
+
+ s->push(15)->push(6)->push(2)->push(9)->push(17)->push(3);
+ cout << s->pop() << '\n';
+ s->push(18)->push(19)->push(12);
+
+ for(int i = 0; i < 7; ++i)
+ cout << s->pop() << ' ';
+
+ delete s;
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/data_structures/top-sort.cc b/1_anno/Programmazione_2/data_structures/top-sort.cc
new file mode 100644
index 0000000..7441ee9
--- /dev/null
+++ b/1_anno/Programmazione_2/data_structures/top-sort.cc
@@ -0,0 +1,212 @@
+
+#include<iostream>
+#include<vector>
+#include<queue>
+#define W -1
+#define G 0
+#define B 1
+
+using namespace std;
+
+template<class H>
+class node {
+public:
+ explicit node(H key, node<H>* next) : _key{key}, _next(next) {}
+ const H& key() const { return _key; }
+ H& key() { return _key; }
+ const node<H>*& next() const { return _next; }
+ node<H>*& next() { return _next; }
+private:
+ H _key;
+ node<H>* _next;
+};
+
+template<class H>
+class list {
+public:
+ list() : _head{nullptr} {}
+ ~list() {
+ while(_head) {
+ auto tmp = _head;
+ _head = _head->next();
+ delete tmp;
+ }
+ }
+ list<H>* push(H val) {
+ auto iter = _head;
+ while(iter && iter->next())
+ iter = iter->next();
+
+ if(!iter)
+ _head = new node<H>{val, nullptr};
+ else
+ iter->next() = new node<H>{val, nullptr};
+
+ return this;
+ }
+ void print() {
+ auto iter = _head;
+ while(iter) {
+ cout << iter->key() << ' ';
+ iter = iter->next();
+ }
+ }
+ vector<H> as_vector() {
+ vector<H> v;
+ auto iter = _head;
+ while(iter) {
+ v.push_back(iter->key());
+ iter = iter->next();
+ }
+ return v;
+ }
+ node<H>* search(H val) {
+ auto iter = _head;
+ while(iter && iter->key() != val) {
+ iter = iter->next();
+ }
+
+ return iter;
+ }
+private:
+ node<H>* _head;
+};
+
+template<class H>
+class graph {
+private:
+ int _len, _nodes, _edges;
+ int* _parents;
+ int* _radixes;
+ int* _distances;
+ int* _finishes;
+ int* _colors;
+ int _time;
+ int _current;
+ H** _k; // it works like a dictionary, it saves the keys
+ list<int>** _adj;
+ int _index(H val) {
+ for(int i = 0; i < _nodes; ++i)
+ if(*_k[i] == val) return i;
+
+ return -1;
+ }
+ bool _dfsvisit(int u) {
+ bool cycle = false;
+ _colors[u] = G;
+ _distances[u] = _time++;
+ _radixes[u] = _current;
+ for(auto const& v : _adj[u]->as_vector()) {
+ if(_colors[v] == W) {
+ _parents[v] = u;
+ _dfsvisit(v);
+ } else if(_colors[v] == G) {
+ cycle = true;
+ }
+ }
+ _colors[u] = B;
+ _finishes[u] = _time++;
+ return cycle;
+ }
+public:
+ graph(int len) : _len{len}, _nodes{0}, _edges{0} {
+ _k = new H*[len];
+ _adj = new list<int>*[_len];
+ _parents = new int[_len];
+ _radixes = new int[_len];
+ _distances = new int[_len];
+ _finishes = new int[_len];
+ _colors = new int[_len];
+ for(int i = 0; i < _len; ++i) {
+ _k[i] = nullptr;
+ _adj[i] = new list<int>{};
+ }
+ }
+
+ graph<H>* add_node(H k) {
+ if(_nodes == _len) return this;
+ if(_index(k) >= 0) return this; // node is already there
+
+ _k[_nodes++] = new H(k);
+
+ return this;
+ }
+
+
+ bool dfs() {
+ bool cycle = 0;
+ _time = 0;
+ for(int i = 0; i < _nodes; ++i) {
+ _colors[i] = W;
+ _parents[i] = -1;
+ }
+
+ for(int i = 0; i < _nodes; ++i) {
+ if(_colors[i] == W) {
+ _current = i;
+ cycle |= _dfsvisit(i);
+ }
+ }
+ for(int i = 0; i < _nodes; ++i) {
+ cout << *_k[i] << "(" << _distances[i]+1 << ',' << _finishes[i]+1 << ")" << endl;
+ }
+ return cycle;
+ }
+
+ void top_sort() {
+ bool cycle = dfs();
+ if(cycle) {
+ cerr << "Grafo ciclico\n";
+ return;
+ }
+ vector<int> s(_finishes, _finishes+_nodes);
+ sort(begin(s), end(s));
+ for(auto const& i : s) {
+ cout << "(" << i << ", " << _finishes[i] << ") ";
+ }
+ }
+
+ graph<H>* add_edge(H x, H y) {
+ int i = _index(x);
+ int j = _index(y);
+ if(i < 0 || j < 0) return this;
+
+ if(!_adj[i]->search(j)) {
+ _adj[i]->push(j);
+ _edges++;
+ }
+
+ return this;
+ }
+
+ void print() {
+ for(int i = 0; i < _nodes; ++i) {
+ cout << "(" << i << ", " << *_k[i] << "): ";
+ for(auto const& j : _adj[i]->as_vector())
+ cout << "(" << j << ", " << *_k[j] << "), ";
+ cout << '\n';
+ }
+ }
+};
+
+
+int main() {
+ graph<char>* g = new graph<char>(6);
+ g->add_node('u')->add_node('v')->add_node('x')->add_node('y');
+ g->add_node('w')->add_node('z');
+ g->add_edge('u', 'v');
+ g->add_edge('u', 'x');
+ g->add_edge('x', 'v');
+ g->add_edge('y', 'x');
+ g->add_edge('v', 'y');
+ g->add_edge('w', 'y');
+ g->add_edge('w', 'z');
+ g->add_edge('z', 'z');
+
+ g->print();
+ g->dfs();
+ g->top_sort();
+
+ delete g;
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/exercises/carattere-maggiore.cc b/1_anno/Programmazione_2/exercises/carattere-maggiore.cc
new file mode 100644
index 0000000..2e89fcd
--- /dev/null
+++ b/1_anno/Programmazione_2/exercises/carattere-maggiore.cc
@@ -0,0 +1,40 @@
+#include<iostream>
+#include<map>
+#include<fstream>
+
+using namespace std;
+
+
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int ts = 0; ts < 100; ++ts) {
+ string line;
+ getline(in, line);
+ map<char, int> chs;
+ for(auto const& c : line) {
+ if(c == ' ') continue;
+ if(chs.find(c) != chs.end())
+ chs[c]++;
+ else
+ chs[c] = 1;
+ }
+ int n = 0;
+ char c = 'a';
+ for(auto const& i : chs) {
+ if(i.second >= n) {
+ if(i.first >= c) {
+ n = i.second;
+ c = i.first;
+ }
+ }
+ }
+ out << c << ' ' << n << endl;
+ }
+
+ out.close();
+ in.close();
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/exercises/dequeue.cc b/1_anno/Programmazione_2/exercises/dequeue.cc
new file mode 100644
index 0000000..4b012c4
--- /dev/null
+++ b/1_anno/Programmazione_2/exercises/dequeue.cc
@@ -0,0 +1,137 @@
+
+#include<iostream>
+#include<fstream>
+
+using namespace std;
+
+template<class T>
+class node {
+public:
+ node(T key, node<T>* next) : _key{key}, _next{next} {}
+ node(T key) : _key{key}, _next{nullptr} {}
+ const T& key() const { return _key; }
+ T& key() { return _key; }
+ const node<T>*& next() const { return _next; }
+ node<T>*& next() { return _next; }
+private:
+ T _key;
+ node<T>* _next;
+};
+
+template<class T>
+class Coda {
+public:
+ Coda() : _head{nullptr}, _tail{nullptr} {}
+ ~Coda() {
+
+ }
+ Coda<T>* enqueue(T val) {
+ if(!_head) {
+ _head = new node<T>{val, nullptr};
+ _tail = _head;
+ } else {
+ _tail->next() = new node<T>{val, nullptr};
+ _tail = _tail->next();
+ }
+
+ return this;
+ }
+ node<T>* dequeue() {
+ if(!_head) return nullptr;
+ node<T>* elem = _head;
+ delete _head;
+ _head = elem->next();
+
+ return elem;
+ }
+
+ bool is_empty() { return _head == nullptr; }
+private:
+ node<T>* _head;
+ node<T>* _tail;
+};
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int ts = 0; ts < 100; ++ts) {
+ string t;
+ int n;
+ in >> t;
+ switch(t.at(0)) {
+ case 'b': {
+ Coda<bool>* queue = new Coda<bool>{};
+ in >> n;
+ string s;
+ for(int i = 0; i < n; ++i) {
+ in >> s;
+ if(s.at(0) == 'i') {
+ queue->enqueue(s.at(1) - '0');
+ } else {
+ queue->dequeue();
+ }
+ }
+ while(!queue->is_empty())
+ out << queue->dequeue()->key() << ' ';
+ out << endl;
+ break;
+ }
+ case 'd': {
+ Coda<double>* queue = new Coda<double>{};
+ in >> n;
+ string s;
+ for(int i = 0; i < n; ++i) {
+ in >> s;
+ if(s.at(0) == 'i') {
+ queue->enqueue(stod(s.substr(1, s.length()-1)));
+ } else {
+ queue->dequeue();
+ }
+ }
+ while(!queue->is_empty())
+ out << queue->dequeue()->key() << ' ';
+ out << endl;
+ break;
+ }
+ case 'c': {
+ Coda<char>* queue = new Coda<char>{};
+ in >> n;
+ string s;
+ for(int i = 0; i < n; ++i) {
+ in >> s;
+ if(s.at(0) == 'i') {
+ queue->enqueue(s.at(1));
+ } else {
+ queue->dequeue();
+ }
+ }
+ while(!queue->is_empty())
+ out << queue->dequeue()->key() << ' ';
+ out << endl;
+ break;
+ }
+ case 'i': {
+ Coda<int>* queue = new Coda<int>{};
+ in >> n;
+ string s;
+ for(int i = 0; i < n; ++i) {
+ in >> s;
+ if(s.at(0) == 'i') {
+ queue->enqueue(stoi(s.substr(1, s.length()-1)));
+ } else {
+ queue->dequeue();
+ }
+ }
+ while(!queue->is_empty())
+ out << queue->dequeue()->key() << ' ';
+ out << endl;
+ break;
+ }
+ }
+ }
+ in.close();
+ out.close();
+ return 0;
+}
+
diff --git a/1_anno/Programmazione_2/exercises/doppioni.cc b/1_anno/Programmazione_2/exercises/doppioni.cc
new file mode 100644
index 0000000..fdd3e88
--- /dev/null
+++ b/1_anno/Programmazione_2/exercises/doppioni.cc
@@ -0,0 +1,77 @@
+#include<iostream>
+#include<fstream>
+
+using namespace std;
+
+template<class T>
+class node {
+public:
+ node(T key, node* parent, node* right, node* left) : _key{key}, _parent{parent}, _right{right}, _left{left} {}
+ T& key() { return _key; }
+ const T& key() const { return _key; }
+ node<T>*& parent() { return _parent; }
+ const node<T>*& parent() const { return _parent; }
+ node<T>*& right() { return _right; }
+ const node<T>*& right() const { return _right; }
+ node<T>*& left() { return _left; }
+ const node<T>*& left() const { return _left; }
+private:
+ T _key;
+ node<T>* _parent;
+ node<T>* _right;
+ node<T>* _left;
+};
+
+class bst {
+public:
+ bst() : _duplicates{0}, _root{nullptr} {}
+ bst* add(int val) {
+ node<int>* iter = _root;
+ node<int>* prev = nullptr;
+ while(iter) {
+ prev = iter;
+ if(iter->key() == val) {
+ _duplicates++;
+ return this;
+ }
+
+ if(iter->key() > val)
+ iter = iter->right();
+ else
+ iter = iter->left();
+ }
+
+ node<int>* nodus = new node<int>{val, prev, nullptr, nullptr};
+ if(!prev)
+ _root = nodus;
+ else if(prev->key() > val)
+ prev->right() = nodus;
+ else
+ prev->left() = nodus;
+
+ return this;
+ }
+ const int& duplicates() const { return _duplicates; }
+private:
+ int _duplicates;
+ node<int>* _root;
+};
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+ for(int ts = 0; ts < 100; ++ts) {
+ bst* b = new bst{};
+ int n;
+ in >> n;
+ int e;
+ for(int i = 0; i < n; ++i) {
+ in >> e;
+ b->add(e);
+ }
+ out << b->duplicates() << endl;
+ }
+ in.close();
+ out.close();
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/exercises/estremi-uguali.cc b/1_anno/Programmazione_2/exercises/estremi-uguali.cc
new file mode 100644
index 0000000..63ac019
--- /dev/null
+++ b/1_anno/Programmazione_2/exercises/estremi-uguali.cc
@@ -0,0 +1,32 @@
+#include<iostream>
+#include<string>
+#include<fstream>
+
+using namespace std;
+
+int result(string s) {
+ if(s.at(0) == s.at(s.length()-1))
+ return 1;
+
+ return 0;
+}
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int ts = 0; ts < 100; ++ts) {
+ int _;
+ string s;
+ int size{};
+ for(int i = 0; i < 3; ++i) {
+ in >> _ >> s;
+ size += result(s);
+ }
+ out << size << '\n';
+ }
+
+ in.close();
+ out.close();
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/exercises/even-length.cc b/1_anno/Programmazione_2/exercises/even-length.cc
new file mode 100644
index 0000000..2d3d6a4
--- /dev/null
+++ b/1_anno/Programmazione_2/exercises/even-length.cc
@@ -0,0 +1,27 @@
+#include<iostream>
+#include<string>
+#include<fstream>
+
+using namespace std;
+
+string result(string s) {
+ if(s.length() % 2 == 0)
+ return s;
+
+ return s.substr(0, s.length()-1);
+}
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int ts = 0; ts < 100; ++ts) {
+ string s;
+ in >> s;
+ out << result(s) << '\n';
+ }
+
+ in.close();
+ out.close();
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/exercises/exam_08_10_14.cc b/1_anno/Programmazione_2/exercises/exam_08_10_14.cc
new file mode 100644
index 0000000..c9c33be
--- /dev/null
+++ b/1_anno/Programmazione_2/exercises/exam_08_10_14.cc
@@ -0,0 +1,202 @@
+#include<iostream>
+
+using namespace std;
+
+template<class H> class MultiBST {
+ virtual MultiBST<H>* ins(H x) = 0;
+ virtual int multiplicity(H x) = 0;
+ virtual void inorder() = 0;
+};
+
+template<class H>
+class node {
+public:
+ node(H val) : _key{val}, _parent{nullptr}, _left{nullptr}, _right{nullptr}, _rk{1} {}
+ H& key() { return _key; }
+ const H& key() const { return _key; }
+ node<H>*& parent() { return _parent; }
+ const node<H>*& parent() const { return _parent; }
+ node<H>*& left() { return _left; }
+ const node<H>*& left() const { return _left; }
+ node<H>*& right() { return _right; }
+ const node<H>*& right() const { return _right; }
+ int& rk() { return _rk; }
+ const int& rk() const { return _rk; }
+private:
+ H _key;
+ node<H>* _parent;
+ node<H>* _left;
+ node<H>* _right;
+ int _rk;
+};
+
+template<class H>
+class MyMultiBST : public MultiBST<H> {
+public:
+ MyMultiBST() : _root{nullptr} {}
+ node<H>*& root() { return _root; }
+ const node<H>*& root() const { return _root; }
+ int multiplicity(H x) {
+ auto elem = _search(x);
+ if(elem)
+ return elem->rk();
+ return 0;
+ }
+ MyMultiBST<H>* ins(H x) {
+ auto iter = _search(x);
+ if(iter) {
+ iter->rk() = iter->rk()+1;
+ } else {
+ iter = _root;
+ node<H>* y{nullptr};
+
+ while(iter) {
+ y = iter;
+ if(iter->key() > x)
+ iter = iter->left();
+ else
+ iter = iter->right();
+ }
+
+ node<H>* nodus = new node<H>{x};
+ nodus->parent() = y;
+ if(!y) {
+ _root = nodus;
+ } else if(y->key() > x) {
+ y->left() = nodus;
+ } else {
+ y->right() = nodus;
+ }
+ }
+
+ return this;
+ }
+ void inorder() {
+ _inorder(_root);
+ }
+ MyMultiBST<H>* del(H x) {
+ node<H>* y;
+ node<H>* z = _search(x);
+
+ if(!z) return this;
+
+ if(z->rk() > 1) {
+ z->rk() = z->rk()-1;
+ } else {
+ if(!z->left()) {
+ _transplant(z, z->right());
+ } else if(!z->right()) {
+ _transplant(z, z->left());
+ } else {
+ y = _min(z->right());
+ if(y->parent() != z) {
+ _transplant(y, y->right());
+ y->right() = z->right();
+ y->right()->parent() = y;
+ }
+ _transplant(z, y);
+ y->left() = z->left();
+ y->left()->parent() = y;
+ delete z;
+ }
+ }
+
+ return this;
+ }
+ node<H>* predecessor(H x) {
+ auto iter = _search(x);
+ if(!iter) return nullptr;
+ if(iter->left())
+ return _max(iter->left());
+
+ auto y = iter->parent();
+ while(y && iter == y->left()) {
+ iter = y;
+ y = y->parent();
+ }
+
+ return y;
+ }
+ int rank(H x) {
+ auto iter = predecessor(x);
+ int sum{1};
+ while(iter) {
+ sum+=iter->rk();
+ iter = predecessor(iter->key());
+ }
+ return sum;
+ }
+private:
+ void _transplant(node<H>* u, node<H>* v) {
+ if(!u->parent()) _root = v;
+ else if(u == u->parent()->left())
+ u->parent()->left() = v;
+ else
+ u->parent()->right() = v;
+
+ if(v)
+ v->parent() = u->parent();
+ }
+ node<H>* _max(node<H>* x) {
+ if(!x) return nullptr;
+
+ auto iter = x;
+ while(iter->right()) {
+ iter = iter->right();
+ }
+
+ return iter;
+ }
+ node<H>* _min(node<H>* x) {
+ if(!x) return nullptr;
+
+ auto iter = x;
+ while(iter->left()) {
+ iter = iter->left();
+ }
+
+ return iter;
+ }
+ void _inorder(node<H>* p) {
+ if(p) {
+ _inorder(p->left());
+ for(int i = 0; i < p->rk(); ++i) {
+ cout << p->key() << ' ';
+ }
+ _inorder(p->right());
+ }
+ }
+ node<H>* _search(H val) {
+ auto iter = _root;
+ while(iter && iter->key() != val) {
+ if(iter->key() > val)
+ iter = iter->left();
+ else
+ iter = iter->right();
+ }
+
+ return iter;
+ }
+ node<H>* _root;
+};
+
+int main() {
+ MyMultiBST<int>* t = new MyMultiBST<int>{};
+
+ for(auto const& i : {10, 7, 7, 23, 30, 4, 1, 5, 9, 5, 1, 7, 1, 9})
+ t->ins(i);
+
+ t->inorder();
+ cout << '\n';
+ for(auto const& i : {5, 7, 17})
+ cout << i << ": " << t->multiplicity(i) << endl;
+
+ for(auto const& i : {7, 4, 23, 7, 7})
+ t->del(i);
+ t->inorder();
+ cout << '\n';
+ for(auto const& i: {5, 9, 30})
+ cout << t->rank(i) << ' ';
+ delete t;
+ return 0;
+}
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
new file mode 100644
index 0000000..4f08a74
--- /dev/null
+++ b/1_anno/Programmazione_2/exercises/exam_20_07_20/ex1.cpp
@@ -0,0 +1,39 @@
+#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
new file mode 100644
index 0000000..aed25e4
--- /dev/null
+++ b/1_anno/Programmazione_2/exercises/exam_20_07_20/ex2.cpp
@@ -0,0 +1,63 @@
+#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
new file mode 100644
index 0000000..71f9c65
--- /dev/null
+++ b/1_anno/Programmazione_2/exercises/exam_20_07_20/ex3.cpp
@@ -0,0 +1,284 @@
+#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
new file mode 100644
index 0000000..e234363
--- /dev/null
+++ b/1_anno/Programmazione_2/exercises/exam_20_07_20/ex4.cpp
@@ -0,0 +1,293 @@
+#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
new file mode 100644
index 0000000..dd8fc98
--- /dev/null
+++ b/1_anno/Programmazione_2/exercises/exam_20_07_20/ex5.cpp
@@ -0,0 +1,285 @@
+#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;
+}
+
diff --git a/1_anno/Programmazione_2/exercises/inizia-con.cc b/1_anno/Programmazione_2/exercises/inizia-con.cc
new file mode 100644
index 0000000..97f0c39
--- /dev/null
+++ b/1_anno/Programmazione_2/exercises/inizia-con.cc
@@ -0,0 +1,33 @@
+#include<iostream>
+#include<string>
+#include<fstream>
+
+using namespace std;
+
+string result(string s, char c) {
+ if(s.at(0) == c)
+ return s + ' ';
+
+ return "";
+}
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int ts = 0; ts < 100; ++ts) {
+ int _;
+ string s;
+ char c;
+ in >> c;
+ for(int i = 0; i < 3; ++i) {
+ in >> _ >> s;
+ out << result(s, c);
+ }
+ out << '\n';
+ }
+
+ in.close();
+ out.close();
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/exercises/inserimento-coda.cc b/1_anno/Programmazione_2/exercises/inserimento-coda.cc
new file mode 100644
index 0000000..6775ca2
--- /dev/null
+++ b/1_anno/Programmazione_2/exercises/inserimento-coda.cc
@@ -0,0 +1,119 @@
+#include<iostream>
+#include<fstream>
+
+using namespace std;
+
+template<class T>
+class node {
+public:
+ node(T key, node<T>* next) : _key{key}, _next{next} {}
+ node(T key) : _key{key}, _next{nullptr} {}
+ const T& key() const { return _key; }
+ T& key() { return _key; }
+ const node<T>*& next() const { return _next; }
+ node<T>*& next() { return _next; }
+private:
+ T _key;
+ node<T>* _next;
+};
+
+template<class T>
+class Coda {
+public:
+ Coda() : _head{nullptr}, _tail{nullptr} {}
+ ~Coda() {
+
+ }
+ Coda<T>* enqueue(T val) {
+ if(!_head) {
+ _head = new node<T>{val, nullptr};
+ _tail = _head;
+ } else {
+ _tail->next() = new node<T>{val, nullptr};
+ _tail = _tail->next();
+ }
+
+ return this;
+ }
+ node<T>* pop() {
+ if(!_head) return nullptr;
+ node<T>* elem = _head;
+ delete _head;
+ _head = elem->next();
+
+ return elem;
+ }
+
+ bool is_empty() { return _head == nullptr; }
+private:
+ node<T>* _head;
+ node<T>* _tail;
+};
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int ts = 0; ts < 100; ++ts) {
+ string t;
+ int n;
+ in >> t;
+ switch(t.at(0)) {
+ case 'b': {
+ Coda<bool>* queue = new Coda<bool>{};
+ in >> n;
+ bool e;
+ for(int i = 0; i < n; ++i) {
+ in >> e;
+ queue->enqueue(e);
+ }
+ while(!queue->is_empty())
+ out << queue->pop()->key() << ' ';
+ out << endl;
+ break;
+ }
+ case 'd': {
+ Coda<double>* queue = new Coda<double>{};
+ in >> n;
+ double e;
+ for(int i = 0; i < n; ++i) {
+ in >> e;
+ queue->enqueue(e);
+ }
+ while(!queue->is_empty())
+ out << queue->pop()->key() << ' ';
+ out << endl;
+ break;
+ }
+ case 'c': {
+ Coda<char>* queue = new Coda<char>{};
+ in >> n;
+ char e;
+ for(int i = 0; i < n; ++i) {
+ in >> e;
+ queue->enqueue(e);
+ }
+ while(!queue->is_empty())
+ out << queue->pop()->key() << ' ';
+ out << endl;
+ break;
+ }
+ case 'i': {
+ Coda<int>* queue = new Coda<int>{};
+ in >> n;
+ int e;
+ for(int i = 0; i < n; ++i) {
+ in >> e;
+ queue->enqueue(e);
+ }
+ while(!queue->is_empty())
+ out << queue->pop()->key() << ' ';
+ out << endl;
+ break;
+ }
+ }
+ }
+ in.close();
+ out.close();
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/exercises/inserimento-pila.cc b/1_anno/Programmazione_2/exercises/inserimento-pila.cc
new file mode 100644
index 0000000..0dbe99b
--- /dev/null
+++ b/1_anno/Programmazione_2/exercises/inserimento-pila.cc
@@ -0,0 +1,116 @@
+#include<iostream>
+#include<fstream>
+
+using namespace std;
+
+template<class T>
+class node {
+public:
+ node(T key, node<T>* next) : _key{key}, _next{next} {}
+ node(T key) : _key{key}, _next{nullptr} {}
+ const T& key() const { return _key; }
+ T& key() { return _key; }
+ const node<T>*& next() const { return _next; }
+ node<T>*& next() { return _next; }
+private:
+ T _key;
+ node<T>* _next;
+};
+
+template<class T>
+class Pila {
+public:
+ Pila() : _head{nullptr}{}
+ ~Pila() {
+
+ }
+ Pila<T>* push(T val) {
+ if(!_head) {
+ _head = new node<T>{val, nullptr};
+ } else {
+ _head = new node<T>{val, _head};
+ }
+
+ return this;
+ }
+ node<T>* pop() {
+ if(!_head) return nullptr;
+ node<T>* elem = _head;
+ delete _head;
+ _head = elem->next();
+
+ return elem;
+ }
+
+ bool is_empty() { return _head == nullptr; }
+private:
+ node<T>* _head;
+};
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int ts = 0; ts < 100; ++ts) {
+ string t;
+ int n;
+ in >> t;
+ switch(t.at(0)) {
+ case 'b': {
+ Pila<bool>* stack = new Pila<bool>{};
+ in >> n;
+ bool e;
+ for(int i = 0; i < n; ++i) {
+ in >> e;
+ stack->push(e);
+ }
+ while(!stack->is_empty())
+ out << stack->pop()->key() << ' ';
+ out << endl;
+ break;
+ }
+ case 'd': {
+ Pila<double>* stack = new Pila<double>{};
+ in >> n;
+ double e;
+ for(int i = 0; i < n; ++i) {
+ in >> e;
+ stack->push(e);
+ }
+ while(!stack->is_empty())
+ out << stack->pop()->key() << ' ';
+ out << endl;
+ break;
+ }
+ case 'c': {
+ Pila<char>* stack = new Pila<char>{};
+ in >> n;
+ char e;
+ for(int i = 0; i < n; ++i) {
+ in >> e;
+ stack->push(e);
+ }
+ while(!stack->is_empty())
+ out << stack->pop()->key() << ' ';
+ out << endl;
+ break;
+ }
+ case 'i': {
+ Pila<int>* stack = new Pila<int>{};
+ in >> n;
+ int e;
+ for(int i = 0; i < n; ++i) {
+ in >> e;
+ stack->push(e);
+ }
+ while(!stack->is_empty())
+ out << stack->pop()->key() << ' ';
+ out << endl;
+ break;
+ }
+ }
+ }
+ in.close();
+ out.close();
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/exercises/matrice-adj.cc b/1_anno/Programmazione_2/exercises/matrice-adj.cc
new file mode 100644
index 0000000..7830f97
--- /dev/null
+++ b/1_anno/Programmazione_2/exercises/matrice-adj.cc
@@ -0,0 +1,151 @@
+#include<iostream>
+#include<vector>
+#include<fstream>
+#include<sstream>
+
+using namespace std;
+
+template<class H>
+class matrix_graph {
+public:
+ ~matrix_graph() {
+ delete[] _m;
+ delete[] _k;
+ }
+ matrix_graph(int len) : _len{len}, _nodes{0}, _edges{0} {
+ _m = new int*[len];
+ _k = new H*[len];
+ for(int i = 0; i < len; ++i) {
+ _m[i] = new int[len];
+ _k[i] = nullptr;
+ for(int j = 0; j < len; ++j)
+ _m[i][j] = 0;
+ }
+ }
+
+ matrix_graph<H>* add_node(H k) {
+ if(_len == _nodes) return this; // no more space for new nodes
+ if(_index(k) > -1) return this; // nodes already exists
+
+ _k[_nodes++] = new H(k);
+
+ return this;
+ }
+
+ matrix_graph<H>* add_edge(H x, H y) {
+ int i = _index(x);
+ int j = _index(y);
+ if(i < 0 || j < 0) return this;
+ if(!_m[i][j]) {
+ _m[i][j] = 1;
+ _edges++;
+ }
+ return this;
+ }
+ vector<vector<H>> print() {
+ vector<vector<H>> v;
+ for(int i = 0; i < _len; ++i) {
+ v.push_back(vector<H>{*_k[i]});
+ vector<H> temp;
+ for(int j = 0; j < _len; ++j) {
+ if(_m[i][j]) {
+ temp.push_back(*_k[j]);
+ }
+ }
+ sort(begin(temp), end(temp));
+ for(auto const& j : temp)
+ v[i].push_back(j);
+ }
+
+ sort(begin(v), end(v));
+ return v;
+ }
+private:
+ int _len, _nodes, _edges;
+ int** _m;
+ H** _k;
+ int _index(H x) {
+ for(int i = 0; i < _nodes; ++i)
+ if(*_k[i] == x) return i;
+ return -1;
+ }
+};
+
+template<class H>
+string result(vector<vector<H>> v) {
+ string s{""};
+ ostringstream ss;
+ for(auto const& i : v) {
+ s += "(";
+ for(auto const& j : i) {
+ ss << j;
+ s+= ss.str();
+ s+= ' ';
+ ss.str(""); ss.clear();
+ }
+ s.pop_back();
+ s += ") ";
+ }
+ return s;
+}
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+ for(int ts = 0; ts < 100; ++ts) {
+ int n, m;
+ in >> n >> m;
+ string t;
+ in >> t;
+ if(t == "int") {
+ matrix_graph<int>* g = new matrix_graph<int>(n);
+ int x,y;
+ for(int i = 0; i < n; ++i) {
+ in >> x;
+ g->add_node(x);
+ }
+ char ex;
+ for(int i = 0; i < m; ++i) {
+ in >> ex >> x >> y >> ex;
+ g->add_edge(x, y);
+ }
+ auto v = g->print();
+ out << result(v) << endl;
+ delete g;
+ } else if(t == "double") {
+ matrix_graph<double>* g = new matrix_graph<double>(n);
+ double x,y;
+ for(int i = 0; i < n; ++i) {
+ in >> x;
+ g->add_node(x);
+ }
+ char ex;
+ for(int i = 0; i < m; ++i) {
+ in >> ex >> x >> y >> ex;
+ g->add_edge(x, y);
+ }
+ auto v = g->print();
+ out << result(v) << endl;
+ delete g;
+ } else {
+ matrix_graph<char>* g = new matrix_graph<char>(n);
+ char x,y;
+ for(int i = 0; i < n; ++i) {
+ in >> x;
+ g->add_node(x);
+ }
+ char ex;
+ for(int i = 0; i < m; ++i) {
+ in >> ex >> x >> y >> ex;
+ g->add_edge(x, y);
+ }
+
+ auto v = g->print();
+ out << result(v) << endl;
+ delete g;
+ }
+ }
+ in.close();
+ out.close();
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/exercises/minore.cc b/1_anno/Programmazione_2/exercises/minore.cc
new file mode 100644
index 0000000..677da76
--- /dev/null
+++ b/1_anno/Programmazione_2/exercises/minore.cc
@@ -0,0 +1,27 @@
+#include<iostream>
+#include<string>
+#include<fstream>
+
+using namespace std;
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int ts = 0; ts < 100; ++ts) {
+ string s;
+ in >> s;
+ int minor = stoi(s);
+ for(in >> s; s != "STOP"; in >> s) {
+ int si = stoi(s);
+ if(si < minor)
+ minor = si;
+ }
+
+ out << minor << '\n';
+ }
+
+ in.close();
+ out.close();
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/exercises/pop-stack.cc b/1_anno/Programmazione_2/exercises/pop-stack.cc
new file mode 100644
index 0000000..3739450
--- /dev/null
+++ b/1_anno/Programmazione_2/exercises/pop-stack.cc
@@ -0,0 +1,132 @@
+#include<iostream>
+#include<fstream>
+
+using namespace std;
+
+template<class T>
+class node {
+public:
+ node(T key, node<T>* next) : _key{key}, _next{next} {}
+ node(T key) : _key{key}, _next{nullptr} {}
+ const T& key() const { return _key; }
+ T& key() { return _key; }
+ const node<T>*& next() const { return _next; }
+ node<T>*& next() { return _next; }
+private:
+ T _key;
+ node<T>* _next;
+};
+
+template<class T>
+class Pila {
+public:
+ Pila() : _head{nullptr}{}
+ ~Pila() {
+
+ }
+ Pila<T>* push(T val) {
+ if(!_head) {
+ _head = new node<T>{val, nullptr};
+ } else {
+ _head = new node<T>{val, _head};
+ }
+
+ return this;
+ }
+ node<T>* pop() {
+ if(!_head) return nullptr;
+ node<T>* elem = _head;
+ delete _head;
+ _head = elem->next();
+
+ return elem;
+ }
+
+ bool is_empty() { return _head == nullptr; }
+private:
+ node<T>* _head;
+};
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int ts = 0; ts < 100; ++ts) {
+ string t;
+ int n;
+ in >> t;
+ switch(t.at(0)) {
+ case 'b': {
+ Pila<bool>* stack = new Pila<bool>{};
+ in >> n;
+ string s;
+ for(int i = 0; i < n; ++i) {
+ in >> s;
+ if(s.at(0) == 'i') {
+ stack->push(s.at(1) - '0');
+ } else {
+ stack->pop();
+ }
+ }
+ while(!stack->is_empty())
+ out << stack->pop()->key() << ' ';
+ out << endl;
+ break;
+ }
+ case 'd': {
+ Pila<double>* stack = new Pila<double>{};
+ in >> n;
+ string s;
+ for(int i = 0; i < n; ++i) {
+ in >> s;
+ if(s.at(0) == 'i') {
+ stack->push(stod(s.substr(1, s.length()-1)));
+ } else {
+ stack->pop();
+ }
+ }
+ while(!stack->is_empty())
+ out << stack->pop()->key() << ' ';
+ out << endl;
+ break;
+ }
+ case 'c': {
+ Pila<char>* stack = new Pila<char>{};
+ in >> n;
+ string s;
+ for(int i = 0; i < n; ++i) {
+ in >> s;
+ if(s.at(0) == 'i') {
+ stack->push(s.at(1));
+ } else {
+ stack->pop();
+ }
+ }
+ while(!stack->is_empty())
+ out << stack->pop()->key() << ' ';
+ out << endl;
+ break;
+ }
+ case 'i': {
+ Pila<int>* stack = new Pila<int>{};
+ in >> n;
+ string s;
+ for(int i = 0; i < n; ++i) {
+ in >> s;
+ if(s.at(0) == 'i') {
+ stack->push(stoi(s.substr(1, s.length()-1)));
+ } else {
+ stack->pop();
+ }
+ }
+ while(!stack->is_empty())
+ out << stack->pop()->key() << ' ';
+ out << endl;
+ break;
+ }
+ }
+ }
+ in.close();
+ out.close();
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/exercises/prima-maiuscola.cc b/1_anno/Programmazione_2/exercises/prima-maiuscola.cc
new file mode 100644
index 0000000..6273219
--- /dev/null
+++ b/1_anno/Programmazione_2/exercises/prima-maiuscola.cc
@@ -0,0 +1,30 @@
+#include<iostream>
+#include<string>
+#include<fstream>
+
+using namespace std;
+
+string result(string s) {
+ s.at(0) = toupper(s.at(0));
+
+ return s;
+}
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int ts = 0; ts < 100; ++ts) {
+ int _;
+ string s;
+ for(int i = 0; i < 3; ++i) {
+ in >> _ >> s;
+ out << result(s) << ' ';
+ }
+ out << '\n';
+ }
+
+ in.close();
+ out.close();
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/exercises/ripetute.cc b/1_anno/Programmazione_2/exercises/ripetute.cc
new file mode 100644
index 0000000..23d151a
--- /dev/null
+++ b/1_anno/Programmazione_2/exercises/ripetute.cc
@@ -0,0 +1,20 @@
+#include<iostream>
+#include<string>
+#include<fstream>
+
+using namespace std;
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int ts = 0; ts < 100; ++ts) {
+ string s;
+ in >> s;
+ out << s+s << '\n';
+ }
+
+ in.close();
+ out.close();
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/exercises/sol-ripetute.cc b/1_anno/Programmazione_2/exercises/sol-ripetute.cc
new file mode 100644
index 0000000..1518d76
--- /dev/null
+++ b/1_anno/Programmazione_2/exercises/sol-ripetute.cc
@@ -0,0 +1,25 @@
+#include<iostream>
+#include<string>
+#include<fstream>
+
+using namespace std;
+
+string result(string s) {
+ int half = s.length()/2;
+ return s.substr(0, half);
+}
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int ts = 0; ts < 100; ++ts) {
+ string s;
+ in >> s;
+ out << result(s) << '\n';
+ }
+
+ in.close();
+ out.close();
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/exercises/sottosequenza.cc b/1_anno/Programmazione_2/exercises/sottosequenza.cc
new file mode 100644
index 0000000..1d7c481
--- /dev/null
+++ b/1_anno/Programmazione_2/exercises/sottosequenza.cc
@@ -0,0 +1,26 @@
+#include<iostream>
+#include<fstream>
+
+using namespace std;
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int ts = 0; ts < 100; ++ts) {
+ int n; string s;
+ in >> n >> s;
+ string tm;
+ for(int i = 0; i < n; ++i) {
+ in >> tm;
+ if(tm.find(s) != string::npos)
+ out << tm << ' ';
+ }
+ out << '\n';
+ }
+
+ in.close();
+ out.close();
+
+ return 0;
+}
diff --git a/1_anno/Programmazione_2/exercises/stringa-inversa.cc b/1_anno/Programmazione_2/exercises/stringa-inversa.cc
new file mode 100644
index 0000000..5c37718
--- /dev/null
+++ b/1_anno/Programmazione_2/exercises/stringa-inversa.cc
@@ -0,0 +1,26 @@
+#include<iostream>
+#include<fstream>
+
+using namespace std;
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int ts = 0; ts < 100; ++ts) {
+ int n;
+ in >> n;
+ for(int i = 0; i < 3; ++i) {
+ string s;
+ in >> s;
+ for(int j = s.length()-1; j > -1; --j) {
+ out << s.at(j);
+ }
+ out << ' ';
+ }
+ out << endl;
+ }
+
+ out.close();
+ in.close();
+}