시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB42529126573.816%

문제

골룸산업은 유연하고 재배치가 가능한 최신 트렌드의 오피스 공간을 디자인하고 있다. 새로이 만드는 공간은 가로로 긴 직사각형 형태의 오피스와 군데군데 선택해 배치할 수 있는 세로 파티션으로 구성되어 있다.

그림 C.1

그림 C.1 은 폭이 10이고 1, 4, 8 자리에 선택적으로 파티션을 배치할 수 있는 오피스를 나타내고 있다. 방의 폭은 언제나 왼쪽과 오른쪽 벽 사이의 거리로 나타내어지며, 파티션은 언제나 왼쪽과 오른쪽 벽에 평행하게 놓여진다.

위 예제에서 아무런 파티션도 선택하지 않는 경우, 우리는 폭 10의 미팅공간을 확보할 수 있다. 만약 회사가 폭 4의 미팅 공간을 필요로 한다면 위치 4에 파티션을 하나 배치함으로써(혹은 4 와 8 자리에 파티션을 하나씩 배치함으로써) 폭 4의 미팅공간을 확보할 수 있다. 폭 7의 미팅공간을 확보하기 위해서는 위치 1과 8에(가운데 4를 제외하고) 파티션을 배치하면 된다.

디자인한 방의 정보가 주어질 때, 해당 방에서 만들 수 있는 가능한 모든 종류의 방 폭을 알아내어라.

입력

입력의 첫 줄은 두 개의 정수로 구성된다: 전체 폭 W(2 <= W <= 100)과 파티션의 개수 P(1 <= P < W). 이어지는 줄에는 P개의 정수가 주어지며, 각각의 정수 L(0 < L < W)은 해당 위치에 파티션을 설치할 수도 있음을 나타낸다. 각각의 파티션의 위치는 서로 다르며 증가수열 형태로 주어진다.

출력

구성가능한 모든 미팅방의 크기를 작은 크기부터 순서대로 출력한다.

예제 입력 1

10 3
1 4 8

예제 출력 1

1 2 3 4 6 7 8 9 10

예제 입력 2

6 2
2 5

예제 출력 2

