chore: order in coding contest folder

10 files changed, 534 insertions, 0 deletions

diff --git a/I_anno/Programmazione_2/coding_contest/dolcetti.cpp b/I_anno/Programmazione_2/coding_contest/dolcetti.cpp
new file mode 100644
index 0000000..c3409a4
--- /dev/null
+++ b/I_anno/Programmazione_2/coding_contest/dolcetti.cpp
@@ -0,0 +1,51 @@
+#include<iostream>
+#include<fstream>
+#include<queue>
+#include<vector>
+
+using namespace std;
+
+int main() {
+    using tii = tuple<int, int, int>;
+    ifstream in("input.txt");
+    ofstream out("output.txt");
+
+    for(int ts = 0; ts < 100; ++ts) {
+        int N;
+        in >> N;
+
+        priority_queue<tii, vector<tii>> pq;
+        tii qq;
+        for(int i = 0; i < N; ++i) {
+            int e1, e2;
+            in >> e1 >> e2;
+            get<0>(qq) = e1-e2;
+            get<1>(qq) = e1;
+            get<2>(qq) = e2;
+
+            pq.push(qq);
+        }
+        
+        int counter = N;
+        int sum{};
+
+        while(counter-- > N/2) {
+            qq = pq.top();
+            sum += get<1>(qq);
+            pq.pop();
+        }
+
+        while(!pq.empty()) {
+            qq = pq.top();
+            sum += get<2>(qq);
+            pq.pop();
+        }
+
+        out << sum << endl;
+    }
+
+    in.close();
+    out.close();
+    return 0;
+}
+
diff --git a/I_anno/Programmazione_2/coding_contest/gita.cpp b/I_anno/Programmazione_2/coding_contest/gita.cpp
new file mode 100644
index 0000000..cbb4910
--- /dev/null
+++ b/I_anno/Programmazione_2/coding_contest/gita.cpp
@@ -0,0 +1,46 @@
+#include<iostream>
+#include<fstream>
+#include<vector>
+#include<map>
+
+using namespace std;
+
+int main() {
+    ifstream in("input.txt");
+    ofstream out("output.txt");
+    
+    for(int c = 0; c < 100; ++c) {
+        int N, L;
+        in >> N >> L;
+        vector<pair<short, int>> students;
+        for(int i = 0; i < N; ++i) {
+            int num;
+            in >> num;
+            students.push_back({num, 0});
+        }
+
+        int index, val;
+        for(int i = 0; i < L; ++i) {
+            in >> index >> val;
+            students[index].second += val;
+        }
+
+        vector<pair<short, int>> errors;
+        short _j{};
+        for(auto const& i : students) {
+            if(i.second < i.first) {
+                errors.push_back({_j, i.first-i.second});
+            }
+            _j++;
+        }
+
+        out << errors.size() << ' ';
+        for(auto const& i : errors) {
+            out << i.first << ' ' << i.second << ' ';
+        }
+        out << endl;
+    }
+    out.close();
+    in.close();
+    return 0;
+}
diff --git a/I_anno/Programmazione_2/coding_contest/gribaudo.cpp b/I_anno/Programmazione_2/coding_contest/gribaudo.cpp
new file mode 100644
index 0000000..39d0e42
--- /dev/null
+++ b/I_anno/Programmazione_2/coding_contest/gribaudo.cpp
@@ -0,0 +1,47 @@
+#include<iostream>
+#include<vector>
+#include<fstream>
+
+using namespace std;
+
+int maxpath(vector<vector<int>>& v) {
+    for(int i = v.size()-2; i >= 0; --i) {
+        for(int j = 0; j <= i; ++j) {
+            if(v[i+1][j] > v[i+1][j+1]) {
+                v[i][j] += v[i+1][j];
+            } else {
+                v[i][j] += v[i+1][j+1];
+            }
+        }
+    }
+
+    return v[0][0];
+}
+
+int main() {
+    ifstream in("input.txt");
+    ofstream out("output.txt");
+
+    for(int ts = 0; ts < 1; ++ts) {
+        int N;
+        in >> N;
+        vector<vector<int>> triangle;
+
+        for(int i = 0; i < N; ++i) {
+            int e;
+            triangle.push_back(vector<int>{});
+            int j;
+            for(j = 0; j <= i; ++j) {
+                in >> e;
+                triangle[i].push_back(e);
+            }
+            for(; j < N; ++j) 
+                triangle[i].push_back(0);
+        }
+        out << maxpath(triangle) << endl;
+    }
+
+    in.close();
+    out.close();
+    return 0;
+}
diff --git a/I_anno/Programmazione_2/coding_contest/gualtieri.cpp b/I_anno/Programmazione_2/coding_contest/gualtieri.cpp
new file mode 100644
index 0000000..f8a0ecf
--- /dev/null
+++ b/I_anno/Programmazione_2/coding_contest/gualtieri.cpp
@@ -0,0 +1,46 @@
+#include<iostream>
+#include<fstream>
+#include<map>
+
+using namespace std;
+
+int main() {
+    ifstream in("input.txt");
+    ofstream out("output.txt");
+
+    for(int ts = 0; ts < 100; ++ts) {
+        string P{}, L{};
+        in >> P;
+        in >> L;
+        map<char, int> chars;
+
+        for(auto const& c : P) {
+            (chars.find(c) == chars.end()) ? chars[c] = 1 : chars[c]+=1;
+        }
+        int lenn = L.length();
+        int lenp = P.length();
+        int counter{};
+
+        for(int i = 0; i < lenn-lenp+1; ++i) {
+            map<char, int> tmp;
+            bool check{true};
+            for(int j = i; j < i+lenp; ++j) {
+                (tmp.find(L[j]) == tmp.end()) ? tmp[L[j]] = 1 : tmp[L[j]]+=1;
+            }
+            for(auto const &i : tmp) {
+                if(chars[i.first] != tmp[i.first]) {
+                    check = false;
+                    break;
+                }
+            }
+            if(check)
+                ++counter;
+        }
+        out << counter << endl;
+
+    }
+
+    out.close();
+    in.close();
+    return 0;
+}
diff --git a/I_anno/Programmazione_2/coding_contest/ladri.cpp b/I_anno/Programmazione_2/coding_contest/ladri.cpp
new file mode 100644
index 0000000..04e8e65
--- /dev/null
+++ b/I_anno/Programmazione_2/coding_contest/ladri.cpp
@@ -0,0 +1,53 @@
+#include<iostream>
+#include<fstream>
+#include<vector>
+
+using namespace std;
+
+int main() {
+    ifstream in("input.txt");
+    ofstream out("output.txt");
+
+    for(short _ = 0; _ < 100; ++_) {
+        int N, K, M;
+        in >> N >> K >> M;
+        int* path = new int[N+1];
+        int i;
+        for(i = 0; i < N; ++i)
+            in >> path[i];
+
+        path[i] = M;
+        int start = 0;
+        vector<int> values;
+        /* 1 31 33 38 62 69 93 97 98 99 */
+        /* x x     x  x   x          x       
+         * K = 30
+         */
+        for(int i = 0; i < N+1; ++i) {
+            if(path[i] - start > K) {
+                for(int j = i-1; j >= 0; --j) {
+                    if(path[i] - path[j] <= K) {
+                        values.push_back(path[j]);
+                        start = path[j];
+                        i = j;
+                        break;
+                    }
+                }
+            }
+        }
+
+        // Stampa la path corretta per debug
+        for(auto const& i: values) 
+            cout << i << ' ';
+
+        cout << endl;
+        out << values.size() << endl;
+        delete[] path;
+    }
+
+
+    out.close();
+    in.close();
+
+    return 0;
+}
diff --git a/I_anno/Programmazione_2/coding_contest/pizzini.cpp b/I_anno/Programmazione_2/coding_contest/pizzini.cpp
new file mode 100644
index 0000000..4fcb4ab
--- /dev/null
+++ b/I_anno/Programmazione_2/coding_contest/pizzini.cpp
@@ -0,0 +1,48 @@
+#include<iostream>
+#include<fstream>
+#include<vector>
+
+using namespace std;
+
+void get_fib(vector<int> &v, int N) {
+    int a = v.at(0);
+    int b = v.at(1);
+    while(b <= N) {
+        a += b;
+        v.push_back(a);
+        swap(a, b);
+    }
+    v.pop_back();
+}
+
+int main() {
+    ifstream in("input.txt");
+    ofstream out("output.txt");
+
+    for(short _ = 0; _ < 100; ++_) {
+        int N;
+        in >> N;
+        vector<int> fib {1, 2};
+        get_fib(fib, N);
+        vector<int> seq(fib.size(), 0);
+
+        int sum{};
+        for(int i = fib.size()-1; i >= 0; --i) {
+            if(fib.at(i) + sum > N) continue;
+
+            sum += fib.at(i);
+            seq[i] = 1;
+        }
+
+
+        for(auto const& i : seq)
+            out << i;
+
+        out << endl;
+    }
+
+    out.close();
+    in.close();
+    
+    return 0;
+}
diff --git a/I_anno/Programmazione_2/coding_contest/scheletri.cpp b/I_anno/Programmazione_2/coding_contest/scheletri.cpp
new file mode 100644
index 0000000..2389d25
--- /dev/null
+++ b/I_anno/Programmazione_2/coding_contest/scheletri.cpp
@@ -0,0 +1,56 @@
+#include<iostream>
+#include<fstream>
+#include<vector>
+#include<algorithm>
+
+using namespace std;
+
+int find_i(int index, vector<int> cms) {
+    for(int i = index; i < cms.size(); ++i) {
+        if(cms.at(i) != 0)
+            return i;
+    }
+    
+    return 0;
+}
+
+int find_j(int index, vector<int> cms) {
+    for(int j = index; j < cms.size()-1; ++j) {
+        if(cms.at(j+1) == 0)
+            return j+1;
+    }
+    
+    return cms.size();
+}
+
+int main() {
+    ifstream in("input.txt");
+    ofstream out("output.txt");
+
+    short N;
+    for(int __c = 0; __c < 100; ++__c) {
+        in >> N;
+        vector<int> cms;
+        int el;
+        for(short i = 0; i < N; ++i) {
+            in >> el;
+            cms.push_back(el);
+        }
+        
+        int counter{};
+        int i{}, j{};
+        while(count_if(begin(cms), end(cms), [](int num) { return num == 0; } ) != cms.size() ) {
+            i = find_i(i, cms);
+            j = find_j(i, cms);
+            for(int ii = i; ii < j; ++ii) {
+                --cms[ii];
+            }
+            ++counter;
+        }
+        out << counter << endl;
+    }
+
+    out.close();
+    in.close();
+    return 0;
+}
diff --git a/I_anno/Programmazione_2/coding_contest/stazioni.cpp b/I_anno/Programmazione_2/coding_contest/stazioni.cpp
new file mode 100644
index 0000000..29ede44
--- /dev/null
+++ b/I_anno/Programmazione_2/coding_contest/stazioni.cpp
@@ -0,0 +1,82 @@
+#include<iostream>
+#include<fstream>
+#include<algorithm>
+#include<vector>
+
+using namespace std;
+
+int main() {
+    ifstream in("input.txt");
+    ofstream out("output.txt");
+
+    for(int ts = 0; ts < 1; ++ts) {
+        int N, S;
+        in >> N >> S;
+        vector<long> st;
+        vector<vector<long>> paths;
+        vector<vector<long>> paths2;
+        vector<vector<long>> paths3;
+
+        int e;
+        for(int i = 0; i < N; ++i) {
+            in >> e;
+            st.push_back(e);
+        }
+
+        int index{};
+        for(int i = 0; i < N-S+1; ++i) {
+            for(int j = 0; j < N; ++j) {
+                paths.push_back(vector<long>{});
+                paths[index].push_back(i);
+                for(int k = j; paths[index].size() < S; ++k) {
+                    int t = (k == N) ? 0 : k;
+                    if(k > N) break;
+                    paths[index].push_back(t);
+                }
+                sort(begin(paths[index]), end(paths[index]));
+                if(paths[index].size() == S)
+                    paths2.push_back(paths[index]);
+                ++index;
+            }
+        }
+        for(int i = 0; i < paths2.size(); ++i) {
+            bool check{true};
+            if(paths2[i].size() != S) continue;
+            for(int j = 0; j < paths2[i].size()-1; ++j) {
+                if(paths2[i].at(j) == paths2[i].at(j+1)) {
+                    check = false;
+                    break;
+                }
+            }
+            if(check)
+                paths3.push_back(paths2[i]);
+        }
+
+        for(auto const& i : paths3) {
+            for(auto const& j : i) 
+                cout << st[j] << ' ';
+
+            cout << endl;
+        }
+        cout << endl;
+
+        int major{};
+        for(int i = 0; i < paths3.size(); ++i) {
+            vector<long> diffs;
+            for(int j = 0; j < paths3[i].size()-1; ++j) {
+                int p1 = st[paths3[i][j+1]];
+                int p2 = st[paths3[i][j]];
+                diffs.push_back(p1 - p2);
+            }
+            int miner = *min_element(begin(diffs), end(diffs));
+            if(miner > major)
+                major = miner;
+        }
+        cout << ts << ' ' << major << endl;
+        out << major << endl;
+    }
+
+    in.close();
+    out.close();
+    return 0;
+}
diff --git a/I_anno/Programmazione_2/coding_contest/tastevin.cpp b/I_anno/Programmazione_2/coding_contest/tastevin.cpp
new file mode 100644
index 0000000..301ebcf
--- /dev/null
+++ b/I_anno/Programmazione_2/coding_contest/tastevin.cpp
@@ -0,0 +1,38 @@
+#include<iostream>
+#include<fstream>
+#include<vector>
+#include<algorithm>
+
+using namespace std;
+
+int main() {
+    ifstream in("input.txt");
+    ofstream out("output.txt");
+
+    for(int ts = 0; ts < 100; ++ts) {
+        int N;
+        in >> N;
+        vector<int> arr(N);
+        for(int i = 0; i < N; ++i) {
+            in >> arr.at(i);
+        }
+
+        vector<int> paths(N, 1);
+
+        for(int i = N-2; i >= 0; --i) {
+            int mx = 0;
+            for(int j = i+2; j < N; ++j) {
+                if(mx < paths[j] && arr[j] >= arr[i]) {
+                    mx = paths[j];
+                }
+            }
+            paths[i] += mx;
+        }
+
+        out << *max_element(begin(paths), end(paths)) << '\n';
+    }
+
+    in.close();
+    out.close();
+    return 0;
+}
diff --git a/I_anno/Programmazione_2/coding_contest/tastevin_paths.cpp b/I_anno/Programmazione_2/coding_contest/tastevin_paths.cpp
new file mode 100644
index 0000000..eb7da54
--- /dev/null
+++ b/I_anno/Programmazione_2/coding_contest/tastevin_paths.cpp
@@ -0,0 +1,67 @@
+// It prints all possible paths
+
+#include<iostream>
+#include<fstream>
+#include<vector>
+
+using namespace std;
+
+int main() {
+    ifstream in("input.txt");
+    ofstream out("output.txt");
+
+    for(int ts = 0; ts < 100; ++ts) {
+        int N;
+        in >> N;
+        vector<int> arr;
+        int e;
+        for(int i = 0; i < N; ++i) {
+            in >> e;
+            arr.push_back(e);
+        }
+
+        int max_value{};
+        int value;
+
+        for(int i = 0; i < N; ++i) {
+            vector<int> tmp;
+            tmp.push_back(i);
+            value = arr[i];
+            for(int j = i+2; j < N; ++j) {
+                if(arr[j] >= value) {
+                    tmp.push_back(j);
+                    value = arr[j];
+                    ++j;
+                }
+            }
+            while(!tmp.empty()) {
+                if(tmp.size() > max_value) {
+                    for(auto const&i : tmp) {
+                        cout << i << ' ';
+                    }
+                    cout << endl;
+                    max_value = tmp.size();
+                }
+                int k = tmp.back();
+                tmp.pop_back();
+                if(tmp.size() > 0)
+                    value = arr[tmp.back()];
+                else
+                    value = arr[k];
+                for(int j = k+1; j < N; ++j) {
+                    if(arr[j] >= value) {
+                        value = arr[j];
+                        tmp.push_back(j);
+                        ++j;
+                    }
+                }
+            }
+        }
+
+        out << max_value << '\n';
+    }
+
+    in.close();
+    out.close();
+    return 0;
+}