Due to the installation of a new fire alarm in ITMO server room, the system may be occasionally unavailable on the 27-th of May between 06:00 and 15:00 (UTC). ×

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.

History

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