Solved new problems from codeforces

68 files changed, 1783 insertions, 0 deletions

diff --git a/codeforces/CormenTheBestFriendOfAMan/main b/codeforces/CormenTheBestFriendOfAMan/main
new file mode 100755
index 0000000..43222bb
--- /dev/null
+++ b/codeforces/CormenTheBestFriendOfAMan/main
diff --git a/codeforces/CormenTheBestFriendOfAMan/main.cpp b/codeforces/CormenTheBestFriendOfAMan/main.cpp
index 25db2b2..4e41dad 100755
--- a/codeforces/CormenTheBestFriendOfAMan/main.cpp
+++ b/codeforces/CormenTheBestFriendOfAMan/main.cpp
@@ -22,10 +22,27 @@ const db PI = acos((db)-1);
 const int dx[4]{1, 0, -1, 0};
 const int dy[4]{0, 1, 0, -1};
 
+// v[i + 1] + v[i] = k
+
 void solve() {
   int n, k;
   cin >> n >> k;
   vi v(n);
+  for (auto &x : v) cin >> x;
+  vi ans(n);
+  int cnt = 0;
+  for (int i = 0; i < n - 1; i++) {
+    if (v[i] + v[i + 1] < k)  {
+      int aw = k - v[i];
+      cnt += aw - v[i + 1];
+      v[i + 1] = aw;
+    }
+  }
+  cout << cnt << '\n';
+  for (auto x : v) {
+    cout << x << ' ';
+  }
+  cout << '\n';
 
 }
 
