algorithms

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

commit ee35c25236c5051aab17d773ceae598763bc9367
parent d7f87117f9c26991f2b2b8e1ed5b9b0b4c786279
Author: Andrew Laack <andrew@laack.co>
Date:   Wed, 21 Oct 2026 14:08:49 -0500

All in one gun

Diffstat:
Acomp/all-in-one-gun/ex1.in | 13+++++++++++++
Acomp/all-in-one-gun/ex2.in | 3+++
Acomp/all-in-one-gun/main.cpp | 91+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/all-in-one-gun/problem.txt | 157+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 264 insertions(+), 0 deletions(-)

diff --git a/comp/all-in-one-gun/ex1.in b/comp/all-in-one-gun/ex1.in @@ -0,0 +1,13 @@ +6 +5 10 1 +4 2 3 5 3 +5 10 1 +4 2 3 7 3 +3 10 2 +1 2 3 +2 5 3 +2 1 +3 18 5 +1 2 3 +4 10 10 +1 1 2 2 diff --git a/comp/all-in-one-gun/ex2.in b/comp/all-in-one-gun/ex2.in @@ -0,0 +1,3 @@ +1 +60 568546998 561569521 +8 4 4 3 10 9 9 6 9 3 10 8 1 6 6 2 2 4 1 2 4 9 10 1 7 2 7 1 8 5 10 5 3 5 9 10 2 5 10 6 2 2 4 5 5 6 6 5 5 5 8 8 1 8 10 6 2 2 8 6 diff --git a/comp/all-in-one-gun/main.cpp b/comp/all-in-one-gun/main.cpp @@ -0,0 +1,91 @@ +#include <iostream> +#include <vector> + +long long vecSum(std::vector<long long> inp) { + long long sm = 0; + for(auto i : inp) { + sm += i; + } + return sm; +} + +void printVec(std::vector<long long> inp) { + for(long long i = 0 ; i < inp.size(); ++i) { + std::cout << inp[i] << " "; + } + std::cout << std::endl; + +} + +long long solve(std::vector<long long> nums, int health, int reloadTime) { + + std::vector<long long> minPrefixInc {}; + + long long min = nums[0]; + + for(int i = 0; i < nums.size(); ++i) { + if(nums[i] < min) { + min = nums[i]; + } + minPrefixInc.push_back(min); + } + + std::vector<long long> maxPostfixExc (nums.size() - 1); + long long max = nums[nums.size()-1]; + + for(int i = nums.size()-2; i >= 0; --i) { + maxPostfixExc[i] = max; + if(nums[i] > max) { + max = nums[i]; + } + } + + //printVec(nums); + //printVec(maxPostfixExc); + //printVec(minPrefixInc); + + long long vs = vecSum(nums); + long long target = health % vs; + + long long running = 0; + int required = 1; + + if(target != 0) { + for(int i = 0; i < nums.size()-1; ++i) { + running += nums[i]; + long long bestChoiceDelta = maxPostfixExc[i] - minPrefixInc[i]; + if(running + bestChoiceDelta >= target) { + break; + } else { + required += 1; + } + } + } else { + required = 0; + } + + long long base = (health / vs) * (reloadTime + nums.size()); + if(target == 0) { + base = ((health / vs) * (nums.size())) + (((health / vs) - 1) * reloadTime); + } + + + return required + base; +} + +int main() { + + int testCount, arrElement, nElements, reloadTime, health; + std::cin >> testCount; + for(int i = 0; i < testCount; ++i) { + std::cin >> nElements; + std::cin >> health; + std::cin >> reloadTime; + std::vector<long long> current {}; + for(int x = 0; x < nElements; ++x) { + std::cin >> arrElement; + current.push_back(arrElement); + } + std::cout << solve(current, health, reloadTime) << std::endl; + } +} diff --git a/comp/all-in-one-gun/problem.txt b/comp/all-in-one-gun/problem.txt @@ -0,0 +1,157 @@ +C. All-in-one Gun +time limit per test2 seconds +memory limit per test256 megabytes +You are developing a new shooter game, but since there are a lot of shooter games out there, you decide to have something unique in your game. + +You have an all-in-one gun that shoots bullets in a fixed order. There are n + bullets in the magazine, the i +-th of which deals ai + damage. The enemy starts with h + health and dies when its health becomes ≤0 +. + +The gun shoots one bullet per second. After firing all n + bullets, it must reload, which takes k + seconds. Reloading always restores the same sequence of bullets [a1,a2,…,an] +. You cannot reload early; you must empty the magazine first. At the start, the magazine is already full. + +Before the fight begins, you may perform at most one swap: pick any indices 1≤i<j≤n + and exchange ai + with aj +. + +Your task is to find the minimum number of seconds needed to kill the enemy, taking into account this optional single swap. + +Input +Each test contains multiple test cases. The first line contains the number of test cases t + (1≤t≤104 +). The description of the test cases follows. + +The first line of each testcase contains three integer n +, h + and k + (2≤n≤2⋅105 +, 1≤h,k≤109 +) — the size of magazine, health of your enemy and time required to reload the magazine. + +The second line of each testcase contains n + integers a1,a2,…,an + (1≤ai≤109 +). + +It is guaranteed that the sum of n + does not exceed 2⋅105 + over all test cases. + + +--- + +- bullet damage array a +- a_i is damage done by bullet i +- enemy has h health to start +- one bullet per second +- k seconds to reload + - can't reload early +- you may swap two bullets at the start a_i -> a_j a_j -> a_i + +--- + + +5 10 1 +4 2 3 5 3 + +n,h,k + +5 elements +h = 10 == health start +k = 1 == seconds to reload + +4 2 3 5 3 + +swap: 2,5 + +4 5 3 2 3 + +shoot 1,2,3 that's it. + +3 seconds + +heuristic: find section from start that sums to 10. check each swap with smallest value in section and later values to see if this changes things + +--- + +5 10 1 +4 2 3 7 3 + +5 elements +10 health +1 second reload + +4 2 3 7 3 + +4+2+3+7 = 16 + +smallest = 2 + +2,3 swap does nothing +2,7 swap decreases by 1 +... + +4 7 3 2 3 + +same heuristic as above, but the issue here is that we don't only care about the min value; if we could swap the first with a larger value even +if first > second and that'd finish the problem we should do that. + +--- + +3 10 2 +1 2 3 + +two second reload +10 health + +3 2 1 + +3, 2, 1, (reload), 3, 2 -> 7 + +--- + +2 5 3 +2 1 + +2 elements, 3 second reload, 5 health + +since descending order do nothing. + +2,1,reload,2 -> 6 + +--- + +3 18 5 +1 2 3 + +3,2,1 + + +--- + +4 10 10 +1 1 2 2 + +2,1,2,1 + +--- + +idea: + +- compute sum of array +- compute rem = health % sum + - rem is then the amount of damage to be dealt in the last magazine +- how to compute shortest array ordering that results in sum >= rem + - compute default substring s.t. sum >= rem + - from 0 -> len: + - check if current where we swap smallest on left with largest on right (inclusive of current) would be > target + - if so, return this idx + (magTime * magsUsed) + - if not continue + - how to make this fast: + - compute max postfix (exclusive of current) and min prefix (inclusive)