The Juno spacecraft in front of Jupiter. Graphic by
Although we imagine interplanetary probes to be very
sophisticated pieces of technology, their information systems
are quite archaic. You might assume that they have a certain
amount of contiguous main memory and can store their data
wherever is convenient, but unfortunately that is not the case.
The probe’s main memory is organised in a number of FIFO
(first-in-first-out) queues. In such a queue, data has to be
taken out of the queue in the same order as it has been added
A probe has multiple sensors and each sensor is linked to
one of the queues. Whenever a sensor finishes recording, it
appends the generated data to its queue. A sensor can write
data to the queue only if the queue has enough space left to
take all the data; if not, the data is lost.
In order to transfer data from the probe to Earth (in a
process called downlinking), the path between the
satellite and Earth must not be blocked by anything
(e.g. a planet like Jupiter) and the antenna must be
correctly positioned. During each downlink opportunity, data
can be taken from multiple queues and transmitted back to
Earth. The total amount of data that can be transmitted during
a downlink opportunity depends on the length of the downlink
opportunity and distance to Earth. Sensors do not collect data
during downlink opportunities, since all electricity available
is devoted to the transmitter.
The most important thing for scientists is not to lose any
data recorded by sensors. In particular, all queues have to be
empty after the last downlink opportunity. The scientists have
asked you to write a program to determine whether all data can
be transferred to Earth in a given time frame.
one line containing three positive integers $n,q,s$ ($1\leq n,q \leq 30$, $1 \leq s \leq 100$), the number
of downlink windows, FIFO queues, and sensors,
one line with $s$
integers $q_1 \ldots q_
s$ ($1 \leq q_ i \leq
q$ for each $i$), determining for each sensor
the queue it feeds its data into.
one line with $q$
integers $c_1 \ldots c_
q$ ($1 \leq c_ i \leq
10^6$ for each $i$), determining for each queue
the size of the queue in megabytes.
$n$ lines, each
describing one downlink window. Each contains $s + 1$ non-negative integers.
The first integer $d$ ($1 \leq d \leq 10^6$) states
the number of megabytes that can be transferred to
earth during the window.
The following $s$ numbers $a_1 \ldots a_ s$
($0 \leq a_ i \leq
10^6$ for each $i$) describing the amount of
data (in megabytes) generated by each of the sensors
after the last but before this downlink window.
There will never be new data during a downlink window.
Output “possible” if it is
possible to transfer all data to Earth, and “impossible” otherwise.
|Sample Input 1
||Sample Output 1
2 2 2
5 2 2
5 2 2
|Sample Input 2
||Sample Output 2
2 2 2
1 2 2
5 2 2