From d2edbc38cac8da52f58c5cd3da6c0c625fa05736 Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Sat, 6 Feb 2021 19:56:36 +0100 Subject: conf: rename --- Year_1/Programming_2/algorithms/binarysearch.cc | 33 +++ Year_1/Programming_2/algorithms/cbrt.cc | 37 +++ Year_1/Programming_2/algorithms/insertionsort.cc | 42 +++ Year_1/Programming_2/algorithms/log.cc | 25 ++ Year_1/Programming_2/algorithms/mergesort.cc | 52 ++++ Year_1/Programming_2/algorithms/pow.cc | 25 ++ Year_1/Programming_2/algorithms/quicksort.cc | 38 +++ Year_1/Programming_2/algorithms/selectionsort.cc | 46 ++++ Year_1/Programming_2/algorithms/sqrt.cc | 46 ++++ Year_1/Programming_2/coding_contest/dolcetti.cpp | 51 ++++ Year_1/Programming_2/coding_contest/gita.cpp | 46 ++++ Year_1/Programming_2/coding_contest/gribaudo.cpp | 47 ++++ Year_1/Programming_2/coding_contest/gualtieri.cpp | 46 ++++ Year_1/Programming_2/coding_contest/ladri.cpp | 53 ++++ Year_1/Programming_2/coding_contest/pizzini.cpp | 48 ++++ Year_1/Programming_2/coding_contest/scheletri.cpp | 56 ++++ Year_1/Programming_2/coding_contest/stazioni.cpp | 82 ++++++ Year_1/Programming_2/coding_contest/tastevin.cpp | 38 +++ .../coding_contest/tastevin_paths.cpp | 67 +++++ Year_1/Programming_2/data_structures/bfs.cc | 186 +++++++++++++ Year_1/Programming_2/data_structures/bst.cc | 225 ++++++++++++++++ .../data_structures/circle_double_list.cc | 185 +++++++++++++ .../Programming_2/data_structures/circle_list.cc | 189 +++++++++++++ Year_1/Programming_2/data_structures/dfs.cc | 191 ++++++++++++++ Year_1/Programming_2/data_structures/graph.cc | 164 ++++++++++++ Year_1/Programming_2/data_structures/graph_stl.cc | 221 ++++++++++++++++ Year_1/Programming_2/data_structures/list.cc | 164 ++++++++++++ .../Programming_2/data_structures/list_double.cc | 182 +++++++++++++ .../Programming_2/data_structures/matrix-graph.cc | 81 ++++++ Year_1/Programming_2/data_structures/queue.cc | 72 +++++ .../Programming_2/data_structures/queue_w_array.cc | 66 +++++ Year_1/Programming_2/data_structures/stack.cc | 70 +++++ .../Programming_2/data_structures/stack_w_array.cc | 50 ++++ Year_1/Programming_2/data_structures/top-sort.cc | 212 +++++++++++++++ .../Programming_2/exercises/carattere-maggiore.cc | 40 +++ Year_1/Programming_2/exercises/dequeue.cc | 137 ++++++++++ Year_1/Programming_2/exercises/doppioni.cc | 77 ++++++ Year_1/Programming_2/exercises/estremi-uguali.cc | 32 +++ Year_1/Programming_2/exercises/even-length.cc | 27 ++ Year_1/Programming_2/exercises/exam_08_10_14.cc | 202 ++++++++++++++ .../Programming_2/exercises/exam_20_07_20/ex1.cpp | 39 +++ .../Programming_2/exercises/exam_20_07_20/ex2.cpp | 63 +++++ .../Programming_2/exercises/exam_20_07_20/ex3.cpp | 284 ++++++++++++++++++++ .../Programming_2/exercises/exam_20_07_20/ex4.cpp | 293 +++++++++++++++++++++ .../Programming_2/exercises/exam_20_07_20/ex5.cpp | 285 ++++++++++++++++++++ Year_1/Programming_2/exercises/inizia-con.cc | 33 +++ Year_1/Programming_2/exercises/inserimento-coda.cc | 119 +++++++++ Year_1/Programming_2/exercises/inserimento-pila.cc | 116 ++++++++ Year_1/Programming_2/exercises/matrice-adj.cc | 151 +++++++++++ Year_1/Programming_2/exercises/minore.cc | 27 ++ Year_1/Programming_2/exercises/pop-stack.cc | 132 ++++++++++ Year_1/Programming_2/exercises/prima-maiuscola.cc | 30 +++ Year_1/Programming_2/exercises/ripetute.cc | 20 ++ Year_1/Programming_2/exercises/sol-ripetute.cc | 25 ++ Year_1/Programming_2/exercises/sottosequenza.cc | 26 ++ Year_1/Programming_2/exercises/stringa-inversa.cc | 26 ++ 56 files changed, 5320 insertions(+) create mode 100644 Year_1/Programming_2/algorithms/binarysearch.cc create mode 100644 Year_1/Programming_2/algorithms/cbrt.cc create mode 100644 Year_1/Programming_2/algorithms/insertionsort.cc create mode 100644 Year_1/Programming_2/algorithms/log.cc create mode 100644 Year_1/Programming_2/algorithms/mergesort.cc create mode 100644 Year_1/Programming_2/algorithms/pow.cc create mode 100644 Year_1/Programming_2/algorithms/quicksort.cc create mode 100644 Year_1/Programming_2/algorithms/selectionsort.cc create mode 100644 Year_1/Programming_2/algorithms/sqrt.cc create mode 100644 Year_1/Programming_2/coding_contest/dolcetti.cpp create mode 100644 Year_1/Programming_2/coding_contest/gita.cpp create mode 100644 Year_1/Programming_2/coding_contest/gribaudo.cpp create mode 100644 Year_1/Programming_2/coding_contest/gualtieri.cpp create mode 100644 Year_1/Programming_2/coding_contest/ladri.cpp create mode 100644 Year_1/Programming_2/coding_contest/pizzini.cpp create mode 100644 Year_1/Programming_2/coding_contest/scheletri.cpp create mode 100644 Year_1/Programming_2/coding_contest/stazioni.cpp create mode 100644 Year_1/Programming_2/coding_contest/tastevin.cpp create mode 100644 Year_1/Programming_2/coding_contest/tastevin_paths.cpp create mode 100644 Year_1/Programming_2/data_structures/bfs.cc create mode 100644 Year_1/Programming_2/data_structures/bst.cc create mode 100644 Year_1/Programming_2/data_structures/circle_double_list.cc create mode 100644 Year_1/Programming_2/data_structures/circle_list.cc create mode 100644 Year_1/Programming_2/data_structures/dfs.cc create mode 100644 Year_1/Programming_2/data_structures/graph.cc create mode 100644 Year_1/Programming_2/data_structures/graph_stl.cc create mode 100644 Year_1/Programming_2/data_structures/list.cc create mode 100644 Year_1/Programming_2/data_structures/list_double.cc create mode 100644 Year_1/Programming_2/data_structures/matrix-graph.cc create mode 100644 Year_1/Programming_2/data_structures/queue.cc create mode 100644 Year_1/Programming_2/data_structures/queue_w_array.cc create mode 100644 Year_1/Programming_2/data_structures/stack.cc create mode 100644 Year_1/Programming_2/data_structures/stack_w_array.cc create mode 100644 Year_1/Programming_2/data_structures/top-sort.cc create mode 100644 Year_1/Programming_2/exercises/carattere-maggiore.cc create mode 100644 Year_1/Programming_2/exercises/dequeue.cc create mode 100644 Year_1/Programming_2/exercises/doppioni.cc create mode 100644 Year_1/Programming_2/exercises/estremi-uguali.cc create mode 100644 Year_1/Programming_2/exercises/even-length.cc create mode 100644 Year_1/Programming_2/exercises/exam_08_10_14.cc create mode 100644 Year_1/Programming_2/exercises/exam_20_07_20/ex1.cpp create mode 100644 Year_1/Programming_2/exercises/exam_20_07_20/ex2.cpp create mode 100644 Year_1/Programming_2/exercises/exam_20_07_20/ex3.cpp create mode 100644 Year_1/Programming_2/exercises/exam_20_07_20/ex4.cpp create mode 100644 Year_1/Programming_2/exercises/exam_20_07_20/ex5.cpp create mode 100644 Year_1/Programming_2/exercises/inizia-con.cc create mode 100644 Year_1/Programming_2/exercises/inserimento-coda.cc create mode 100644 Year_1/Programming_2/exercises/inserimento-pila.cc create mode 100644 Year_1/Programming_2/exercises/matrice-adj.cc create mode 100644 Year_1/Programming_2/exercises/minore.cc create mode 100644 Year_1/Programming_2/exercises/pop-stack.cc create mode 100644 Year_1/Programming_2/exercises/prima-maiuscola.cc create mode 100644 Year_1/Programming_2/exercises/ripetute.cc create mode 100644 Year_1/Programming_2/exercises/sol-ripetute.cc create mode 100644 Year_1/Programming_2/exercises/sottosequenza.cc create mode 100644 Year_1/Programming_2/exercises/stringa-inversa.cc (limited to 'Year_1/Programming_2') diff --git a/Year_1/Programming_2/algorithms/binarysearch.cc b/Year_1/Programming_2/algorithms/binarysearch.cc new file mode 100644 index 0000000..c9b4cd7 --- /dev/null +++ b/Year_1/Programming_2/algorithms/binarysearch.cc @@ -0,0 +1,33 @@ +#include + +using namespace std; + +bool bs(int a[], int i, int j, int x) { + if(j 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 << ' '< + +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/Year_1/Programming_2/algorithms/insertionsort.cc b/Year_1/Programming_2/algorithms/insertionsort.cc new file mode 100644 index 0000000..9b309d6 --- /dev/null +++ b/Year_1/Programming_2/algorithms/insertionsort.cc @@ -0,0 +1,42 @@ +#include + +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/Year_1/Programming_2/algorithms/log.cc b/Year_1/Programming_2/algorithms/log.cc new file mode 100644 index 0000000..1e49a2e --- /dev/null +++ b/Year_1/Programming_2/algorithms/log.cc @@ -0,0 +1,25 @@ +#include + +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/Year_1/Programming_2/algorithms/mergesort.cc b/Year_1/Programming_2/algorithms/mergesort.cc new file mode 100644 index 0000000..68d28cb --- /dev/null +++ b/Year_1/Programming_2/algorithms/mergesort.cc @@ -0,0 +1,52 @@ +#include + +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/Year_1/Programming_2/algorithms/pow.cc b/Year_1/Programming_2/algorithms/pow.cc new file mode 100644 index 0000000..16cf419 --- /dev/null +++ b/Year_1/Programming_2/algorithms/pow.cc @@ -0,0 +1,25 @@ +#include + +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/Year_1/Programming_2/algorithms/quicksort.cc b/Year_1/Programming_2/algorithms/quicksort.cc new file mode 100644 index 0000000..795bd7b --- /dev/null +++ b/Year_1/Programming_2/algorithms/quicksort.cc @@ -0,0 +1,38 @@ +#include + +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/Year_1/Programming_2/algorithms/selectionsort.cc b/Year_1/Programming_2/algorithms/selectionsort.cc new file mode 100644 index 0000000..57dcc17 --- /dev/null +++ b/Year_1/Programming_2/algorithms/selectionsort.cc @@ -0,0 +1,46 @@ +#include +#include + +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/Year_1/Programming_2/algorithms/sqrt.cc b/Year_1/Programming_2/algorithms/sqrt.cc new file mode 100644 index 0000000..aa6b032 --- /dev/null +++ b/Year_1/Programming_2/algorithms/sqrt.cc @@ -0,0 +1,46 @@ +#include + +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/Year_1/Programming_2/coding_contest/dolcetti.cpp b/Year_1/Programming_2/coding_contest/dolcetti.cpp new file mode 100644 index 0000000..c3409a4 --- /dev/null +++ b/Year_1/Programming_2/coding_contest/dolcetti.cpp @@ -0,0 +1,51 @@ +#include +#include +#include +#include + +using namespace std; + +int main() { + using tii = tuple; + ifstream in("input.txt"); + ofstream out("output.txt"); + + for(int ts = 0; ts < 100; ++ts) { + int N; + in >> N; + + priority_queue> 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/Year_1/Programming_2/coding_contest/gita.cpp b/Year_1/Programming_2/coding_contest/gita.cpp new file mode 100644 index 0000000..cbb4910 --- /dev/null +++ b/Year_1/Programming_2/coding_contest/gita.cpp @@ -0,0 +1,46 @@ +#include +#include +#include +#include + +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> 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> 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/Year_1/Programming_2/coding_contest/gribaudo.cpp b/Year_1/Programming_2/coding_contest/gribaudo.cpp new file mode 100644 index 0000000..39d0e42 --- /dev/null +++ b/Year_1/Programming_2/coding_contest/gribaudo.cpp @@ -0,0 +1,47 @@ +#include +#include +#include + +using namespace std; + +int maxpath(vector>& 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> triangle; + + for(int i = 0; i < N; ++i) { + int e; + triangle.push_back(vector{}); + 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/Year_1/Programming_2/coding_contest/gualtieri.cpp b/Year_1/Programming_2/coding_contest/gualtieri.cpp new file mode 100644 index 0000000..f8a0ecf --- /dev/null +++ b/Year_1/Programming_2/coding_contest/gualtieri.cpp @@ -0,0 +1,46 @@ +#include +#include +#include + +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 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 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/Year_1/Programming_2/coding_contest/ladri.cpp b/Year_1/Programming_2/coding_contest/ladri.cpp new file mode 100644 index 0000000..04e8e65 --- /dev/null +++ b/Year_1/Programming_2/coding_contest/ladri.cpp @@ -0,0 +1,53 @@ +#include +#include +#include + +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 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/Year_1/Programming_2/coding_contest/pizzini.cpp b/Year_1/Programming_2/coding_contest/pizzini.cpp new file mode 100644 index 0000000..4fcb4ab --- /dev/null +++ b/Year_1/Programming_2/coding_contest/pizzini.cpp @@ -0,0 +1,48 @@ +#include +#include +#include + +using namespace std; + +void get_fib(vector &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 fib {1, 2}; + get_fib(fib, N); + vector 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/Year_1/Programming_2/coding_contest/scheletri.cpp b/Year_1/Programming_2/coding_contest/scheletri.cpp new file mode 100644 index 0000000..2389d25 --- /dev/null +++ b/Year_1/Programming_2/coding_contest/scheletri.cpp @@ -0,0 +1,56 @@ +#include +#include +#include +#include + +using namespace std; + +int find_i(int index, vector cms) { + for(int i = index; i < cms.size(); ++i) { + if(cms.at(i) != 0) + return i; + } + + return 0; +} + +int find_j(int index, vector 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 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/Year_1/Programming_2/coding_contest/stazioni.cpp b/Year_1/Programming_2/coding_contest/stazioni.cpp new file mode 100644 index 0000000..29ede44 --- /dev/null +++ b/Year_1/Programming_2/coding_contest/stazioni.cpp @@ -0,0 +1,82 @@ +#include +#include +#include +#include + +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 st; + vector> paths; + vector> paths2; + vector> 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{}); + 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 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/Year_1/Programming_2/coding_contest/tastevin.cpp b/Year_1/Programming_2/coding_contest/tastevin.cpp new file mode 100644 index 0000000..301ebcf --- /dev/null +++ b/Year_1/Programming_2/coding_contest/tastevin.cpp @@ -0,0 +1,38 @@ +#include +#include +#include +#include + +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 arr(N); + for(int i = 0; i < N; ++i) { + in >> arr.at(i); + } + + vector 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/Year_1/Programming_2/coding_contest/tastevin_paths.cpp b/Year_1/Programming_2/coding_contest/tastevin_paths.cpp new file mode 100644 index 0000000..eb7da54 --- /dev/null +++ b/Year_1/Programming_2/coding_contest/tastevin_paths.cpp @@ -0,0 +1,67 @@ +// It prints all possible paths + +#include +#include +#include + +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 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 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/Year_1/Programming_2/data_structures/bfs.cc b/Year_1/Programming_2/data_structures/bfs.cc new file mode 100644 index 0000000..2b4efbd --- /dev/null +++ b/Year_1/Programming_2/data_structures/bfs.cc @@ -0,0 +1,186 @@ +#include +#include +#include +#define W -1 +#define G 0 +#define B 1 + +using namespace std; + +template +class node { +public: + explicit node(H key, node* next) : _key{key}, _next(next) {} + const H& key() const { return _key; } + H& key() { return _key; } + const node*& next() const { return _next; } + node*& next() { return _next; } +private: + H _key; + node* _next; +}; + +template +class list { +public: + list() : _head{nullptr} {} + ~list() { + while(_head) { + auto tmp = _head; + _head = _head->next(); + delete tmp; + } + } + list* push(H val) { + auto iter = _head; + while(iter && iter->next()) + iter = iter->next(); + + if(!iter) + _head = new node{val, nullptr}; + else + iter->next() = new node{val, nullptr}; + + return this; + } + void print() { + auto iter = _head; + while(iter) { + cout << iter->key() << ' '; + iter = iter->next(); + } + } + vector as_vector() { + vector v; + auto iter = _head; + while(iter) { + v.push_back(iter->key()); + iter = iter->next(); + } + return v; + } + node* search(H val) { + auto iter = _head; + while(iter && iter->key() != val) { + iter = iter->next(); + } + + return iter; + } +private: + node* _head; +}; + +template +class graph { +public: + +private: + int _len, _nodes, _edges; + int* _parents; + int* _distances; + H** _k; // it works like a dictionary, it saves the keys + list** _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*[_len]; + _parents = new int[_len]; + _distances = new int[_len]; + for(int i = 0; i < _len; ++i) { + _k[i] = nullptr; + _adj[i] = new list{}; + } + } + + graph* 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 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* 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* g = new graph(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/Year_1/Programming_2/data_structures/bst.cc b/Year_1/Programming_2/data_structures/bst.cc new file mode 100644 index 0000000..9223e04 --- /dev/null +++ b/Year_1/Programming_2/data_structures/bst.cc @@ -0,0 +1,225 @@ +#include + +using namespace std; + +template +struct node { + T key; + node* prev; + node* right; + node* left; +}; + +template +class bst { +public: + bst() : root{nullptr} {} + + ~bst() { + // TODO + } + + bst* insert(initializer_list&& list) { + for(auto const& i : list) + insert(i); + + return this; + } + + bst* insert(T k) { + node* nodus = new node{k, nullptr, nullptr, nullptr}; + node* iter = root; + node* 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* remove(initializer_list&& list) { + for(auto const& i : list) + remove(i); + + return this; + } + + bst* remove(T k) { + node* nodus = search(k); + if(!nodus) return this; + + if(!nodus->left) { + _transplant(nodus, nodus->right); + } else if(!nodus->right) { + _transplant(nodus, nodus->left); + } else { + node* 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* min() { + return _min(root); + } + + node* min(node* nodus) { + return _min(nodus); + } + + node* max() { + return _max(root); + } + + node* max(node* nodus) { + return _max(nodus); + } + + node* search(T k) { + node* iter = root; + while(iter && iter->key != k) + iter = (iter->key > k) ? iter->left : iter->right; + + return iter; + } + + node* successor(T k) { + node* nodus = search(k); + if(!nodus) return nullptr; + + if(nodus->right) + return min(nodus->right); + + node* prev = nodus->prev; + while(prev && nodus == prev->right) { + nodus = prev; + prev = prev->prev; + } + + return prev; + + } + node* predecessor(T k) { + node* nodus = search(k); + if(!nodus) return nullptr; + + if(nodus->left) + return max(nodus->left); + + node* prev = nodus->prev; + while(prev && nodus == prev->left) { + nodus = prev; + prev = prev->prev; + } + + return prev; + } + + friend ostream& operator<<(ostream& os, bst* tree) { + tree->_preorder(os, tree->root); + return os; + } +private: + void _transplant(node* u, node* 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* _min(node* root) { + node* iter = root; + while(iter && iter->left) + iter = iter->left; + + return iter; + } + + node* _max(node* root) { + node* iter = root; + while(iter && iter->right) + iter = iter->right; + + return iter; + } + + void _inorder(ostream& os, node* root) { + if(root) { + _inorder(os, root->left); + os << root->key << ' '; + _inorder(os, root->right); + } + } + + void _preorder(ostream& os, node* root) { + if(root) { + os << root->key << ' '; + _inorder(os, root->left); + _inorder(os, root->right); + } + } + + void _postorder(ostream& os, node* root) { + if(root) { + _inorder(os, root->left); + _inorder(os, root->right); + os << root->key << ' '; + } + } + node* root; +}; + +int main() { + bst* b = new bst{}; + + // 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/Year_1/Programming_2/data_structures/circle_double_list.cc b/Year_1/Programming_2/data_structures/circle_double_list.cc new file mode 100644 index 0000000..f162e57 --- /dev/null +++ b/Year_1/Programming_2/data_structures/circle_double_list.cc @@ -0,0 +1,185 @@ +#include + +using namespace std; + +template +struct node { + T value; + node* prev; + node* next; +}; + + +template +class list { +public: + list() : _head{nullptr} {} + + ~list() { + node* iter = _head; + while(iter->next != _head) { + node* tmp = iter; + delete tmp; + iter = iter->next; + } + node* tmp = iter; + delete tmp; + } + + list* push_front(T val) { + auto elem = _last(); + if(!_head) { + _head = new node{val, nullptr, nullptr}; + _head->prev = _head->next = _head; + } else { + _head = new node{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{val, last_e, _head}; + _head->prev = last_e->next; + + return this; + } + + list* push_after_value(T val, T newval) { + node* iter = _search(val); + if(iter) { + node* nod = new node{newval, iter, iter->next}; + iter->next = nod; + nod->next->prev = nod; + } + + return this; + } + + list* push_before_value(T val, T newval) { + node* elem = _search(val); + if(!elem) return this; + + node* iter = _head; + + if(iter->value == val) + return this->push_front(newval); + + while(iter->next != elem) + iter = iter->next; + + node* nod = new node{newval, iter, iter->next}; + iter->next = nod; + nod->next->prev = nod; + + return this; + } + + list* pop(int val) { + node* elem = _search(val); + if(!elem) return this; + + if(elem == _head) return this->pop_front(); + + node* iter = elem->prev; + node* 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* 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* 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* _last() { + node* iter = _head; + while(iter && iter->next != _head) { + iter = iter->next; + } + + return iter; + } + + node* _search(T val) { + node* iter = _head; + if(iter->value == val) return iter; + + while(iter && iter->value != val) { + iter = iter->next; + if(iter == _head) return nullptr; + } + + return iter; + } + + node* _head; +}; + +int main() { + list* l = new list{}; + 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/Year_1/Programming_2/data_structures/circle_list.cc b/Year_1/Programming_2/data_structures/circle_list.cc new file mode 100644 index 0000000..2143ac1 --- /dev/null +++ b/Year_1/Programming_2/data_structures/circle_list.cc @@ -0,0 +1,189 @@ +#include + +using namespace std; + +template +struct node { + T value; + node* next; +}; + + +template +class list { +public: + list() : _head{nullptr} {} + + ~list() { + node* iter = _head; + while(iter->next != _head) { + node* tmp = iter; + delete tmp; + iter = iter->next; + } + node* tmp = iter; + delete tmp; + } + + list* push_front(T val) { + auto elem = _last(); + _head = new node{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{val, _head}; + + return this; + } + + list* push_after_value(T val, T newval) { + node* iter = _search(val); + if(iter) + iter->next = new node{newval, iter->next}; + + return this; + } + + list* push_before_value(T val, T newval) { + node* elem = _search(val); + if(!elem) return this; + + node* iter = _head; + + if(iter->value == val) + return this->push_front(newval); + + while(iter->next != elem) + iter = iter->next; + + iter->next = new node{newval, iter->next}; + + return this; + } + + list* pop(int val) { + node* elem = _search(val); + if(!elem) return this; + + node* iter = _head; + if(iter == elem) return this->pop_front(); + + while(iter->next != elem) + iter = iter->next; + + node* 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* elem = _head; + _head = _head->next; + last_e->next = _head; + delete elem; + } + + return this; + } + + list* pop_back() { + if(!_head) + return this; + + node* 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* iter = _head; + while(iter) { + cout << iter->value << ' '; + iter = iter->next; + if(iter == _head) break; + } + } +private: + node* _last() { + node* iter = _head; + while(iter && iter->next != _head) { + iter = iter->next; + } + + return iter; + } + + node* _search(T val) { + node* iter = _head; + if(iter->value == val) return iter; + + while(iter && iter->value != val) { + iter = iter->next; + if(iter == _head) return nullptr; + } + + return iter; + } + + node* _head; +}; + +int main() { + list* l = new list{}; + 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/Year_1/Programming_2/data_structures/dfs.cc b/Year_1/Programming_2/data_structures/dfs.cc new file mode 100644 index 0000000..744f153 --- /dev/null +++ b/Year_1/Programming_2/data_structures/dfs.cc @@ -0,0 +1,191 @@ +#include +#include +#include +#define W -1 +#define G 0 +#define B 1 + +using namespace std; + +template +class node { +public: + explicit node(H key, node* next) : _key{key}, _next(next) {} + const H& key() const { return _key; } + H& key() { return _key; } + const node*& next() const { return _next; } + node*& next() { return _next; } +private: + H _key; + node* _next; +}; + +template +class list { +public: + list() : _head{nullptr} {} + ~list() { + while(_head) { + auto tmp = _head; + _head = _head->next(); + delete tmp; + } + } + list* push(H val) { + auto iter = _head; + while(iter && iter->next()) + iter = iter->next(); + + if(!iter) + _head = new node{val, nullptr}; + else + iter->next() = new node{val, nullptr}; + + return this; + } + void print() { + auto iter = _head; + while(iter) { + cout << iter->key() << ' '; + iter = iter->next(); + } + } + vector as_vector() { + vector v; + auto iter = _head; + while(iter) { + v.push_back(iter->key()); + iter = iter->next(); + } + return v; + } + node* search(H val) { + auto iter = _head; + while(iter && iter->key() != val) { + iter = iter->next(); + } + + return iter; + } +private: + node* _head; +}; + +template +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** _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*[_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{}; + } + } + + graph* 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* 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* g = new graph(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/Year_1/Programming_2/data_structures/graph.cc b/Year_1/Programming_2/data_structures/graph.cc new file mode 100644 index 0000000..12837be --- /dev/null +++ b/Year_1/Programming_2/data_structures/graph.cc @@ -0,0 +1,164 @@ +#include +#include + +using namespace std; + +template +class node { +public: + explicit node(H key, node* next) : _key{key}, _next(next) {} + const H& key() const { return _key; } + H& key() { return _key; } + const node*& next() const { return _next; } + node*& next() { return _next; } +private: + H _key; + node* _next; +}; + +template +class list { +public: + list() : _head{nullptr} {} + ~list() { + while(_head) { + auto tmp = _head; + _head = _head->next(); + delete tmp; + } + } + list* push(H val) { + auto iter = _head; + while(iter && iter->next()) + iter = iter->next(); + + if(!iter) + _head = new node{val, nullptr}; + else + iter->next() = new node{val, nullptr}; + + return this; + } + list* 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 as_vector() { + vector v; + auto iter = _head; + while(iter) { + v.push_back(iter->key()); + iter = iter->next(); + } + return v; + } + node* search(H val) { + auto iter = _head; + while(iter && iter->key() != val) { + iter = iter->next(); + } + + return iter; + } +private: + node* _head; +}; + +template +class graph { +public: + +private: + int _len, _nodes, _edges; + H **_k; + list **_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*[_len]; + for(int i = 0; i < _len; ++i) { + _k[i] = nullptr; + _adj[i] = new list{}; + } + } + + graph* 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* 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* g = new graph(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/Year_1/Programming_2/data_structures/graph_stl.cc b/Year_1/Programming_2/data_structures/graph_stl.cc new file mode 100644 index 0000000..5381747 --- /dev/null +++ b/Year_1/Programming_2/data_structures/graph_stl.cc @@ -0,0 +1,221 @@ +#include +#include +#include +#include +#include +#define INF 99999999 +#define W -1 +#define G 0 +#define B 1 + +using namespace std; + +template +class graph { +public: + graph(int len) : _len{len}, _nodes{0}, _edges{0} { + _k = new H*[len]; + _adj = new vector[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* add_node(H x) { + if(_index(x) > -1) return this; + if(_nodes == _len) return this; + _k[_nodes++] = new H(x); + + return this; + } + graph* 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 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* _transpose() { + graph* g = new graph{_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 _stack; + H** _k; + vector* _adj; + int _len, _nodes, _edges; + int* _colors; + int _time; + int* _d; + int* _f; + int* _p; +}; + +int main() { + graph* g = new graph{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/Year_1/Programming_2/data_structures/list.cc b/Year_1/Programming_2/data_structures/list.cc new file mode 100644 index 0000000..8ddcbf9 --- /dev/null +++ b/Year_1/Programming_2/data_structures/list.cc @@ -0,0 +1,164 @@ +#include + +using namespace std; + +template +struct node { + T value; + node* next; +}; + + +template +class list { +public: + list() : _head{nullptr} {} + + ~list() { + while(_head) { + node* tmp = _head->next; + delete tmp; + _head = tmp; + } + } + + list* push_front(T val) { + _head = new node{val, _head}; + + return this; + } + + list* push_back(T val) { + if(!_head) return this->push_front(val); + + node* iter = _head; + while(iter->next) { + iter = iter->next; + } + iter->next = new node{val, nullptr}; + + return this; + } + + list* push_after_value(T val, T newval) { + node* iter = _search(val); + if(iter) + iter->next = new node{newval, iter->next}; + + return this; + } + + list* push_before_value(T val, T newval) { + node* elem = _search(val); + if(!elem) return this; + + node* iter = _head; + + if(iter->value == val) + return this->push_front(newval); + + while(iter->next != elem) + iter = iter->next; + + iter->next = new node{newval, iter->next}; + + return this; + } + + list* pop(int val) { + node* elem = _search(val); + if(!elem) return this; + + node* iter = _head; + if(iter == elem) return this->pop_front(); + + while(iter->next != elem) + iter = iter->next; + + node* temp = iter->next; + iter->next = iter->next->next; + delete temp; + + return this; + } + + list* pop_front() { + if(!_head) + return this; + + node* elem = _head; + _head = _head->next; + delete elem; + + return this; + } + + list* pop_back() { + if(!_head) + return this; + + node* 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* iter = _head; + while(iter) { + cout << iter->value << ' '; + iter = iter->next; + } + } +private: + node* _search(T value) { + node* iter = _head; + while(iter && iter->value != value) + iter = iter->next; + + return iter; + } + + node* _head; +}; + +int main() { + list* l = new list{}; + 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/Year_1/Programming_2/data_structures/list_double.cc b/Year_1/Programming_2/data_structures/list_double.cc new file mode 100644 index 0000000..fa0af26 --- /dev/null +++ b/Year_1/Programming_2/data_structures/list_double.cc @@ -0,0 +1,182 @@ +#include + +using namespace std; + +template +struct node { + T value; + node* prev; + node* next; +}; + + +template +class list { +public: + list() : _head{nullptr} {} + + ~list() { + while(_head != nullptr) { + node* tmp = _head->next; + delete tmp; + _head = tmp; + } + } + + list* push_front(T val) { + if(!_head) { + _head = new node{val, nullptr, nullptr}; + } else { + _head = new node{val, nullptr, _head}; + _head->next->prev = _head; + } + + return this; + } + + list* push_back(T val) { + if(!_head) return this->push_front(val); + + node* iter = _head; + while(iter->next) { + iter = iter->next; + } + iter->next = new node{val, iter, nullptr}; + + return this; + } + + list* push_after_value(T val, T newval) { + node* elem = _search(val); + if(elem) { + node* nod = new node{newval, elem, elem->next}; + elem->next = nod; + nod->next->prev = nod; + } + + return this; + } + + list* push_before_value(T val, T newval) { + node* elem = _search(val); + if(!elem) return this; + + node* iter = _head; + + if(iter->value == val) + return this->push_front(newval); + + while(iter->next != elem) + iter = iter->next; + + node* nod = new node{newval, iter, iter->next}; + iter->next = nod; + nod->next->prev = nod; + + return this; + } + + list* pop(int val) { + node* elem = _search(val); + if(!elem) return this; + + if(elem == _head) return this->pop_front(); + + node* iter = elem->prev; + node* temp = iter->next; + iter->next = iter->next->next; + iter->next->prev = iter; + delete temp; + + return this; + } + + list* pop_front() { + if(!_head) + return this; + + node* elem = _head; + _head = _head->next; + _head->prev = nullptr; + delete elem; + + return this; + } + + list* pop_back() { + if(!_head) + return this; + + node* 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* 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* _last() { + node* iter = _head; + while(iter->next) { + iter = iter->next; + } + + return iter; + } + + node* _search(T value) { + node* iter = _head; + while(iter && iter->value != value) + iter = iter->next; + + return iter; + } + + node* _head; +}; + +int main() { + list* l = new list{}; + 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/Year_1/Programming_2/data_structures/matrix-graph.cc b/Year_1/Programming_2/data_structures/matrix-graph.cc new file mode 100644 index 0000000..a644ec1 --- /dev/null +++ b/Year_1/Programming_2/data_structures/matrix-graph.cc @@ -0,0 +1,81 @@ +#include +#include + +using namespace std; + +template +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* 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* 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* g = new matrix_graph(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/Year_1/Programming_2/data_structures/queue.cc b/Year_1/Programming_2/data_structures/queue.cc new file mode 100644 index 0000000..8398459 --- /dev/null +++ b/Year_1/Programming_2/data_structures/queue.cc @@ -0,0 +1,72 @@ +#include + +using namespace std; + +template +struct node { + T value; + node* next; +}; + +template +class queue { +public: + queue() : _head{nullptr} {} + + ~queue() { + auto iter = _head; + while(iter) { + delete iter; + iter = iter->next; + } + } + + queue* enqueue(T val) { + + if(!_head) { + _head = new node{val, nullptr}; + _tail = _head; + } else { + _tail->next = new node{val, nullptr}; + _tail = _tail->next; + } + + return this; + } + + node* 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* _head; + node* _tail; +}; + +int main() { + queue* q = new queue(); + + 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/Year_1/Programming_2/data_structures/queue_w_array.cc b/Year_1/Programming_2/data_structures/queue_w_array.cc new file mode 100644 index 0000000..fb92d68 --- /dev/null +++ b/Year_1/Programming_2/data_structures/queue_w_array.cc @@ -0,0 +1,66 @@ +#include + +using namespace std; + +template +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* 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* q = new queue{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/Year_1/Programming_2/data_structures/stack.cc b/Year_1/Programming_2/data_structures/stack.cc new file mode 100644 index 0000000..ffff780 --- /dev/null +++ b/Year_1/Programming_2/data_structures/stack.cc @@ -0,0 +1,70 @@ +#include + +using namespace std; + +template +struct node { + T value; + node* next; +}; + +template +class stack { +public: + stack() : _head{nullptr} {} + + ~stack() { + auto iter = _head; + while(iter) { + delete iter; + iter = iter->next; + } + } + + stack* push(T val) { + + if(!_head) { + _head = new node{val, nullptr}; + } else { + _head = new node{val, _head}; + } + + return this; + } + + node* pop() { + if(!_head) return nullptr; + node* 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* _head; +}; + +int main() { + stack* s = new stack(); + + 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/Year_1/Programming_2/data_structures/stack_w_array.cc b/Year_1/Programming_2/data_structures/stack_w_array.cc new file mode 100644 index 0000000..c20db90 --- /dev/null +++ b/Year_1/Programming_2/data_structures/stack_w_array.cc @@ -0,0 +1,50 @@ +#include + +using namespace std; + +template +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* 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* s = new stack{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/Year_1/Programming_2/data_structures/top-sort.cc b/Year_1/Programming_2/data_structures/top-sort.cc new file mode 100644 index 0000000..7441ee9 --- /dev/null +++ b/Year_1/Programming_2/data_structures/top-sort.cc @@ -0,0 +1,212 @@ + +#include +#include +#include +#define W -1 +#define G 0 +#define B 1 + +using namespace std; + +template +class node { +public: + explicit node(H key, node* next) : _key{key}, _next(next) {} + const H& key() const { return _key; } + H& key() { return _key; } + const node*& next() const { return _next; } + node*& next() { return _next; } +private: + H _key; + node* _next; +}; + +template +class list { +public: + list() : _head{nullptr} {} + ~list() { + while(_head) { + auto tmp = _head; + _head = _head->next(); + delete tmp; + } + } + list* push(H val) { + auto iter = _head; + while(iter && iter->next()) + iter = iter->next(); + + if(!iter) + _head = new node{val, nullptr}; + else + iter->next() = new node{val, nullptr}; + + return this; + } + void print() { + auto iter = _head; + while(iter) { + cout << iter->key() << ' '; + iter = iter->next(); + } + } + vector as_vector() { + vector v; + auto iter = _head; + while(iter) { + v.push_back(iter->key()); + iter = iter->next(); + } + return v; + } + node* search(H val) { + auto iter = _head; + while(iter && iter->key() != val) { + iter = iter->next(); + } + + return iter; + } +private: + node* _head; +}; + +template +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** _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*[_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{}; + } + } + + graph* 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 s(_finishes, _finishes+_nodes); + sort(begin(s), end(s)); + for(auto const& i : s) { + cout << "(" << i << ", " << _finishes[i] << ") "; + } + } + + graph* 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* g = new graph(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/Year_1/Programming_2/exercises/carattere-maggiore.cc b/Year_1/Programming_2/exercises/carattere-maggiore.cc new file mode 100644 index 0000000..2e89fcd --- /dev/null +++ b/Year_1/Programming_2/exercises/carattere-maggiore.cc @@ -0,0 +1,40 @@ +#include +#include +#include + +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 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/Year_1/Programming_2/exercises/dequeue.cc b/Year_1/Programming_2/exercises/dequeue.cc new file mode 100644 index 0000000..4b012c4 --- /dev/null +++ b/Year_1/Programming_2/exercises/dequeue.cc @@ -0,0 +1,137 @@ + +#include +#include + +using namespace std; + +template +class node { +public: + node(T key, node* next) : _key{key}, _next{next} {} + node(T key) : _key{key}, _next{nullptr} {} + const T& key() const { return _key; } + T& key() { return _key; } + const node*& next() const { return _next; } + node*& next() { return _next; } +private: + T _key; + node* _next; +}; + +template +class Coda { +public: + Coda() : _head{nullptr}, _tail{nullptr} {} + ~Coda() { + + } + Coda* enqueue(T val) { + if(!_head) { + _head = new node{val, nullptr}; + _tail = _head; + } else { + _tail->next() = new node{val, nullptr}; + _tail = _tail->next(); + } + + return this; + } + node* dequeue() { + if(!_head) return nullptr; + node* elem = _head; + delete _head; + _head = elem->next(); + + return elem; + } + + bool is_empty() { return _head == nullptr; } +private: + node* _head; + node* _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* queue = new Coda{}; + 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* queue = new Coda{}; + 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* queue = new Coda{}; + 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* queue = new Coda{}; + 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/Year_1/Programming_2/exercises/doppioni.cc b/Year_1/Programming_2/exercises/doppioni.cc new file mode 100644 index 0000000..fdd3e88 --- /dev/null +++ b/Year_1/Programming_2/exercises/doppioni.cc @@ -0,0 +1,77 @@ +#include +#include + +using namespace std; + +template +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*& parent() { return _parent; } + const node*& parent() const { return _parent; } + node*& right() { return _right; } + const node*& right() const { return _right; } + node*& left() { return _left; } + const node*& left() const { return _left; } +private: + T _key; + node* _parent; + node* _right; + node* _left; +}; + +class bst { +public: + bst() : _duplicates{0}, _root{nullptr} {} + bst* add(int val) { + node* iter = _root; + node* 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* nodus = new node{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* _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/Year_1/Programming_2/exercises/estremi-uguali.cc b/Year_1/Programming_2/exercises/estremi-uguali.cc new file mode 100644 index 0000000..63ac019 --- /dev/null +++ b/Year_1/Programming_2/exercises/estremi-uguali.cc @@ -0,0 +1,32 @@ +#include +#include +#include + +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/Year_1/Programming_2/exercises/even-length.cc b/Year_1/Programming_2/exercises/even-length.cc new file mode 100644 index 0000000..2d3d6a4 --- /dev/null +++ b/Year_1/Programming_2/exercises/even-length.cc @@ -0,0 +1,27 @@ +#include +#include +#include + +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/Year_1/Programming_2/exercises/exam_08_10_14.cc b/Year_1/Programming_2/exercises/exam_08_10_14.cc new file mode 100644 index 0000000..c9c33be --- /dev/null +++ b/Year_1/Programming_2/exercises/exam_08_10_14.cc @@ -0,0 +1,202 @@ +#include + +using namespace std; + +template class MultiBST { + virtual MultiBST* ins(H x) = 0; + virtual int multiplicity(H x) = 0; + virtual void inorder() = 0; +}; + +template +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*& parent() { return _parent; } + const node*& parent() const { return _parent; } + node*& left() { return _left; } + const node*& left() const { return _left; } + node*& right() { return _right; } + const node*& right() const { return _right; } + int& rk() { return _rk; } + const int& rk() const { return _rk; } +private: + H _key; + node* _parent; + node* _left; + node* _right; + int _rk; +}; + +template +class MyMultiBST : public MultiBST { +public: + MyMultiBST() : _root{nullptr} {} + node*& root() { return _root; } + const node*& root() const { return _root; } + int multiplicity(H x) { + auto elem = _search(x); + if(elem) + return elem->rk(); + return 0; + } + MyMultiBST* ins(H x) { + auto iter = _search(x); + if(iter) { + iter->rk() = iter->rk()+1; + } else { + iter = _root; + node* y{nullptr}; + + while(iter) { + y = iter; + if(iter->key() > x) + iter = iter->left(); + else + iter = iter->right(); + } + + node* nodus = new node{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* del(H x) { + node* y; + node* 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* 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* u, node* 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* _max(node* x) { + if(!x) return nullptr; + + auto iter = x; + while(iter->right()) { + iter = iter->right(); + } + + return iter; + } + node* _min(node* x) { + if(!x) return nullptr; + + auto iter = x; + while(iter->left()) { + iter = iter->left(); + } + + return iter; + } + void _inorder(node* p) { + if(p) { + _inorder(p->left()); + for(int i = 0; i < p->rk(); ++i) { + cout << p->key() << ' '; + } + _inorder(p->right()); + } + } + node* _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* _root; +}; + +int main() { + MyMultiBST* t = new MyMultiBST{}; + + 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/Year_1/Programming_2/exercises/exam_20_07_20/ex1.cpp b/Year_1/Programming_2/exercises/exam_20_07_20/ex1.cpp new file mode 100644 index 0000000..4f08a74 --- /dev/null +++ b/Year_1/Programming_2/exercises/exam_20_07_20/ex1.cpp @@ -0,0 +1,39 @@ +#include +#include +#include +#include + +using namespace std; +int insertionsort(vector& 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 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/Year_1/Programming_2/exercises/exam_20_07_20/ex2.cpp b/Year_1/Programming_2/exercises/exam_20_07_20/ex2.cpp new file mode 100644 index 0000000..aed25e4 --- /dev/null +++ b/Year_1/Programming_2/exercises/exam_20_07_20/ex2.cpp @@ -0,0 +1,63 @@ +#include +#include +#include +#include + +using namespace std; +using pi = tuple>; + +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> v; + priority_queue, comp> pq; + int k; + for(int i = 0; i < R; ++i) { + v.push_back(vector{}); + 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/Year_1/Programming_2/exercises/exam_20_07_20/ex3.cpp b/Year_1/Programming_2/exercises/exam_20_07_20/ex3.cpp new file mode 100644 index 0000000..71f9c65 --- /dev/null +++ b/Year_1/Programming_2/exercises/exam_20_07_20/ex3.cpp @@ -0,0 +1,284 @@ +#include +#include +#include + +using namespace std; + +template +struct node { + T key; + node* prev; + node* right; + node* left; +}; + +template +class bst { +public: + bst() : root{nullptr} , _val{0}{} + + ~bst() { + // TODO + } + + bst* insert(initializer_list&& list) { + for(auto const& i : list) + insert(i); + + return this; + } + + bst* insert(T k) { + node* nodus = new node{k, nullptr, nullptr, nullptr}; + node* iter = root; + node* 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* remove(initializer_list&& list) { + for(auto const& i : list) + remove(i); + + return this; + } + + bst* remove(T k) { + node* nodus = search(k); + if(!nodus) return this; + + if(!nodus->left) { + _transplant(nodus, nodus->right); + } else if(!nodus->right) { + _transplant(nodus, nodus->left); + } else { + node* 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* min() { + return _min(root); + } + + node* min(node* nodus) { + return _min(nodus); + } + + node* max() { + return _max(root); + } + + node* max(node* nodus) { + return _max(nodus); + } + + node* search(T k) { + node* iter = root; + while(iter && iter->key != k) + iter = (iter->key > k) ? iter->left : iter->right; + + return iter; + } + + node* successor(T k) { + node* nodus = search(k); + if(!nodus) return nullptr; + + if(nodus->right) + return min(nodus->right); + + node* prev = nodus->prev; + while(prev && nodus == prev->right) { + nodus = prev; + prev = prev->prev; + } + + return prev; + + } + node* predecessor(T k) { + node* nodus = search(k); + if(!nodus) return nullptr; + + if(nodus->left) + return max(nodus->left); + + node* prev = nodus->prev; + while(prev && nodus == prev->left) { + nodus = prev; + prev = prev->prev; + } + + return prev; + } + + friend ostream& operator<<(ostream& os, bst* tree) { + tree->_inorder(os, tree->root); + return os; + } + T sol(T k) { + return _max(search(k))->key; + } +private: + int _val; + void _transplant(node* u, node* 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* _min(node* root) { + node* iter = root; + while(iter && iter->left) + iter = iter->left; + + return iter; + } + + node* _max(node* root) { + node* iter = root; + while(iter && iter->right) + iter = iter->right; + + return iter; + } + + void _inorder(ostream& os, node* 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* root) { + if(root) { + os << root->key << ' '; + _inorder(os, root->left); + _inorder(os, root->right); + } + } + + void _postorder(ostream& os, node* root) { + if(root) { + _inorder(os, root->left); + _inorder(os, root->right); + os << root->key << ' '; + } + } + node* 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* b = new bst{}; + 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* b = new bst{}; + 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/Year_1/Programming_2/exercises/exam_20_07_20/ex4.cpp b/Year_1/Programming_2/exercises/exam_20_07_20/ex4.cpp new file mode 100644 index 0000000..e234363 --- /dev/null +++ b/Year_1/Programming_2/exercises/exam_20_07_20/ex4.cpp @@ -0,0 +1,293 @@ +#include +#include +#include + +using namespace std; + +template +struct node { + T key; + node* prev; + node* right; + node* left; +}; + +template +class bst { +public: + bst() : root{nullptr} , _val{0}{} + + ~bst() { + // TODO + } + + bst* insert(initializer_list&& list) { + for(auto const& i : list) + insert(i); + + return this; + } + + bst* insert(T k) { + node* nodus = new node{k, nullptr, nullptr, nullptr}; + node* iter = root; + node* 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* remove(initializer_list&& list) { + for(auto const& i : list) + remove(i); + + return this; + } + + bst* remove(T k) { + node* nodus = search(k); + if(!nodus) return this; + + if(!nodus->left) { + _transplant(nodus, nodus->right); + } else if(!nodus->right) { + _transplant(nodus, nodus->left); + } else { + node* 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* min() { + return _min(root); + } + + node* min(node* nodus) { + return _min(nodus); + } + + node* max() { + return _max(root); + } + + node* max(node* nodus) { + return _max(nodus); + } + + node* search(T k) { + node* iter = root; + while(iter && iter->key != k) + iter = (iter->key > k) ? iter->left : iter->right; + + return iter; + } + + node* successor(T k) { + node* nodus = search(k); + if(!nodus) return nullptr; + + if(nodus->right) + return min(nodus->right); + + node* prev = nodus->prev; + while(prev && nodus == prev->right) { + nodus = prev; + prev = prev->prev; + } + + return prev; + + } + node* predecessor(T k) { + node* nodus = search(k); + if(!nodus) return nullptr; + + if(nodus->left) + return max(nodus->left); + + node* prev = nodus->prev; + while(prev && nodus == prev->left) { + nodus = prev; + prev = prev->prev; + } + + return prev; + } + + friend ostream& operator<<(ostream& os, bst* 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* u, node* 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* _min(node* root) { + node* iter = root; + while(iter && iter->left) + iter = iter->left; + + return iter; + } + + node* _max(node* root) { + node* iter = root; + while(iter && iter->right) + iter = iter->right; + + return iter; + } + + void _inorder(ostream& os, node* 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* root) { + if(root) { + os << root->key << ' '; + _inorder(os, root->left); + _inorder(os, root->right); + } + } + + void _postorder(ostream& os, node* root) { + if(root) { + _inorder(os, root->left); + _inorder(os, root->right); + os << root->key << ' '; + } + } + node* 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* b = new bst{}; + 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* b = new bst{}; + 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/Year_1/Programming_2/exercises/exam_20_07_20/ex5.cpp b/Year_1/Programming_2/exercises/exam_20_07_20/ex5.cpp new file mode 100644 index 0000000..dd8fc98 --- /dev/null +++ b/Year_1/Programming_2/exercises/exam_20_07_20/ex5.cpp @@ -0,0 +1,285 @@ +#include +#include +#include +#include +#include +#include +#define INF 99999999 +#define W -1 +#define G 0 +#define B 1 + +using namespace std; + +template +class graph { +public: + graph(int len) : _len{len}, _nodes{0}, _edges{0} { + _k = new H*[len]; + _adj = new vector[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* add_node(H x) { + if(_index(x) > -1) return this; + if(_nodes == _len) return this; + _k[_nodes++] = new H(x); + + return this; + } + graph* 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 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* _transpose() { + graph* g = new graph{_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 _stack; + H** _k; + vector* _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* g = new graph{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()<* g = new graph{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()<* g = new graph{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()< +#include +#include + +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/Year_1/Programming_2/exercises/inserimento-coda.cc b/Year_1/Programming_2/exercises/inserimento-coda.cc new file mode 100644 index 0000000..6775ca2 --- /dev/null +++ b/Year_1/Programming_2/exercises/inserimento-coda.cc @@ -0,0 +1,119 @@ +#include +#include + +using namespace std; + +template +class node { +public: + node(T key, node* next) : _key{key}, _next{next} {} + node(T key) : _key{key}, _next{nullptr} {} + const T& key() const { return _key; } + T& key() { return _key; } + const node*& next() const { return _next; } + node*& next() { return _next; } +private: + T _key; + node* _next; +}; + +template +class Coda { +public: + Coda() : _head{nullptr}, _tail{nullptr} {} + ~Coda() { + + } + Coda* enqueue(T val) { + if(!_head) { + _head = new node{val, nullptr}; + _tail = _head; + } else { + _tail->next() = new node{val, nullptr}; + _tail = _tail->next(); + } + + return this; + } + node* pop() { + if(!_head) return nullptr; + node* elem = _head; + delete _head; + _head = elem->next(); + + return elem; + } + + bool is_empty() { return _head == nullptr; } +private: + node* _head; + node* _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* queue = new Coda{}; + 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* queue = new Coda{}; + 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* queue = new Coda{}; + 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* queue = new Coda{}; + 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/Year_1/Programming_2/exercises/inserimento-pila.cc b/Year_1/Programming_2/exercises/inserimento-pila.cc new file mode 100644 index 0000000..0dbe99b --- /dev/null +++ b/Year_1/Programming_2/exercises/inserimento-pila.cc @@ -0,0 +1,116 @@ +#include +#include + +using namespace std; + +template +class node { +public: + node(T key, node* next) : _key{key}, _next{next} {} + node(T key) : _key{key}, _next{nullptr} {} + const T& key() const { return _key; } + T& key() { return _key; } + const node*& next() const { return _next; } + node*& next() { return _next; } +private: + T _key; + node* _next; +}; + +template +class Pila { +public: + Pila() : _head{nullptr}{} + ~Pila() { + + } + Pila* push(T val) { + if(!_head) { + _head = new node{val, nullptr}; + } else { + _head = new node{val, _head}; + } + + return this; + } + node* pop() { + if(!_head) return nullptr; + node* elem = _head; + delete _head; + _head = elem->next(); + + return elem; + } + + bool is_empty() { return _head == nullptr; } +private: + node* _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* stack = new Pila{}; + 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* stack = new Pila{}; + 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* stack = new Pila{}; + 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* stack = new Pila{}; + 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/Year_1/Programming_2/exercises/matrice-adj.cc b/Year_1/Programming_2/exercises/matrice-adj.cc new file mode 100644 index 0000000..7830f97 --- /dev/null +++ b/Year_1/Programming_2/exercises/matrice-adj.cc @@ -0,0 +1,151 @@ +#include +#include +#include +#include + +using namespace std; + +template +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* 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* 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> print() { + vector> v; + for(int i = 0; i < _len; ++i) { + v.push_back(vector{*_k[i]}); + vector 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 +string result(vector> 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* g = new matrix_graph(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* g = new matrix_graph(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* g = new matrix_graph(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/Year_1/Programming_2/exercises/minore.cc b/Year_1/Programming_2/exercises/minore.cc new file mode 100644 index 0000000..677da76 --- /dev/null +++ b/Year_1/Programming_2/exercises/minore.cc @@ -0,0 +1,27 @@ +#include +#include +#include + +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/Year_1/Programming_2/exercises/pop-stack.cc b/Year_1/Programming_2/exercises/pop-stack.cc new file mode 100644 index 0000000..3739450 --- /dev/null +++ b/Year_1/Programming_2/exercises/pop-stack.cc @@ -0,0 +1,132 @@ +#include +#include + +using namespace std; + +template +class node { +public: + node(T key, node* next) : _key{key}, _next{next} {} + node(T key) : _key{key}, _next{nullptr} {} + const T& key() const { return _key; } + T& key() { return _key; } + const node*& next() const { return _next; } + node*& next() { return _next; } +private: + T _key; + node* _next; +}; + +template +class Pila { +public: + Pila() : _head{nullptr}{} + ~Pila() { + + } + Pila* push(T val) { + if(!_head) { + _head = new node{val, nullptr}; + } else { + _head = new node{val, _head}; + } + + return this; + } + node* pop() { + if(!_head) return nullptr; + node* elem = _head; + delete _head; + _head = elem->next(); + + return elem; + } + + bool is_empty() { return _head == nullptr; } +private: + node* _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* stack = new Pila{}; + 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* stack = new Pila{}; + 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* stack = new Pila{}; + 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* stack = new Pila{}; + 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/Year_1/Programming_2/exercises/prima-maiuscola.cc b/Year_1/Programming_2/exercises/prima-maiuscola.cc new file mode 100644 index 0000000..6273219 --- /dev/null +++ b/Year_1/Programming_2/exercises/prima-maiuscola.cc @@ -0,0 +1,30 @@ +#include +#include +#include + +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/Year_1/Programming_2/exercises/ripetute.cc b/Year_1/Programming_2/exercises/ripetute.cc new file mode 100644 index 0000000..23d151a --- /dev/null +++ b/Year_1/Programming_2/exercises/ripetute.cc @@ -0,0 +1,20 @@ +#include +#include +#include + +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/Year_1/Programming_2/exercises/sol-ripetute.cc b/Year_1/Programming_2/exercises/sol-ripetute.cc new file mode 100644 index 0000000..1518d76 --- /dev/null +++ b/Year_1/Programming_2/exercises/sol-ripetute.cc @@ -0,0 +1,25 @@ +#include +#include +#include + +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/Year_1/Programming_2/exercises/sottosequenza.cc b/Year_1/Programming_2/exercises/sottosequenza.cc new file mode 100644 index 0000000..1d7c481 --- /dev/null +++ b/Year_1/Programming_2/exercises/sottosequenza.cc @@ -0,0 +1,26 @@ +#include +#include + +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/Year_1/Programming_2/exercises/stringa-inversa.cc b/Year_1/Programming_2/exercises/stringa-inversa.cc new file mode 100644 index 0000000..5c37718 --- /dev/null +++ b/Year_1/Programming_2/exercises/stringa-inversa.cc @@ -0,0 +1,26 @@ +#include +#include + +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(); +} -- cgit v1.2.3-18-g5258