시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 133 | 42 | 32 | 30.769% |
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 to it.
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.
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.
2 2 2 1 2 3 3 5 2 2 5 2 2
possible
2 2 2 1 2 3 3 1 2 2 5 2 2
impossible
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2016 J번