algorithms

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

commit 4ea354fe4442d77e066dddc1f1382687fb539c4c
parent 7d16114abe60e91e112ae93ba5938ef0a91b2d10
Author: Andrew Laack <andrew@laack.co>
Date:   Tue, 17 Nov 2026 13:11:15 -0600

1300 math and binary search

Diffstat:
Acomp/chat-ban/ex1.in | 8++++++++
Acomp/chat-ban/ex2.in | 0
Acomp/chat-ban/main.cpp | 149+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/chat-ban/thoughts.txt | 0
4 files changed, 157 insertions(+), 0 deletions(-)

diff --git a/comp/chat-ban/ex1.in b/comp/chat-ban/ex1.in @@ -0,0 +1,8 @@ +7 +4 6 +4 7 +1 2 +3 7 +2 5 +100 1 +1000000000 923456789987654321 diff --git a/comp/chat-ban/ex2.in b/comp/chat-ban/ex2.in diff --git a/comp/chat-ban/main.cpp b/comp/chat-ban/main.cpp @@ -0,0 +1,149 @@ +#include <iostream> +#include <vector> +#include <unordered_set> +#include <unordered_map> +#include <algorithm> +#include <queue> + +#define ll long long + +// spam emote triangle of size k +// it's 2k-1 messages + +// k = 3 is: + +// e +// e e +// e e e +// e e +// e + +// k = 4 is: + +// e +// e e +// e e e +// e e e e +// e e e +// e e +// e + +// k = 5 is: + +// e +// e e +// e e e +// e e e e +// e e e e e +// e e e e +// e e e +// e e +// e + +// Auto moderator of the current chat will ban you right after you spam at least x emotes in succession + // e is an emote above +// assume only user in chat is us +// how many messages will we write before being banned + // message is a full line +// banned message is also included in sum of messages sent + + +// k = 3 +// this has 5*1 + 3*1 + 1*1 = 9 emotes + +// k = 5 +// this has 7*1 + 5*1 + 3*1 + 1*1 = 16 emotes + +// NOTE: This includes the midpoint line +// top half sum == + // lineNumber = min(lineNum, k) + // (lineNumber + 1) * (lineNumber / 2) + // NOTE: lineNumber / 2 is floating point + +// IFF lineNumber > k + // bottom half sum = + // (deltaToEnd + 1) * (deltaToEnd / 2) + + +// Then, we do a binary search to find the first value > target + +using namespace std; + + +ll computeAbove(ll lineNum, ll k) { + ll lineNumber = min(lineNum,k); + ll delta = 0; + + // this is always correct because the +1 will make line number evenly div by 2. + if(lineNumber%2 == 1) { + delta = (lineNumber+1) / 2; + } + + ll topHalf = ((lineNumber+1) * (lineNumber/2)) + delta; + + ll bottomHalfMissing = -1; + + if(lineNum > k) { + ll delta = ((k*2)-1) - (lineNum); + ll dt = 0; + + if(delta%2 == 1) { + dt = (delta+1) / 2; + } + + bottomHalfMissing = (delta + 1) * (delta / 2) + dt; + } + if(bottomHalfMissing == -1) { + return topHalf; + } else { + return topHalf + ((topHalf-k) - bottomHalfMissing); + } +} + +void binarySearchFor(ll k, ll target, ll left, ll right) { + + ll midPoint = left + ((right - left)/2); + + if(midPoint == left) { + ll score = computeAbove(midPoint, k); + if(score >= target) { + cout << midPoint << endl; + } else { + cout << right << endl; + } + return; + } + + ll score = computeAbove(midPoint, k); + + if(score < target) { + binarySearchFor(k,target,midPoint,right); + return; + } + + if(score == target) { + cout << midPoint << endl; + return; + } + + if(score > target) { + binarySearchFor(k,target,left,midPoint); + return; + } + + +} + + +int main() { + + ll testCases, k,m; + cin >> testCases; + + for(ll z = 0; z < testCases; ++z) { + cin >> k; + cin >> m; + binarySearchFor(k,m,1, (2*k) - 1); + } + +} diff --git a/comp/chat-ban/thoughts.txt b/comp/chat-ban/thoughts.txt