Ticket Exchange Problem

Revision en1, by send_nodes, 2016-12-25 05:31:47

Hi community,

I've been thinking about some problem for a while, and was wondering if it has a polynomial time solution. The problem goes as follows:

You character starts with B blue tickets and R red tickets. There are N offers proposed to you, the i'th in which you first lose ai blue tickets, bi red tickets, and then right afterwards gain ci blue tickets and di red tickets (Suppose all values except N are  ≤ 109). You lose if you ever have a negative amount of either ticket type. Is it possible to complete all offers and not lose?

Obviously you first want to complete all offers that yield positive profit for both red and blue tickets, but even then there might be some offers you can't complete. The rest is not so trivial.

Does anyone have ideas or seen this problem before? As said, this is original, so I don't have a problem link and am simply looking for the best time complexity possible.


  Rev. Lang. By When Δ Comment
en1 English send_nodes 2016-12-25 05:31:47 965 Initial revision (published)