시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 512 MB | 125 | 78 | 69 | 62.162% |
Your brother has won an award at the recent Breakthroughs in Architectural Problems Conference and has been given the once in a lifetime opportunity of redesigning the city center of his favorite city Nijmegen. Since the most striking parts of a city’s layout are the skylines, your brother has started by drawing ideas for how he wants the northern and eastern skylines of Nijmegen to look. However, some of his proposals look rather outlandish, and you are starting to wonder whether his designs are possible.
For his design, your brother has put an R × C grid on the city. Each cell of the city will contain a building of a certain height. The eastern skyline is given by the tallest building in each of the R rows, and the northern skyline is given by the tallest building in each of the C columns.
A pair of your brother’s drawings of skylines is possible if and only if there exists some way of assigning building heights to the grid cells such that the resulting skylines match these drawings.
Figure A.1 shows a possible city with the northern and eastern skylines exactly as given in the input of the first sample.
Figure A.1: Example city showing sample 1 has a valid solution.
Output one line containing the string possible if there exists a city design that produces the specified skyline, and impossible otherwise.
4 4 4 3 2 1 1 2 3 4
possible
4 4 1 2 3 4 1 2 3 2
impossible
ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2019 Preliminaries A번