1 2 3 4 5 6
W3sicHJvYmxlbV9pZCI6IjEwNDcxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhY2Y1XHVhYzA0XHVjNzQ0IFx1YjljY1x1YjRlNFx1YzViNCBcdWJkMDVcdWMyZGNcdWIyZTQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWNlOFx1YjhmOFx1YzBiMFx1YzVjNVx1Yzc0MCBcdWM3MjBcdWM1ZjBcdWQ1NThcdWFjZTAgXHVjN2FjXHViYzMwXHVjZTU4XHVhYzAwIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWNkNWNcdWMyZTAgXHVkMmI4XHViODBjXHViNGRjXHVjNzU4IFx1YzYyNFx1ZDUzY1x1YzJhNCBcdWFjZjVcdWFjMDRcdWM3NDQgXHViNTE0XHVjNzkwXHVjNzc4XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjMGM4XHViODVjXHVjNzc0IFx1YjljY1x1YjRkY1x1YjI5NCBcdWFjZjVcdWFjMDRcdWM3NDAgXHVhYzAwXHViODVjXHViODVjIFx1YWUzNCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHVkNjE1XHVkMGRjXHVjNzU4IFx1YzYyNFx1ZDUzY1x1YzJhNFx1YzY0MCBcdWFkNzBcdWIzNzBcdWFkNzBcdWIzNzAgXHVjMTIwXHVkMGRkXHVkNTc0IFx1YmMzMFx1Y2U1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzEzOFx1Yjg1YyBcdWQzMGNcdWQyZjBcdWMxNThcdWM3M2NcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL2ZsZXhpYmxlLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEzM3B4OyB3aWR0aDozMTVweFwiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+XHVhZGY4XHViOWJjIEMuMTxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI5YmMgQy4xIFx1Yzc0MCBcdWQzZWRcdWM3NzQgMTBcdWM3NzRcdWFjZTAgMSwgNCwgOCBcdWM3OTBcdWI5YWNcdWM1ZDAgXHVjMTIwXHVkMGRkXHVjODAxXHVjNzNjXHViODVjIFx1ZDMwY1x1ZDJmMFx1YzE1OFx1Yzc0NCBcdWJjMzBcdWNlNThcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM2MjRcdWQ1M2NcdWMyYTRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViYzI5XHVjNzU4IFx1ZDNlZFx1Yzc0MCBcdWM1YjhcdWM4MWNcdWIwOTggXHVjNjdjXHVjYWJkXHVhY2ZjIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWJjYmQgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWM3MFx1YjlhY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjRcdWM1YjRcdWM5YzBcdWJhNzAsIFx1ZDMwY1x1ZDJmMFx1YzE1OFx1Yzc0MCBcdWM1YjhcdWM4MWNcdWIwOTggXHVjNjdjXHVjYWJkXHVhY2ZjIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWJjYmRcdWM1ZDAgXHVkM2M5XHVkNTg5XHVkNTU4XHVhYzhjIFx1YjE5M1x1YzVlY1x1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzA0IFx1YzYwOFx1YzgxY1x1YzVkMFx1YzExYyBcdWM1NDRcdWJiMzRcdWI3ZjAgXHVkMzBjXHVkMmYwXHVjMTU4XHViM2M0IFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhY2JkXHVjNmIwLCBcdWM2YjBcdWI5YWNcdWIyOTQgXHVkM2VkIDEwXHVjNzU4IFx1YmJmOFx1ZDMwNVx1YWNmNVx1YWMwNFx1Yzc0NCBcdWQ2NTVcdWJjZjRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViOWNjXHVjNTdkIFx1ZDY4Y1x1YzBhY1x1YWMwMCBcdWQzZWQgNFx1Yzc1OCBcdWJiZjhcdWQzMDUgXHVhY2Y1XHVhYzA0XHVjNzQ0IFx1ZDU0NFx1YzY5NFx1Yjg1YyBcdWQ1NWNcdWIyZTRcdWJhNzQgXHVjNzA0XHVjZTU4IDRcdWM1ZDAgXHVkMzBjXHVkMmYwXHVjMTU4XHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWJjMzBcdWNlNThcdWQ1NjhcdWM3M2NcdWI4NWNcdWMzNjgoXHVkNjM5XHVjNzQwIDQgXHVjNjQwIDggXHVjNzkwXHViOWFjXHVjNWQwIFx1ZDMwY1x1ZDJmMFx1YzE1OFx1Yzc0NCBcdWQ1NThcdWIwOThcdWM1MjkgXHViYzMwXHVjZTU4XHVkNTY4XHVjNzNjXHViODVjXHVjMzY4KSBcdWQzZWQgNFx1Yzc1OCBcdWJiZjhcdWQzMDVcdWFjZjVcdWFjMDRcdWM3NDQgXHVkNjU1XHViY2Y0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDNlZCA3XHVjNzU4IFx1YmJmOFx1ZDMwNVx1YWNmNVx1YWMwNFx1Yzc0NCBcdWQ2NTVcdWJjZjRcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjXHViMjk0IFx1YzcwNFx1Y2U1OCAxXHVhY2ZjIDhcdWM1ZDAoXHVhYzAwXHVjNmI0XHViMzcwIDRcdWI5N2MgXHVjODFjXHVjNjc4XHVkNTU4XHVhY2UwKSBcdWQzMGNcdWQyZjBcdWMxNThcdWM3NDQgXHViYzMwXHVjZTU4XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNTE0XHVjNzkwXHVjNzc4XHVkNTVjIFx1YmMyOVx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YywgXHVkNTc0XHViMmY5IFx1YmMyOVx1YzVkMFx1YzExYyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViYWE4XHViNGUwIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWJjMjkgXHVkM2VkXHVjNzQ0IFx1YzU0Y1x1YzU0NFx1YjBiNFx1YzViNFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNzQwIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxY1x1YjJlNDogXHVjODA0XHVjY2I0IFx1ZDNlZCBXKDIgJmx0Oz0gVyAmbHQ7PSAxMDApXHVhY2ZjIFx1ZDMwY1x1ZDJmMFx1YzE1OFx1Yzc1OCBcdWFjMWNcdWMyMTggUCgxICZsdDs9IFAgJmx0OyBXKS4gXHVjNzc0XHVjNWI0XHVjOWMwXHViMjk0IFx1YzkwNFx1YzVkMFx1YjI5NCBQXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM4MTVcdWMyMTggTCgwICZsdDsgTCAmbHQ7IFcpXHVjNzQwIFx1ZDU3NFx1YjJmOSBcdWM3MDRcdWNlNThcdWM1ZDAgXHVkMzBjXHVkMmYwXHVjMTU4XHVjNzQ0IFx1YzEyNFx1Y2U1OFx1ZDU2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHVjNzRjXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDMwY1x1ZDJmMFx1YzE1OFx1Yzc1OCBcdWM3MDRcdWNlNThcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3NFx1YmE3MCBcdWM5OWRcdWFjMDBcdWMyMThcdWM1ZjQgXHVkNjE1XHVkMGRjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC5cclxuPFwvcD4iLCJvdXRwdXQiOiI8cD5cdWFkNmNcdWMxMzFcdWFjMDBcdWIyYTVcdWQ1NWMgXHViYWE4XHViNGUwIFx1YmJmOFx1ZDMwNVx1YmMyOVx1Yzc1OCBcdWQwNmNcdWFlMzBcdWI5N2MgXHVjNzkxXHVjNzQwIFx1ZDA2Y1x1YWUzMFx1YmQ4MFx1ZDEzMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LlxyXG48XC9wPiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjEwNDcxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmxleGlibGUgU3BhY2VzIiwiZGVzY3JpcHRpb24iOiI8cD5Hb2xvbWIgSW5kdXN0cmllcyBpcyBkZXNpZ25pbmcgdGhlaXIgbmV3IG9mZmljZSBidWlsZGluZyBmb2xsb3dpbmcgbW9kZXJuIHByaW5jaXBsZXMgdGhhdCBhbGxvdyBmb3IgZmxleGlibGUsIHJlY29uZmlndXJhYmxlIG1lZXRpbmcgc3BhY2VzLiBUaGVpciBwbGFucyBpbmNsdWRlIGEgdmVyeSB3aWRlIHJlY3Rhbmd1bGFyIHJvb20sIHdpdGggYSBzZXJpZXMgb2Ygb3B0aW9uYWwgcGFyYWxsZWwgcGFydGl0aW9ucy48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvZmxleGlibGUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTMzcHg7IHdpZHRoOjMxNXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPkZpZ3VyZSBDLjE6IEFuIGV4YW1wbGUgb2YgYSBjb25maWd1cmFibGUgc3BhY2U8XC9wPlxyXG5cclxuPHA+RmlndXJlIEMuMSBpbGx1c3RyYXRlcyBzdWNoIGEgcm9vbSBoYXZpbmcgYSB3aWR0aCBvZiAxMCB1bml0cyBhbmQgdGhyZWUgb3B0aW9uYWwgcGFydGl0aW9ucyBsb2NhdGVkIDEgdW5pdCwgNCB1bml0cywgYW5kIDggdW5pdHMgYXdheSBmcm9tIHRoZSBsZWZ0IHdhbGwgb2YgdGhlIHJvb20uIFRoZSB3aWR0aCBvZiB0aGUgcm9vbSBhbHdheXMgbWVhc3VyZXMgdGhlIGRpc3RhbmNlIGJldHdlZW4gdGhlIGxlZnQgYW5kIHJpZ2h0IHdhbGxzLCBhbmQgcGFydGl0aW9ucyBhbHdheXMgcnVuIHBhcmFsbGVsIHRvIHRoZXNlIHdhbGxzLiBXZSBkbyBub3QgY29uY2VybiBvdXJzZWx2ZXMgd2l0aCB0aGUgZGVwdGggb2YgdGhlIHJvb20uPFwvcD5cclxuXHJcbjxwPkZvciB0aGlzIGV4YW1wbGUsIGlmIG5vIHBhcnRpdGlvbnMgYXJlIHVzZWQsIGEgbWVldGluZyBjYW4gYmUgaGVsZCBpbiB0aGUgb3JpZ2luYWwgc3BhY2UgaGF2aW5nIHdpZHRoIDEwLiBJZiB0aGUgY29tcGFueSBuZWVkcyBhIHNwYWNlIHRoYXQgaXMgcHJlY2lzZWx5IDQgdW5pdHMgd2lkZSwgdGhleSBjYW4gdXNlIHRoZSBwb3J0aW9uIG9mIHRoZSByb29tIGJldHdlZW4gdGhlIGxlZnQgd2FsbCBhbmQgYSBwYXJ0aXRpb24gcGxhY2VkIGF0IGxvY2F0aW9uIDQgKG9yIHRoZXkgY291bGQgdXNlIHRoZSBwb3J0aW9uIGJldHdlZW4gdGhlIHBhcnRpdGlvbnMgYXQgbG9jYXRpb25zIDQgYW5kIDgpLiBUbyBwcm92aWRlIGEgc3BhY2UgaGF2aW5nIHdpZHRoIDcgdGhleSBjYW4gdXNlIHRoZSBwb3J0aW9uIG9mIHRoZSByb29tIGJldHdlZW4gdGhlIHBhcnRpdGlvbnMgcGxhY2VkIGF0IGxvY2F0aW9ucyAxIGFuZCA4IChvbWl0dGluZyB0aGUgcGFydGl0aW9uIGF0IGxvY2F0aW9uIDQpLjxcL3A+XHJcblxyXG48cD5HaXZlbiBhIHBhcnRpY3VsYXIgcm9vbSBkZXNpZ24sIHlvdXIgam9iIGlzIHRvIGRldGVybWluZSBhbGwgZmVhc2libGUgd2lkdGhzIGZvciBhIG1lZXRpbmcuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzOiB0aGUgb3ZlcmFsbCB3aWR0aCBXIG9mIHRoZSByb29tLCB3aXRoIDIgJmxlOyBXICZsZTsgMTAwLCBhbmQgdGhlIG51bWJlciBQIG9mIGludGVybWVkaWF0ZSBwYXJ0aXRpb25zLCBzdWNoIHRoYXQgMSAmbGU7IFAgJmx0OyBXLiBGb2xsb3dpbmcgdGhhdCBpcyBhIGxpbmUgd2l0aCBQIGludGVnZXJzLCBlYWNoIGRlc2lnbmF0aW5nIHRoZSBsb2NhdGlvbiBMIG9mIGFuIG9wdGlvbmFsIHBhcnRpdGlvbiwgc3VjaCB0aGF0IDAgJmx0OyBMICZsdDsgVy4gRWFjaCBwYXJ0aXRpb24gaXMgYXQgYSBkaXN0aW5jdCBsb2NhdGlvbiBhbmQgdGhlIHBhcnRpdGlvbnMmcnNxdW87IGxvY2F0aW9ucyB3aWxsIGJlIGxpc3RlZCBpbiBpbmNyZWFzaW5nIG9yZGVyLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBzaG91bGQgb3V0cHV0IGEgbGlzdCwgZnJvbSBzbWFsbGVzdCB0byBsYXJnZXN0LCBvZiBlYWNoIGRpc3RpbmN0IHdpZHRoIHRoYXQgY2FuIGJlIGFjaGlldmVkIGZvciBhIG1lZXRpbmcgc3BhY2UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > North America > North America Qualification Contest > ACM-ICPC North America Qualifier 2014 C번

ICPC > Regionals > North America > North America Qualification Contest > ICPC North America Qualifier 2020 D번

  • 문제를 번역한 사람: tae
  • 문제를 만든 사람: Michael Goldwasser