diff --git a/codeforces/CormenTheBestFriendOfAMan/main_input0.txt b/codeforces/CormenTheBestFriendOfAMan/main_input0.txt
new file mode 100644
index 0000000..6642156
--- /dev/null
+++ b/codeforces/CormenTheBestFriendOfAMan/main_input0.txt
@@ -0,0 +1,2 @@
+3 5
+2 0 1
diff --git a/codeforces/CormenTheBestFriendOfAMan/main_input1.txt b/codeforces/CormenTheBestFriendOfAMan/main_input1.txt
new file mode 100644
index 0000000..2e3b056
--- /dev/null
+++ b/codeforces/CormenTheBestFriendOfAMan/main_input1.txt
@@ -0,0 +1,2 @@
+3 1
+0 0 0
diff --git a/codeforces/CormenTheBestFriendOfAMan/main_input2.txt b/codeforces/CormenTheBestFriendOfAMan/main_input2.txt
new file mode 100644
index 0000000..d0085cf
--- /dev/null
+++ b/codeforces/CormenTheBestFriendOfAMan/main_input2.txt
@@ -0,0 +1,2 @@
+4 6
+2 4 3 5
diff --git a/codeforces/CormenTheBestFriendOfAMan/main_output0.txt b/codeforces/CormenTheBestFriendOfAMan/main_output0.txt
new file mode 100644
index 0000000..0639b2b
--- /dev/null
+++ b/codeforces/CormenTheBestFriendOfAMan/main_output0.txt
@@ -0,0 +1,2 @@
+4
+2 3 2
diff --git a/codeforces/CormenTheBestFriendOfAMan/main_output1.txt b/codeforces/CormenTheBestFriendOfAMan/main_output1.txt
new file mode 100644
index 0000000..4fd2a3f
--- /dev/null
+++ b/codeforces/CormenTheBestFriendOfAMan/main_output1.txt
@@ -0,0 +1,2 @@
+1
+0 1 0
diff --git a/codeforces/CormenTheBestFriendOfAMan/main_output2.txt b/codeforces/CormenTheBestFriendOfAMan/main_output2.txt
new file mode 100644
index 0000000..9b66e1b
--- /dev/null
+++ b/codeforces/CormenTheBestFriendOfAMan/main_output2.txt
@@ -0,0 +1,2 @@
+0
+2 4 3 5
diff --git a/codeforces/EqualizeByDivide/main b/codeforces/EqualizeByDivide/main
new file mode 100755
index 0000000..2adc6ce
--- /dev/null
+++ b/codeforces/EqualizeByDivide/main
diff --git a/codeforces/EqualizeByDivide/main.cpp b/codeforces/EqualizeByDivide/main.cpp
new file mode 100755
index 0000000..1c22f4e
--- /dev/null
+++ b/codeforces/EqualizeByDivide/main.cpp
@@ -0,0 +1,117 @@
+#include<bits/stdc++.h>
+using namespace std;
+
+using ll = long long;
+using pii = pair<int, int>;
+using vpi = vector<pii>;
+using vi = vector<int>;
+using vll = vector<long long>;
+using mpii = map<int, int>;
+using mpll = map<ll, ll>;
+using db = long double;
+
+#define pb push_back 
+#define all(x) (x).begin(), (x).end()
+#define rall(x) (x).rbegin(), (x).rend()
+#define lb lower_bound
+#define ub upper_bound
+
+// #define ceil(a, b) (a + b - 1 / b)
+
+const int MOD = (int)1e9 + 7;
+const db PI = acos((db)-1);
+const int dx[4]{1, 0, -1, 0};
+const int dy[4]{0, 1, 0, -1};
+
+//pretty printing
+template<typename K, typename V>
+void printm(const map<K, V> &mp) {
+  cerr << "{" << endl;
+  for (auto p : mp) {
+    cerr << "  { " << p.first << " : " << p.second << " }\n";
+  }
+  cerr << "}" << endl;
+}
+template<typename T>
+void printv(const vector<T> &v) {
+  cerr << "[";
+  for (int i = 0; i < v.size(); i++) {
+    if (i == v.size() - 1) {
+      cerr << v[i];
+    } else {
+      cerr << v[i] << ", ";
+    }
+  }
+  cerr << "]\n";
+}
+
+template<typename T>
+void printvv(const vector<vector<T>> &v) {
+  cerr << "[\n";
+  for (auto &vec : v) {
+    cout << "  ";
+    printv(vec);
+  }
+  cerr << "]\n";
+}
+void print() {
+  cerr << "\n";
+}
+
+template<typename T, typename... TS>
+void print(T val, TS... vals) {
+  cerr << val << " ";
+  print(vals...);
+}
+
+
+
+/* stuff you should look for:
+  ---------------------------
+   * special cases (n=1?)
+   * int overflow, array bounds
+   * do smth instead of nothing and stay organized
+   * WRITE STUFF DOWN
+   * DON'T GET STUCK ON ONE APPROACH
+ */
+
+
+void solve() {
+  int n;
+  cin >> n;
+  vi v(n);
+  for (auto &x : v) cin >> x;
+  auto isEqual = [&](vi &a) {
+    return count(all(a), a[0]) == a.size();
+  };
+
+  int ans = 0;
+  vector<pii> p;
+  while (!isEqual(v)) {
+    if (ans > n * 30) {cout << -1 << '\n'; return;};
+    auto imx = max_element(all(v)) - v.begin();
+    auto imn = min_element(all(v)) - v.begin();
+    int mx = *max_element(all(v));
+    int mn = *min_element(all(v));
+    p.push_back({imx + 1, imn + 1});
+    v[imx] = ceil((double)mx / mn);
+    ans++;
+  }
+  cout << ans << '\n';
+  for (int i = 0; i < ans; i++) {
+    cout << p[i].first << ' ' << p[i].second << '\n';
+  }
+
+}
+
+int main () {
+  ios_base::sync_with_stdio(false);
+  cin.tie(NULL);
+  int tt;
+  cin >> tt;
+  while(tt--) {
+    solve();
+  }
+}
+
+
diff --git a/codeforces/EqualizeByDivide/main_input0.txt b/codeforces/EqualizeByDivide/main_input0.txt
new file mode 100644
index 0000000..5d32c10
--- /dev/null
+++ b/codeforces/EqualizeByDivide/main_input0.txt
@@ -0,0 +1,21 @@
+10
+1
+100
+3
+1 1 1
+2
+2 1
+2
+5 5
+3
+4 3 2
+4
+3 3 4 4
+2
+2 100
+5
+5 3 6 7 8
+6
+3 3 80 3 8 3
+4
+19 40 19 55
diff --git a/codeforces/EqualizeByDivide/main_output0.txt b/codeforces/EqualizeByDivide/main_output0.txt
new file mode 100644
index 0000000..642f8e4
--- /dev/null
+++ b/codeforces/EqualizeByDivide/main_output0.txt
@@ -0,0 +1,43 @@
+0
+0
+-1
+0
+2
+1 3
+2 1
+4
+3 1
+4 2
+1 3
+2 4
+6
+2 1
+2 1
+2 1
+2 1
+2 1
+2 1
+8
+5 2
+4 2
+3 2
+1 3
+1 3
+2 1
+4 1
+5 1
+4
+5 1
+3 1
+3 1
+3 1
+9
+4 2
+2 1
+1 2
+1 2
+3 2
+3 2
+1 4
+2 4
+3 4
diff --git a/codeforces/IdealPoint/main b/codeforces/IdealPoint/main
new file mode 100755
index 0000000..cdd18a8
--- /dev/null
+++ b/codeforces/IdealPoint/main
diff --git a/codeforces/IdealPoint/main.cpp b/codeforces/IdealPoint/main.cpp
new file mode 100755
index 0000000..fdd9d35
--- /dev/null
+++ b/codeforces/IdealPoint/main.cpp
@@ -0,0 +1,116 @@
+#include<bits/stdc++.h>
+using namespace std;
+
+using ll = long long;
+using pii = pair<int, int>;
+using vpi = vector<pii>;
+using vi = vector<int>;
+using vll = vector<long long>;
+using mpii = map<int, int>;
+using mpll = map<ll, ll>;
+using db = long double;
+
+#define pb push_back 
+#define all(x) (x).begin(), (x).end()
+#define rall(x) (x).rbegin(), (x).rend()
+#define lb lower_bound
+#define ub upper_bound
+
+#define ceil(a, b) (a + b - 1 / b)
+
+const int MOD = (int)1e9 + 7;
+const db PI = acos((db)-1);
+const int dx[4]{1, 0, -1, 0};
+const int dy[4]{0, 1, 0, -1};
+
+//pretty printing
+template<typename K, typename V>
+void printm(const map<K, V> &mp) {
+  cerr << "{" << endl;
+  for (auto p : mp) {
+    cerr << "  { " << p.first << " : " << p.second << " }\n";
+  }
+  cerr << "}" << endl;
+}
+template<typename T>
+void printv(const vector<T> &v) {
+  cerr << "[";
+  for (int i = 0; i < v.size(); i++) {
+    if (i == v.size() - 1) {
+      cerr << v[i];
+    } else {
+      cerr << v[i] << ", ";
+    }
+  }
+  cerr << "]\n";
+}
+
+template<typename T>
+void printvv(const vector<vector<T>> &v) {
+  cerr << "[\n";
+  for (auto &vec : v) {
+    cout << "  ";
+    printv(vec);
+  }
+  cerr << "]\n";
+}
+void print() {
+  cerr << "\n";
+}
+
+template<typename T, typename... TS>
+void print(T val, TS... vals) {
+  cerr << val << " ";
+  print(vals...);
+}
+
+
+
+/* stuff you should look for:
+  ---------------------------
+   * special cases (n=1?)
+   * int overflow, array bounds
+   * do smth instead of nothing and stay organized
+   * WRITE STUFF DOWN
+   * DON'T GET STUCK ON ONE APPROACH
+ */
+
+void add(vi &v, int l, int r) {
+  for (int i = l; i <= r; i++) {
+    v[i]++;
+  }
+}
+
+
+void solve() {
+  int n, k;
+  cin >> n >> k;
+  int cnt = 0;
+  vi v(51);
+  for (int i = 0; i < n; i++) {
+    int l, r;
+    cin >> l >> r;
+    if (k >= l && k <= r) {
+      add(v, l, r);
+    }
+  }
+  for (int i = 1; i < v.size(); i++) {
+    if (v[k] <= v[i] && i != k) {
+      cout << "NO\n";
+      return;
+    }
+  }
+  cout << "YES\n";
+}
+
+int main () {
+  ios_base::sync_with_stdio(false);
+  cin.tie(NULL);
+  int tt;
+  cin >> tt;
+  while(tt--) {
+    solve();
+  }
+}
+
+
diff --git a/codeforces/IdealPoint/main_input0.txt b/codeforces/IdealPoint/main_input0.txt
new file mode 100644
index 0000000..284f7f3
--- /dev/null
+++ b/codeforces/IdealPoint/main_input0.txt
@@ -0,0 +1,15 @@
+4
+4 3
+1 3
+7 9
+2 5
+3 6
+2 9
+1 4
+3 7
+1 3
+2 4
+3 5
+1 4
+6 7
+5 5
diff --git a/codeforces/IdealPoint/main_output0.txt b/codeforces/IdealPoint/main_output0.txt
new file mode 100644
index 0000000..c8cd351
--- /dev/null
+++ b/codeforces/IdealPoint/main_output0.txt
@@ -0,0 +1,4 @@
+YES
+NO
+NO
+YES
diff --git a/codeforces/MexMaster/main b/codeforces/MexMaster/main
new file mode 100755
index 0000000..a0d3157
--- /dev/null
+++ b/codeforces/MexMaster/main
diff --git a/codeforces/MexMaster/main.cpp b/codeforces/MexMaster/main.cpp
new file mode 100755
index 0000000..92727d0
--- /dev/null
+++ b/codeforces/MexMaster/main.cpp
@@ -0,0 +1,153 @@
+#include<bits/stdc++.h>
+using namespace std;
+
+using ll = long long;
+using pii = pair<int, int>;
+using vpi = vector<pii>;
+using vi = vector<int>;
+using vll = vector<long long>;
+using mpii = map<int, int>;
+using mpll = map<ll, ll>;
+using db = long double;
+
+#define pb push_back 
+#define all(x) (x).begin(), (x).end()
+#define rall(x) (x).rbegin(), (x).rend()
+#define lb lower_bound
+#define ub upper_bound
+#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())
+#define ceil(a, b) (((a) + (b) - 1) / (b))
+
+const int MOD = (int)1e9 + 7;
+const db PI = acos((db)-1);
+const int dx[4]{1, 0, -1, 0};
+const int dy[4]{0, 1, 0, -1};
+
+template<typename K, typename V> ostream& operator<<(ostream& os, const pair<K, V>& p);
+template<typename T> ostream& operator<<(ostream& os, const vector<T>& vec);
+template<typename K, typename V> ostream& operator<<(ostream& os, const map<K, V>& m);
+template<typename K, typename V> ostream& operator<<(ostream& os, const unordered_map<K, V>& m);
+template<typename T> ostream& operator<<(ostream& os, const set<T>& s);
+template<typename T> ostream& operator<<(ostream& os, const unordered_set<T>& s);
+
+template<typename K, typename V>
+ostream& operator<<(ostream& os, const pair<K, V>& p) {
+  os << "(" << p.first << ", " << p.second << ")";
+  return os;
+}
+
+template<typename T>
+ostream& operator<<(ostream& os, const vector<T>& vec) {
+  os << "{";
+  for (size_t i = 0; i < vec.size(); ++i) {
+    if (i > 0) os << ", ";
+    os << vec[i];
+  }
+  os << "}";
+  return os;
+}
+
+
+template<typename K, typename V>
+ostream& operator<<(ostream& os, const map<K, V>& m) {
+  os << "{";
+  for (const auto& p : m) {
+    os << p.first << ": " << p.second << ", ";
+  }
+  os << "}";
+  return os;
+}
+
+template<typename K, typename V>
+ostream& operator<<(ostream& os, const unordered_map<K, V>& m) {
+  os << "{";
+  for (const auto& p : m) {
+    os << p.first << ": " << p.second << ", ";
+  }
+  os << "}";
+  return os;
+}
+
+template<typename T>
+ostream& operator<<(ostream& os, const set<T>& s) {
+  int i = 0;
+  os << "{";
+  for (const auto& e : s) {
+    if (i > 0) os << ", ";
+    os << e;
+    i++;
+  }
+  os << "}";
+  return os;
+}
+
+template<typename T>
+ostream& operator<<(ostream& os, const unordered_set<T>& s) {
+  int i = 0;
+  os << "{";
+  for (const auto& e : s) {
+    if (i > 0) os << ", ";
+    os << e;
+    i++;
+  }
+  os << "}";
+  return os;
+}
+
+void print() {
+  cerr << "\n";
+}
+
+template<typename T, typename... TS>
+void print(T val, TS... vals) {
+  cerr << val << " ";
+  print(vals...);
+}
+
+
+
+/* stuff you should look for:
+  ---------------------------
+   * special cases (n=1?)
+   * int overflow, array bounds
+   * do smth instead of nothing and stay organized
+   * WRITE STUFF DOWN
+   * DON'T GET STUCK ON ONE APPROACH
+ */
+
+// 1 1 0 0 0 0
+// 1 1 0 0 0 0
+
+void solve() {
+  int n;
+  cin >> n;
+  vi v(n);
+  int zrs = 0;
+  int ons = 0;
+  for (auto &x : v) {
+    cin >> x;
+    zrs += (x == 0);
+    ons += (x == 1);
+  }
+  if (zrs <= ceil(n, 2)) {
+    cout << 0 << '\n';
+  } else {
+    if (ons + zrs == n && ons != 0) {
+      cout << 2 << '\n';
+    } else {
+      cout << 1 << '\n';
+    }
+  }
+}
+
+int main () {
+  ios_base::sync_with_stdio(false);
+  cin.tie(NULL);
+  int tt;
+  cin >> tt;
+  while(tt--) {
+    solve();
+  }
+}
+
+
diff --git a/codeforces/MexMaster/main_input0.txt b/codeforces/MexMaster/main_input0.txt
new file mode 100644
index 0000000..62587c3
--- /dev/null
+++ b/codeforces/MexMaster/main_input0.txt
@@ -0,0 +1,7 @@
+3
+2
+0 0
+3
+0 0 1
+8
+1 0 0 0 2 0 3 0
diff --git a/codeforces/MexMaster/main_output0.txt b/codeforces/MexMaster/main_output0.txt
new file mode 100644
index 0000000..16db301
--- /dev/null
+++ b/