summaryrefslogtreecommitdiff
path: root/I_anno/Programmazione_2/coding_contest
diff options
context:
space:
mode:
authorSanto Cariotti <dcariotti24@gmail.com>2020-05-29 17:37:43 +0200
committerSanto Cariotti <dcariotti24@gmail.com>2020-05-29 17:37:43 +0200
commitc1b13da17b2d20bdb9392f0e390df771772f0020 (patch)
tree20f266a590a4bb36738355f54fd48f4229b58b05 /I_anno/Programmazione_2/coding_contest
parentbc8b5b446a6a2d37bae82e7ad20e31e1439a2f0b (diff)
chore: order in coding contest folder
Diffstat (limited to 'I_anno/Programmazione_2/coding_contest')
-rw-r--r--I_anno/Programmazione_2/coding_contest/dolcetti.cpp51
-rw-r--r--I_anno/Programmazione_2/coding_contest/gita.cpp46
-rw-r--r--I_anno/Programmazione_2/coding_contest/gribaudo.cpp47
-rw-r--r--I_anno/Programmazione_2/coding_contest/gualtieri.cpp46
-rw-r--r--I_anno/Programmazione_2/coding_contest/ladri.cpp53
-rw-r--r--I_anno/Programmazione_2/coding_contest/pizzini.cpp48
-rw-r--r--I_anno/Programmazione_2/coding_contest/scheletri.cpp56
-rw-r--r--I_anno/Programmazione_2/coding_contest/stazioni.cpp82
-rw-r--r--I_anno/Programmazione_2/coding_contest/tastevin.cpp38
-rw-r--r--I_anno/Programmazione_2/coding_contest/tastevin_paths.cpp67
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;
+}