algorithms

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

main.cpp (2765B)


      1 #include <iostream>
      2 #include <vector>
      3 #include <unordered_set>
      4 #include <unordered_map>
      5 #include <algorithm>
      6 #include <queue>
      7 
      8 #define ll long long
      9 
     10 // spam emote triangle of size k
     11 // it's 2k-1 messages
     12 
     13 // k = 3 is:
     14 
     15 // e 
     16 // e e
     17 // e e e
     18 // e e
     19 // e
     20 
     21 // k = 4 is:
     22 
     23 // e 
     24 // e e
     25 // e e e
     26 // e e e e
     27 // e e e
     28 // e e
     29 // e
     30 
     31 // k = 5 is:
     32 
     33 // e
     34 // e e 
     35 // e e e
     36 // e e e e
     37 // e e e e e
     38 // e e e e
     39 // e e e
     40 // e e
     41 // e
     42 
     43 // Auto moderator of the current chat will ban you right after you spam at least x emotes in succession
     44     // e is an emote above
     45 // assume only user in chat is us
     46 // how many messages will we write before being banned
     47     // message is a full line
     48 // banned message is also included in sum of messages sent
     49 
     50 
     51 // k = 3
     52 // this has 5*1 + 3*1 + 1*1 = 9 emotes
     53 
     54 // k = 5
     55 // this has 7*1 + 5*1 + 3*1 + 1*1 = 16 emotes
     56 
     57 // NOTE: This includes the midpoint line
     58 // top half sum ==
     59     // lineNumber = min(lineNum, k)
     60     // (lineNumber + 1) * (lineNumber / 2)
     61         // NOTE: lineNumber / 2 is floating point
     62 
     63 // IFF lineNumber > k
     64     // bottom half sum =
     65         // (deltaToEnd + 1) * (deltaToEnd / 2)
     66 
     67 
     68 // Then, we do a binary search to find the first value > target
     69 
     70 using namespace std;
     71 
     72 
     73 ll computeAbove(ll lineNum, ll k) {
     74     ll lineNumber = min(lineNum,k);
     75     ll delta = 0;
     76 
     77     // this is always correct because the +1 will make line number evenly div by 2.
     78     if(lineNumber%2 == 1) {
     79         delta = (lineNumber+1) / 2;
     80     }
     81 
     82     ll topHalf = ((lineNumber+1) * (lineNumber/2)) + delta;
     83 
     84     ll bottomHalfMissing = -1;
     85 
     86     if(lineNum > k) {
     87         ll delta = ((k*2)-1) - (lineNum);
     88         ll dt = 0;
     89 
     90         if(delta%2 == 1) {
     91             dt = (delta+1) / 2;
     92         }
     93 
     94         bottomHalfMissing = (delta + 1) * (delta / 2) + dt;
     95     }
     96     if(bottomHalfMissing == -1) {
     97         return topHalf;
     98     } else {
     99         return topHalf + ((topHalf-k) - bottomHalfMissing);
    100     }
    101 }
    102 
    103 void binarySearchFor(ll k, ll target, ll left, ll right) {
    104 
    105     ll midPoint = left + ((right - left)/2);
    106 
    107     if(midPoint == left) {
    108         ll score = computeAbove(midPoint, k);
    109         if(score >= target) {
    110             cout << midPoint << endl;
    111         } else {
    112             cout << right << endl;
    113         }
    114         return;
    115     }
    116 
    117     ll score = computeAbove(midPoint, k);
    118     
    119     if(score < target) {
    120         binarySearchFor(k,target,midPoint,right);
    121         return;
    122     } 
    123 
    124     if(score == target) {
    125         cout << midPoint << endl;
    126         return;
    127     } 
    128     
    129     if(score > target) {
    130         binarySearchFor(k,target,left,midPoint);
    131         return;
    132     }
    133     
    134 
    135 }
    136 
    137 
    138 int main() {
    139 
    140     ll testCases, k,m;
    141     cin >> testCases;
    142 
    143     for(ll z = 0; z < testCases; ++z) {
    144         cin >> k;
    145         cin >> m;
    146         binarySearchFor(k,m,1, (2*k) - 1);
    147     }
    148 
    149 }