dyatkovskiy's blog

By dyatkovskiy, history, 5 days ago, translation, In English,

For problem 1241C. Legacy tut.

Here's another idea to solve it in linear time. Whole idea is to become a thug seller, haha! You sell ticket, but you can take it back! Any time! But respect police, ah? So whenever you take ticket back, you return funds. Otherwise you'll never reach k.

Idea

This is how whole thing works. OK, we also swap x and y, so x is always better.

  1. All non-x and non-y buyers should wait. You respect their.. booking, but kindly ask them to quit the line. They will get their tickets after you deal with X and Y. Besides those guys will get best price.
  2. So, you start selling X, or Y. Whatever it is, you sell most expensive remaining ticket. AND.. if at some point you've just realized, that you could sell even more expensive ticket, but it is sold with lower profit, you just take it back, (give money back) and sell it again with better profit. Buyer who just suffered lose of ticket is to be calmed by buying another (probably cheaper) one. Below is more scientific form.

More scientific form

  1. Tickets sorted in ascending order.
  2. EAB = EA = EB = n
  3. If you're selling XY, sell ticket[--EAB]. 3.1 If there was sold at least one X or Y ticket (which is detected by EA-1 vs EAB and EB-1 vs EAB comparinson), then that ticked is already owned by some poor guy. So, roll it back, and sell X or Y respectively again (call sellX or sellY). Both EA and EB should be decremented anyways.. somehow (see code).
  4. sellX. If you're selling X, sell ticket[--EA]. If this ticket is already owned by smb as Y one, rollit back, and re-run sellY.
  5. sellY. Just sell it for a while (sell ticket[--EB]).

And yes, each after each X,Y and XY transaction check total profit, and if we've reached k, say good-bye to everyone and run, haha!

Slow man's solution (code is non contest-encrypted, so you could read it):

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdint>

typedef uint64_t int_t;

#ifndef LOG
struct dummy {
  template<typename T>
  dummy& operator << (const T& v) { return *this; }
} log;
#else
auto &log = std::cout;
#endif

struct state_t {
  std::vector<int_t> tickets, aprofits, bprofits;
  int_t a, x, b, y, eab, ea, eb;
  int_t profit = 0;
  
  state_t(int_t n) {
    tickets.resize(n);
    aprofits.resize(n);
    bprofits.resize(n);
    eab = n, ea = n, eb = n;
  }
  
  // should be called before any sales
  void mayBeSwapAB() {
    if (y > x) {
      std::swap(a, b);
      std::swap(x, y);
    }  
  }
  
  void sellAB() {
    if (a == b) {
      profit += tickets[--eab] * (x + y) / 100;
      return;
    }
    
    auto curProfit = tickets[--eab] * (x + y) / 100;        
    profit += curProfit;

    log << "sellAB, ticket[" << eab << "] " << tickets[eab] << ", profit +" << curProfit << "\n";
    
    if (ea-1 < eab) {
      log << "  rollback A, -" << aprofits[eab] << "\n";    
      profit -= aprofits[eab];
      sellA();
    } else { // then we've already sold at least one b
      // but also move ea pointer
      --ea;
      log << "  rollback B, -" << bprofits[eab] << "\n";       
      profit -= bprofits[eab];
      sellB();
    }
  }
  
  void sellA() {
    auto curProfit = tickets[--ea] * x / 100;
    profit += curProfit;
    
    log << "sellA, ticket[" << ea << "] " << tickets[ea] << ", profit +" << curProfit << "\n";    
    
    aprofits[ea] = curProfit;
    
    if (eb-1 < ea) {
      log << "  rollback B, -" << bprofits[ea] << "\n";    
      profit -= bprofits[ea];
      sellB();
    } else {
      --eb; // move eb anyways
    }
  }
  
  void sellB() {
    auto curProfit = tickets[--eb] * y / 100;
    profit += curProfit;
    
    log << "sellB, ticket[" << eb << "] " << tickets[eb] << ", profit +" << curProfit << "\n";        
    
    bprofits[eb] = curProfit;    
  }
};

int solve() {
  int_t n, k;
  
  std::cin >> n;

  state_t state(n);
    
  for (size_t i = 0; i != n; ++i)
    std::cin >> state.tickets[i];
  std::sort(state.tickets.begin(), state.tickets.end());
      
  std::cin >> state.x >> state.a >> state.y >> state.b >> k;
  
  state.mayBeSwapAB();
  
  int_t t = std::min({n, state.a, state.b});
  
  while (t <= n) {
  
    log << "ticket #" << t << "\n";
  
    if ((t % state.a == 0) && (t % state.b == 0))
      state.sellAB();
    else if (t % state.a == 0)
      state.sellA();
    else // if (t % b)
      state.sellB();
      
    if (state.profit >= k)
      return (int)t;
    
    auto ma = state.a - t % state.a;
    auto mb = state.b - t % state.b;
    
    t += std::min(ma, mb);
  }
  
  return -1;
}

int main() {
  int q;
  std::cin >> q;
  
  for (int i = 0; i != q; ++i) {
    log << "TEST #" << i << "\n"; 
    std::cout << solve() << "\n";
  }  
  
  return 0;
}
 
 
 
 
  • Vote: I like it
  • +22
  • Vote: I do not like it