algorithms

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

commit ed1e2177227b0b26ffe05f719953c8bc492d6fd2
parent f72b228b25b817c12be7f69c992195ad53fb0d45
Author: Andrew Laack <andrew@laack.co>
Date:   Thu, 29 Oct 2026 23:33:50 -0500

Couple of div 3 contest problems

Diffstat:
Acomp/did-not-go-to-print/ex1.in | 13+++++++++++++
Acomp/did-not-go-to-print/main.cpp | 56++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/did-not-go-to-print/problem.txt | 100+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/in-search-of-convenience/ex1.in | 4++++
Acomp/in-search-of-convenience/main.cpp | 19+++++++++++++++++++
Acomp/in-search-of-convenience/problem.txt | 70++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/main.cpp | 11+++++++++++
7 files changed, 273 insertions(+), 0 deletions(-)

diff --git a/comp/did-not-go-to-print/ex1.in b/comp/did-not-go-to-print/ex1.in @@ -0,0 +1,13 @@ +6 +2 +12 +2 +13 +2 +23 +6 +112332 +3 +112 +6 +211213 diff --git a/comp/did-not-go-to-print/main.cpp b/comp/did-not-go-to-print/main.cpp @@ -0,0 +1,56 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> + +using namespace std; + +// - documents 1 to n +// - n commands where we do the following for each instruction +// 1. scan - place document i on top of memory +// 2. print - iff memory not empty, print topmost and pop, else print i +// 3. quick print - prints document i + +int main() { + + int testCases, n; + string s; + cin >> testCases; + + for(int x = 0; x < testCases; ++x) { + + cin >> n; + cin >> s; + + unordered_set<int> printed {}; + + vector<int> stack {}; + + for(int i = 0; i < n; ++i) { + if(s[i] == '1') { + stack.push_back(i); + } + else if(s[i] == '2') { + if(stack.size() > 0) { + printed.insert(stack[stack.size() - 1]); + stack.pop_back(); + } else { + printed.insert(i); + } + } + else if(s[i] == '3') { + printed.insert(i); + } + } + + std::cout << n - printed.size() << std::endl; + + for(int i = 0; i < n; ++i) { + if(!printed.contains(i)) { + std::cout << i + 1 << " "; + } + } + std::cout << std::endl; + } +} diff --git a/comp/did-not-go-to-print/problem.txt b/comp/did-not-go-to-print/problem.txt @@ -0,0 +1,100 @@ +B. Did Not Go to Print +time limit per test2 seconds +memory limit per test256 megabytes +Recently, K1o0n bought himself a new expensive printer, which is distinguished by its memory, that is, it may not print immediately. Yesterday, while he was away from his new purchase, his friends used the printer. + +There are n + documents numbered from 1 + to n +. Initially, the printer memory is empty. The friends sequentially performed n + commands on the printer, where the i +-th command can be one of: + +'1' — scanning. Document i + is sent to the device memory and is placed on top of everything already there. +'2' — printing from memory. If the memory is not empty, the device prints the topmost document in memory and removes it from there. Otherwise, the device prints document i +. +'3' — quick print. The device prints document i +. +Today, the friends came to K1o0n with a complaint — not all documents were printed. Help K1o0n find the indices of all documents that were not printed. + +Input +The first line contains an integer t + (1≤t≤104 +) — the number of testcases. + +The first line of each testcase contains an integer n + (1≤n≤2⋅105 +) — the number of documents. + +The second line of each testcase contains a string s + of length n +, consisting of the characters '1', '2' and '3' — the friends' commands. + +It is guaranteed that the sum of n + over all testcases does not exceed 2⋅105 +. + +Output +For each testcase, output two lines. + +In the first line — the number k + of documents that were not printed. + +In the second line — their numbers in increasing order, separated by spaces. If k=0 +, the second line is empty. + +--- + +- documents 1 to n +- n commands where we do the following for each instruction + 1. scan - place document i on top of memory + 2. print - iff memory not empty, print topmost and pop, else print i + 3. quick print - prints document i + +--- + +examples + + + +2 +12 + + +n = 2 +s = 12 (n commands) + +place 1 on top +print 1 + +not printed 2 + +--- + +2 +13 + +n = 2 +s = 13 + +push 1 onto stack +print 2 + +return 1 and 1 + +--- + +2 +23 + + + +--- + +6 +112332 +3 +112 +6 +211213 diff --git a/comp/in-search-of-convenience/ex1.in b/comp/in-search-of-convenience/ex1.in @@ -0,0 +1,4 @@ +3 +0 0 1 +5 5 5 +10 10 13 diff --git a/comp/in-search-of-convenience/main.cpp b/comp/in-search-of-convenience/main.cpp @@ -0,0 +1,19 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> + +using namespace std; + +int main() { + int testCases, x,y,r = 0; + cin >> testCases; + for(int i = 0; i < testCases; ++i) { + cin >> x; + cin >> y; + cin >> r; + std::cout << x << " " << y+r << std::endl; + } + +} diff --git a/comp/in-search-of-convenience/problem.txt b/comp/in-search-of-convenience/problem.txt @@ -0,0 +1,70 @@ +A. In Search of Convenience +time limit per test1 second +memory limit per test256 megabytes +K1o0n got a router and placed it at point (x0,y0) +; we will consider the apartment layout as a coordinate plane, and the floor is tiled, so the furniture can stand only at lattice points with integer coordinates. + +The internet spreads exactly R + meters around the router. K1o0n wants to move his computer as far away from it as possible — but still so that the internet is available. Therefore, the desk with the computer must be placed exactly on the reception boundary, at a distance of R + from the router. For example, if the router is at point (5,5) + and R=5 +, then the desk can be placed at point (2,1) +, because (5−2)2+(5−1)2=52 +. + +Find any point with integer coordinates that is exactly R + away from (x0,y0) +. + +Recall that the distance from the point (x0,y0) + to the point (x,y) + is (x0−x)2+(y0−y)2−−−−−−−−−−−−−−−−−√ +. + +Input +The first line contains an integer t + (1≤t≤104 +) — the number of testcases. + +The only line of each testcase contains three integers x0 +, y0 +, and R + (−10≤x0,y0≤10 +, 1≤R≤25 +) — the coordinates of the router and the coverage radius. + +Output +For each testcase, output two integers x + and y + — the coordinates of the desk. + +If there are several suitable points, output any of them. + +--- + +- router at x_0, y_0 +- internet is R around router +- move computer as far as possible + + +--- + +ex1 + +0 0 1 + +x_0, y_0, R + +0,1 + +--- + +5 5 5 + +5,10 + +--- + +10 10 13 + +10,23 diff --git a/comp/main.cpp b/comp/main.cpp @@ -0,0 +1,11 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> + +using namespace std; + +int main() { + +}