algorithms

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

main.cpp (2510B)


      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 // computer game
     11 // current game can be modeled as a straight line
     12 // start at point 0
     13 // n monsters trying to kill you 
     14 // ith monster has a_i health starts at point x_i
     15 
     16 // every second:
     17     // fire up to k bullets at monsters each hits one monster for 1 damage
     18     // 0 or less health monsters die
     19     // alive move one point closer 
     20         // if monster reaches you die
     21 // can you survive?
     22     // we will always want to target nearest and if at all possible not waste bullets
     23     // 
     24 
     25 // n = 3, k = 2
     26 // healths = [1 2 3]
     27 // positions = [-1 2 3]
     28 
     29 // since we are at 0 we can normalize by distance
     30 
     31 // healths = [1 2 3]
     32 // distances = [1 2 3]
     33 
     34 // we shoot nearest once, second once
     35 //  they move, we shoot second once and third once
     36 // they move, we kill final, return "YES"
     37 
     38 // the issue here is that we can get fucked by large numbers,  computationally
     39 // instead we'll want to consider how many shots to kill nearest, take that many steps with a remainder
     40 // and then move all of them.
     41 
     42 using namespace std;
     43 
     44 int main() {
     45     ll testCases, n, k, current;
     46     cin >> testCases;
     47 
     48     for(ll z = 0; z < testCases; ++z) {
     49         cin >> n;
     50         cin >> k;
     51 
     52         vector<ll> health {};
     53         vector<ll> distance {};
     54 
     55         vector<pair<ll,ll>> distHealth {};
     56 
     57         for(ll i = 0; i < n; ++i) {
     58             cin >> current;
     59             health.push_back(current);
     60         }
     61 
     62         for(ll i = 0; i < n; ++i) {
     63             cin >> current;
     64 
     65             if (current < 0) {
     66                 distance.push_back(current * -1);
     67             }
     68             else {
     69                 distance.push_back(current);
     70             }
     71         }
     72 
     73         for(ll i = 0; i < n; ++i) {
     74             pair<ll,ll> current {distance[i], health[i]};
     75             distHealth.push_back(current);
     76         }
     77 
     78         sort(distHealth.begin(), distHealth.end());
     79         bool ck = true;
     80         long long shot = 0;
     81 
     82         for(ll i = 0; i  < distHealth.size(); ++i) {
     83             ll targetDistance = distHealth[i].first;
     84             ll targetHealth = distHealth[i].second;
     85             if((k*targetDistance) - shot < targetHealth) {
     86                 ck = false;
     87                 break;
     88             }  else {
     89                 shot += targetHealth;
     90             }
     91         }
     92 
     93 
     94         if(!ck) {
     95             cout << "NO" << endl;
     96         } else {
     97             cout << "YES" << endl;
     98         }
     99     }
    100 }