SkyMagic's blog

By SkyMagic, history, 5 hours ago, In English

The problem is basically monopoly but you don't need to roll dices or stuffs, we have $$$N$$$ $$$(1 \leq N \leq 10^5)$$$ positions each of which are all empty. We can play any number of rounds by each rounds we choose an index $$$i$$$, if it's empty, we'll build a house on that position which will cost us $$$A_i$$$, and gives us 1 points, but if it's a house already, we'll transform the house to a apartment, which will cost us $$$B_i$$$, and gives us 1 points, if it's already an apartment we'll do nothing, which gives us nothing and cost us nothing (so there's no reason to do this). We always want to maximize the amount of points. (We can make an apartment on the position $$$i$$$ if and only if the position $$$i$$$ is a already a house)

There will be $$$Q$$$ $$$(1 \leq Q \leq 10^5)$$$ queries, on the $$$ith$$$ query $$$(1 \leq i \leq Q)$$$ we have a budget of $$$X_i$$$, which means that the total sums of cost cannot exceed $$$X_i$$$. We want to know that, for each queries $$$i$$$ $$$(1 \leq i \leq Q)$$$ what is the maximum amount of points we can possibly get?

Constraints:

  • $$$1 \leq N,Q \leq 10^5$$$

  • $$$1 \leq A_i,B_i \leq 10^{14}$$$

  • $$$1 \leq X_i \leq 2 \cdot 10^{14}$$$

What I tried(Not the full solution)

I could not find a solution. But if anyone can, please comment what the solution to this problem could be(Other people would know too!), I would really appreciate it!

Thanks in advance!

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By SkyMagic, history, 6 months ago, In English

can anybody please share the solution or the thought process of this problem? i am really having a hard time on it https://codeforces.me/gym/105192/problem/D Thanks!

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it