algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

commit d54dabb31cf1562412a91723331e1fb805fe2ecf
parent 519ca1294599819069e45a36d3ec783be8107548
Author: Andrew Laack <andrew@laack.co>
Date:   Mon,  9 Nov 2026 19:15:08 -0600

A few easy problems to prep for div4 contest

Diffstat:
Acomp/perfect-sandwiches/ex1.in | 4++++
Acomp/perfect-sandwiches/main.cpp | 29+++++++++++++++++++++++++++++
Acomp/perfect-sandwiches/problem.txt | 83+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/the-projections-of-paco/ex1.in | 11+++++++++++
Acomp/the-projections-of-paco/main.cpp | 73+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/wip/tiles/main.cpp | 13+++++++++++++
Acomp/wip/tiles/problem.txt | 33+++++++++++++++++++++++++++++++++
7 files changed, 246 insertions(+), 0 deletions(-)

diff --git a/comp/perfect-sandwiches/ex1.in b/comp/perfect-sandwiches/ex1.in @@ -0,0 +1,4 @@ +3 +6 4 +5 1 +4 5 diff --git a/comp/perfect-sandwiches/main.cpp b/comp/perfect-sandwiches/main.cpp @@ -0,0 +1,29 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +using namespace std; + +int main() { + // boilerplate loading + int ch, sa, tc; + cin >> tc; + for(int z = 0; z < tc ; ++z) { + cin >> ch; + cin >> sa; + + int delta = ch - sa; + int ans = std::min(delta, sa); + if(delta == 0 || sa >= ch) { + ans = -1; + } + + cout << ans << endl; + } + +} diff --git a/comp/perfect-sandwiches/problem.txt b/comp/perfect-sandwiches/problem.txt @@ -0,0 +1,83 @@ +Monocarp has a + slices of cheese and b + slices of sausage. He wants to make the maximum possible number of sandwiches for his friends from them. + +Monocarp is very thrifty, so he must use all a + slices of cheese and all b + slices of sausage without any leftovers to make the sandwiches. In addition, he has the following rules for making sandwiches: + +each sandwich must contain at least one slice of cheese and at least one slice of sausage; +each of the a + slices of cheese and each of the b + slices of sausage must be placed on exactly one sandwich; +for each sandwich, the number of slices of cheese must be strictly greater than the number of slices of sausage. +Help Monocarp determine the maximum number of sandwiches he can make, or determine that it is impossible to distribute all slices according to these rules. + +Input +The first line contains an integer t + (1≤t≤104 +) — the number of test cases. + +The only line of each test case contains two integers a + and b + (1≤a,b≤100 +) — the number of slices of cheese and sausage, respectively. + +--- + +- a slices cheese +- b slices sausage +- make max sandwiches + +- each sandwich must contain at least one slice of cheese and at least one slice of sausage; +- each of the a slices of cheese and each of the b slices of sausage must be placed on exactly one sandwich; +- for each sandwich, the number of slices of cheese must be strictly greater than the number of slices of sausage. + +--- + +- min cheese == 2 +- min sausage == 1 +- cheese must be > sausage + +--- + +6 4 + +ch == 6 +sa == 4 + +2 ch +2 ch +1 sa +1 sa + +rem: 2 ch, 2 sa + +since have to use all, must distribute on priors. + +--- + +5 1 + +5 ch, 1 sa + +res: 1 + +--- + +4 5 + +-1 + +--- + +prior = 0 +if ch <= sa: + return prior -1 +else: + (ch > sa) + ch -= 2 + sa -= 1 + if both fail, then return prior + prior += 1 + goto if diff --git a/comp/the-projections-of-paco/ex1.in b/comp/the-projections-of-paco/ex1.in @@ -0,0 +1,11 @@ +5 +1 +3 +2 +2 5 +3 +2 7 1 +4 +-3 0 -3 0 +1 +0 diff --git a/comp/the-projections-of-paco/main.cpp b/comp/the-projections-of-paco/main.cpp @@ -0,0 +1,73 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +using namespace std; + +// n integers +// a_1... rep position +// start at 0 + +// choose p + // token is reflected over + // p, a_1, ... a_n + +// end at 0 + +// 1 +// 3 + +// 0 -> 6 +// 0 -> 6 -> 0 + +// this is done with p == 3 + +// 2 +// 2 5 + +// 0 -> 4 -> 6 + +// 0 -> 12 -> -4 -> ... + + +// prior to last step, must be at 10 +// to get to 10 from 2 we must be at -6 +// to get to -6 from 0 we must have -3 +// so we have -3 + +// 3 +// 2 7 1 +// 4 +// -3 0 -3 0 +// 1 +// 0 + + +int main() { + int testCases, current, n; + cin >> testCases; + + for(int z = 0; z < testCases; ++z) { + + cin >> n; + vector<int> ls {}; + + for(int i = 0; i < n; ++i) { + cin >> current; + ls.push_back(current); + } + + int target = 0; + + for(int i = ls.size()-1; i >= 0; --i) { + int pivot = ls[i]; + target = ((pivot - target) * 2) + target; + } + cout << target / 2 << endl; + } +} diff --git a/comp/wip/tiles/main.cpp b/comp/wip/tiles/main.cpp @@ -0,0 +1,13 @@ +#include <iostream> +using namespace std; +int main() { + // is the answer just (w x h) ** 2? + + long long w; + long long h; + + cin >> w; + cin >> h; + + cout << ((w * h) % 998244353) * ((w * h) % 998244353) % 998244353 << endl; +} diff --git a/comp/wip/tiles/problem.txt b/comp/wip/tiles/problem.txt @@ -0,0 +1,33 @@ +C. Tiles +time limit per test1 second +memory limit per test256 megabytes +Bob is decorating his kitchen, more precisely, the floor. He has found a prime candidate for the tiles he will use. They come in a simple form factor — a square tile that is diagonally split into white and black part as depicted in the figure below. + + +The dimension of this tile is perfect for this kitchen, as he will need exactly w×h + tiles without any scraps. That is, the width of the kitchen is w + tiles, and the height is h + tiles. As each tile can be rotated in one of four ways, he still needs to decide on how exactly he will tile the floor. There is a single aesthetic criterion that he wants to fulfil: two adjacent tiles must not share a colour on the edge — i.e. one of the tiles must have a white colour on the shared border, and the second one must be black. + +The picture on the left shows one valid tiling of a 3×2 + kitchen. The picture on the right shows an invalid arrangement, as the bottom two tiles touch with their white parts. +Find the number of possible tilings. As this number may be large, output its remainder when divided by 998244353 + (a prime number). + +--- + +- decorating his kitchen +- tiles are split in half diagonally with black / white +- w x h kitchen +- a given tile has 4 valid rotations +- two adjacent tiles must not share a colour on the edge +- find the number of possible tilings +- return mod 998244353 +- w <= 1000 +- h <= 1000 +- w x h <= 1,000,000 + +--- + +- is the answer just (w x h) ** 2? + - this is the case for 22, 24