Woburn Challenge 2017-18 Round 3 - Senior Division
Problem 3: Down for Maintenance
Dave spends most of his free time on the internet, and especially loves hanging out on a hot new website. Unfortunately, in order to be able to handle the heavy traffic that it receives, the site frequently needs to be taken down for maintenance!
The site's maintenance schedule repeats every 24 hours. During each 24-hour cycle, it has one or more inactive intervals of time for which it's down. Each interval spans some positive amount of time (though it may be arbitrarily short), is less than 24 hours long, and may span from the end of one day to the start of another. All of the intervals are disjoint from one another (in other words, no point in time is inside multiple intervals, inclusive). The site is neither always up nor always down.
The schedule isn't publicly available, but Dave has noted down some observations about the site's status at various times of the day. He's made a list of N (0 ≤ N ≤ 100,000) times of day (measured in microseconds since midnight) at which he knows that the site is up, the i-th of which is Ui (0 ≤ Ui < 86,400,000,000). He's similarly made a list of M (0 ≤ M ≤ 100,000) times of day at which he knows that the site is down, the i-th of which is Di (0 ≤ Di < 86,400,000,000). All N + M of these times are distinct.
Recently, one piece of information regarding the maintenance schedule has finally surfaced – the Government of Canada has reported that their site has exactly I (1 ≤ I ≤ 1,000,000,000) inactive intervals in each 24-hour cycle. However, Dave isn't quite sure whether the government should be trusted… As such, he'd first like to determine whether or not it's even possible for there to be exactly I inactive intervals according to his own observations.
If it is possible, he'd like to use this additional knowledge to help deduce some additional information about the maintenance schedule, in order to optimize his browsing time. He's interested in a list of K (1 ≤ K ≤ 100,000) possibly non-distinct times of day, the i-th of which is Qi (0 ≤ Qi < 86,400,000,000). For each of these times, he'd like to determine whether the site would definitely be up at that time, definitely be down, or that its status would be unknown (it might be either up or down depending on how the I inactive intervals are laid out).
In test cases worth 8/26 of the points, N ≤ 50, M ≤ 50, K ≤ 50, Ui ≤ 100,000, Di ≤ 100,000, and Qi ≤ 100,000.
In test cases worth another 9/26 of the points, Ui ≤ 100,000, Di ≤ 100,000, and Qi ≤ 100,000.
The first line of input consists of a single integer, I.
The next line consists of a single integer, N.
N lines follow, the i-th of which consists of a single integer, Ui, for i = 1..N.
The next line consists of a single integer, M.
M lines follow, the i-th of which consists of a single integer, Di, for i = 1..M.
The next line consists of a single integer, K.
K lines follow, the i-th of which consists of a single integer, Qi, for i = 1..K.
Either the string "
Impossible" if there can't be exactly I inactive intervals, or K lines, the i-th of which is a string describing the status of time Qi (either "
Down", or "
2 3 33582 9061 62057 3 78415 21592 1344 5 50000 30000 9061 66666 0
Up Unknown Up Unknown Down
Consider the second queried time of day (30,000). It's possible for the site to be up at that time, if the pair of inactive intervals are for example 15,000…25,000 and 70,000…2000. It's also possible for it to be down at that time, if the pair of inactive intervals are for example 65,000…5000 and 20,000…32,000. On the other hand, the statuses of three other queried times are guaranteed over all possible sets of two inactive intervals.
Point Value: 15 (partial)
Time Limit: 4.00s
Memory Limit: 128M
Added: Mar 23, 2018
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3