From c1bbcb6c2a6d02a4ac06d3c41afcfc51993ec1d3 Mon Sep 17 00:00:00 2001 From: omagdy7 Date: Thu, 14 Mar 2024 00:22:45 +0200 Subject: Solved 3 problems in the last Div3 --- codeforces/HalloumiBoxes/main.rs | 32 +++++++++ codeforces/HalloumiBoxes/rust-project.json | 11 +++ codeforces/MovingChips/main.cpp | 104 +++++++++++++++++++++++++++++ codeforces/MovingChips/main_input0.txt | 11 +++ codeforces/MovingChips/main_output0.txt | 5 ++ codeforces/TurtleMath/main.cpp | 82 +++++++++++++++++++++++ 6 files changed, 245 insertions(+) create mode 100644 codeforces/HalloumiBoxes/main.rs create mode 100644 codeforces/HalloumiBoxes/rust-project.json create mode 100755 codeforces/MovingChips/main.cpp create mode 100644 codeforces/MovingChips/main_input0.txt create mode 100644 codeforces/MovingChips/main_output0.txt create mode 100755 codeforces/TurtleMath/main.cpp (limited to 'codeforces') diff --git a/codeforces/HalloumiBoxes/main.rs b/codeforces/HalloumiBoxes/main.rs new file mode 100644 index 0000000..cbc73cd --- /dev/null +++ b/codeforces/HalloumiBoxes/main.rs @@ -0,0 +1,32 @@ +#[allow(dead_code)] +fn read() -> T { + let mut s = String::new(); + std::io::stdin().read_line(&mut s).ok(); + s.trim().parse().ok().unwrap() +} + +#[allow(dead_code)] +fn read_vec() -> Vec { + read::() + .split_whitespace() + .map(|e| e.parse().ok().unwrap()) + .collect() +} + +#[allow(dead_code)] +fn read_mat(n: u32) -> Vec> { + (0..n).map(|_| read_vec()).collect() +} + +fn solve() { + let (k, n) = (read::(), read::()); + let mut v = read_vec::(); +} + +fn main() { + let mut tt = read::(); + while tt > 0 { + solve(); + tt -= 1; + } +} diff --git a/codeforces/HalloumiBoxes/rust-project.json b/codeforces/HalloumiBoxes/rust-project.json new file mode 100644 index 0000000..a195582 --- /dev/null +++ b/codeforces/HalloumiBoxes/rust-project.json @@ -0,0 +1,11 @@ +{ + "sysroot": "/home/omar/.rustup/toolchains/stable-x86_64-unknown-linux-gnu", + "sysroot_src": "/home/omar/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/", + "crates": [ + { + "root_module": "main.rs", + "edition": "2021", + "deps": [] + } + ] +} diff --git a/codeforces/MovingChips/main.cpp b/codeforces/MovingChips/main.cpp new file mode 100755 index 0000000..f847d53 --- /dev/null +++ b/codeforces/MovingChips/main.cpp @@ -0,0 +1,104 @@ +#include +#include + +using namespace std; + +using ll = long long; +using pii = pair; +using vpii = vector; +using vi = vector; +using vll = vector; +using mpii = map; +using mpll = map; +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}; + +#ifdef LOCAL +#include "debug.h" +#else +#define dbg(...) 42 +#endif + +/* 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 + */ + +bool isChip(vi v) { + v.resize(unique(all(v)) - v.begin()); + int n = v.size(); + if (n == 2) { + return true; + } else if (n == 1 && v[0] == 1) { + return true; + } else if (n == 3 && v[0] == 0 && v[1] == 1 && v[2] == 0) { + return true; + } else { + return false; + } +} + +int rfind(vi &v) { + int n = v.size(); + for (int i = n - 1; i >= 0; --i) { + if (v[i] == 1) { + return i; + } + } + return -1; +} + +int helper(vi &v, int idx) { + int n = v.size(); + for (int i = idx; i >= 0; --i) { + if (v[i] == 0) { + return i; + } + } + return -1; +} + +void solve() { + int n; + cin >> n; + vi v(n); + for (auto &x : v) { + cin >> x; + } + int cnt = 0; + while (!isChip(v)) { + auto last_one = rfind(v); + auto first_zero_before_last_one = helper(v, last_one); + swap(v[last_one], v[first_zero_before_last_one]); + cnt++; + } + cout << cnt << '\n'; +} + +int main() { + ios_base::sync_with_stdio(false); + cin.tie(NULL); + int tt; + cin >> tt; + while (tt--) { + solve(); + } +} diff --git a/codeforces/MovingChips/main_input0.txt b/codeforces/MovingChips/main_input0.txt new file mode 100644 index 0000000..5945cde --- /dev/null +++ b/codeforces/MovingChips/main_input0.txt @@ -0,0 +1,11 @@ +5 +8 +0 1 1 1 0 1 1 0 +6 +0 1 0 0 0 0 +6 +1 1 1 1 1 1 +5 +1 0 1 0 1 +9 +0 1 1 0 0 0 1 1 0 diff --git a/codeforces/MovingChips/main_output0.txt b/codeforces/MovingChips/main_output0.txt new file mode 100644 index 0000000..dff77c1 --- /dev/null +++ b/codeforces/MovingChips/main_output0.txt @@ -0,0 +1,5 @@ +1 +0 +0 +2 +3 diff --git a/codeforces/TurtleMath/main.cpp b/codeforces/TurtleMath/main.cpp new file mode 100755 index 0000000..c602443 --- /dev/null +++ b/codeforces/TurtleMath/main.cpp @@ -0,0 +1,82 @@ +#include + +using namespace std; + +using ll = long long; +using pii = pair; +using vpii = vector; +using vi = vector; +using vll = vector; +using mpii = map; +using mpll = map; +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}; + +#ifdef LOCAL +#include "debug.h" +#else +#define dbg(...) 42 +#endif + +/* 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 + */ + +set st1; + +void solve() { + int n; + cin >> n; + vector v(n); + long long sum = 0; + for (auto &x : v) { + cin >> x; + sum += x; + } + if (sum % 3 == 0) { + cout << 0 << '\n'; + return; + } else { + if (sum % 3 == 1) { + for (int i = 0; i < n; ++i) { + if (st1.count(v[i])) { + cout << 1 << '\n'; + return; + } + } + } + } + cout << 3 - (sum % 3) << '\n'; +} + +int main() { + for (int i = 0; i < 1e5; i++) { + st1.insert(1 + i * 3); + } + ios_base::sync_with_stdio(false); + cin.tie(NULL); + int tt; + cin >> tt; + while (tt--) { + solve(); + } +} -- cgit v1.2.3