commit 05990dee3ecdc3d232b96f48ed1789e551a94e66 parent ceda9a1984b2960c6761205edc8ea1d7c6fecded Author: Andrew Laack <andrew@laack.co> Date: Sun, 15 Nov 2026 09:38:45 -0600 Div 2 contest, 3 problems Diffstat:
26 files changed, 339 insertions(+), 1 deletion(-)
diff --git a/comp/r1135/a/ex1.in b/comp/r1135/a/ex1.in @@ -0,0 +1,4 @@ +3 +1 +4 +5 diff --git a/comp/r1135/a/ex2.in b/comp/r1135/a/ex2.in diff --git a/comp/r1135/a/main.cpp b/comp/r1135/a/main.cpp @@ -0,0 +1,37 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +using namespace std; + +// don't we just have to ensure the first number is a non-prime? + +int main() { + + int testCases, n; + cin >> testCases; + + for(int z = 0; z < testCases; ++z) { + cin >> n; + if (n <= 3) { + cout << -1 << endl; + continue; + } + else { + cout << 4 << " "; + for(int i = 2; i <= n; ++i) { + if(i == 4) { + cout << 1 << " "; + continue; + } + cout << i << " "; + } + } + cout << endl; + } +} diff --git a/comp/r1135/a/problem.txt b/comp/r1135/a/problem.txt @@ -0,0 +1,2 @@ +- integer n +- make permutation p of length n such that i * p_i is composite diff --git a/comp/r1135/b/ex1.in b/comp/r1135/b/ex1.in @@ -0,0 +1,9 @@ +4 +1 1 +0 +4 4 +1001 +5 1 +11111 +7 2 +1101001 diff --git a/comp/r1135/b/ex2.in b/comp/r1135/b/ex2.in diff --git a/comp/r1135/b/main.cpp b/comp/r1135/b/main.cpp @@ -0,0 +1,69 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +using namespace std; + +// k defines how many characters can be swapped at the start +// + +int main() { + + int testCases, n, k; + string s = ""; + cin >> testCases; + + for(int z = 0; z < testCases; ++z) { + cin >> n; + cin >> k; + cin >> s; + + int zeroCount = 0; + int oneCount = 0; + for(int i = 0; i < n; ++i) { + if(s[i] == '0') { + zeroCount += 1; + } else { + oneCount += 1; + } + } + + int flipped = 0; + + if(zeroCount > oneCount) { + for(int i = 0; i < n && flipped < k; ++i) { + if(s[i] == '1') { + s[i] = '0'; + flipped += 1; + zeroCount += 1; + oneCount -= 1; + } + } + } else { + for(int i = 0; i < n && flipped < k; ++i) { + if(s[i] == '0') { + s[i] = '1'; + flipped += 1; + zeroCount -= 1; + oneCount += 1; + } + } + } + + long long res = 1; + + for(int i = 1; i <= zeroCount; ++i) { + res += (zeroCount + 1) - i; + } + for(int i = 1; i <= oneCount; ++i) { + res += (oneCount + 1) - i; + } + cout << res << '\n'; + + } +} diff --git a/comp/r1135/b/problem.txt b/comp/r1135/b/problem.txt diff --git a/comp/r1135/c/ex1.in b/comp/r1135/c/ex1.in @@ -0,0 +1,11 @@ +5 +3 +2 2 1 +2 +1000000000 1 +4 +6 7 2 2 +3 +3 4 2 +1 +1 diff --git a/comp/r1135/c/ex2.in b/comp/r1135/c/ex2.in diff --git a/comp/r1135/c/main.cpp b/comp/r1135/c/main.cpp @@ -0,0 +1,105 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +using namespace std; + +#define MV 1000000007LL + +ll pw(ll base, ll exp) { + + base %= MV; + long long result = 1; + + while (exp > 0) { + if (exp & 1) { + result = result * base % MV; + } + + base = base * base % MV; + exp = (exp >> 1); + } + return result; +} + +int main() { + + int testCases; + cin >> testCases; + + // array a of length n + // one operation you may: + // replace the unique largest element in a with a strictly smaller positive value + // this can only be done when there's a unique max element of a + // find the number of unique arrays that can be made by performing the above 0 or more times + + // output mod 10^9 + 7 + + // 3 + // 2 2 1 + + // we can't perform any ops because 2 isn't unique + // 1 + + // 2 + // 1000000000 1 + // we can bring 1000000000 down to any value >= 1 or not change it so + // number of values = 1000000000 + + // 6 7 2 2 + // we may bring 7 down to: + // 6 + // 6622 (done) + // 5 + // 6522 + // 5522 + // 4522 + // 3522 + // 2522 + // 1522 + // 4 + // 6422 + // 3 + // 6322 + // 2 + // 6222 + // 1 + // 6122 + + // from a given state: + // bring max to same position as the value less than current + // max - max_2 + // if we bring it to any value from (1 -> max_2-1) then + + for(int z = 0; z < testCases; ++z) { + vector<long long> ls = {}; + int n = 0; + cin >> n; + + for(int i = 0; i < n; ++i) { + int current = 0; + cin >> current; + ls.push_back(current); + } + + sort(ls.begin(), ls.end()); + long long res = 1; + for (int k = 1; k <= n; ++k) { + long long current = ls[n - k]; + if (k >= 2 && ls[n - k + 1] == current) { + break; + } + if (k < n && ls[n - k - 1] == current) { + break; + } + res = (res + pw(current - 1, k)) % MV; + } + cout << res << "\n"; + + } +} diff --git a/comp/r1135/c/problem.txt b/comp/r1135/c/problem.txt diff --git a/comp/r1135/d/ex1.in b/comp/r1135/d/ex1.in diff --git a/comp/r1135/d/ex2.in b/comp/r1135/d/ex2.in diff --git a/comp/r1135/d/main.cpp b/comp/r1135/d/main.cpp @@ -0,0 +1,20 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +using namespace std; + +int main() { + + int testCases; + cin >> testCases; + + for(int z = 0; z < testCases; ++z) { + + } +} diff --git a/comp/r1135/d/problem.txt b/comp/r1135/d/problem.txt diff --git a/comp/r1135/e/ex1.in b/comp/r1135/e/ex1.in diff --git a/comp/r1135/e/ex2.in b/comp/r1135/e/ex2.in diff --git a/comp/r1135/e/main.cpp b/comp/r1135/e/main.cpp @@ -0,0 +1,20 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +using namespace std; + +int main() { + + int testCases; + cin >> testCases; + + for(int z = 0; z < testCases; ++z) { + + } +} diff --git a/comp/r1135/e/problem.txt b/comp/r1135/e/problem.txt diff --git a/comp/r1135/f/ex1.in b/comp/r1135/f/ex1.in diff --git a/comp/r1135/f/ex2.in b/comp/r1135/f/ex2.in diff --git a/comp/r1135/f/main.cpp b/comp/r1135/f/main.cpp @@ -0,0 +1,20 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +using namespace std; + +int main() { + + int testCases; + cin >> testCases; + + for(int z = 0; z < testCases; ++z) { + + } +} diff --git a/comp/r1135/f/problem.txt b/comp/r1135/f/problem.txt diff --git a/comp/replace-and-compress/ex2.in b/comp/replace-and-compress/ex2.in @@ -1,2 +1,3 @@ -1 +2 001011010 +001010101011111010101000010101011101011011010101001011010001011010001011010001011010001011010001011010 diff --git a/comp/replace-and-compress/naive.ml b/comp/replace-and-compress/naive.ml @@ -0,0 +1,40 @@ +let readInt () = + Scanf.scanf " %d" (fun x->x) + +let readString () = + Scanf.scanf " %s" (fun x->x) + +let compress s = + let buf = Buffer.create (String.length s) in + String.iteri (fun i c -> if i = 0 || s.[i-1] <> c then Buffer.add_char buf c) s; + Buffer.contents buf + +let allFlips s = + + let compressedTbl = Hashtbl.create 10 in + let () = Hashtbl.replace compressedTbl (compress s) () in + + let rec acc idx = + if idx == String.length s - 1 then + () + else + let oldChar = s.[idx] in + let newChar = (if oldChar = '0' then '1' else '0') in + let swapped = String.mapi (fun i c -> if i = idx then newChar else c) s in + Hashtbl.replace compressedTbl (compress swapped) (); + acc (idx+1) + in + acc 1; Hashtbl.length compressedTbl + +let handleTestCase () = + let st = readString () + in + allFlips st + +let () = + let testCases = readInt () in + let rec acc idx = + if idx = testCases then () + else (print_int (handleTestCase ()); print_newline (); acc (idx+1)) + in + acc 0