시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 95 23 18 25.000%

문제

항구를 운영하는 상근이는 컨테이너 박스를 보관할 주차장을 건설하려고 한다.

상근이의 항구가 있는 지역은 진흙진 땅이기 때문에, 단단한 땅을 만드는 비용이 매우 비싸다. 따라서, 상근이는 필요 이상으로 주차장을 크게 만들지 않으려고 한다.

컨테이너의 크기는 길이 40미터 너비 8미터이다. 한 컨테이너를 다른 컨테이너 위에 쌓을 수 있고, 최대 5개까지 쌓을 수 있다. 한 행에 있는 컨테이너 사이에는 공간이 4미터 필요하다. 또, 행과 행 사이에는 공간이 2미터가 필요하다. 모든 컨테이너는 같은 방향으로 놓여져야 한다.

주차장의 크기는 직사각형이어야 한다. 상근이가 원하는 수용 가능 컨테이너의 수가 주어졌을 때, 가장 좋은 주차장의 크기를 구하는 프로그램을 작성하시오. 먼저, 주차장의 면적이 작아야 하며, 되도록 정사각형과 가까워야 한다.

예를 들어, 아래와 같이 총 컨테이너 박스가 쌓인 것이 8개 있는 형태를 보관하는 가장 좋은 주차장의 크기는 92 × 42 = 3864이다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100개이다. 각각의 테스트 케이스는 한 줄로 이루어져 있으며, 상근이가 원하는 주차장의 수용 가능 컨테이너 수 n이 주어진다. n은 양의 정수이며, 1012보다 작거나 같다.

출력

각 테스트 케이스마다 가장 좋은 주차장의 길이와 너비를 (길이 ≥ 너비)와 면적을 출력한다. 가능한 정답이 여러 가지인 경우에는 넓이가 가장 작은 것을 출력하며, 넓이가 같은 것도 여러 가지인 경우에는 길이 - 너비가 가장 작은 것을 출력한다.

예제 출력 형식을 참고한다.

예제 입력 1

6
1
15
22
29
36
43

예제 출력 1

48 X 12 = 576
48 X 32 = 1536
52 X 48 = 2496
92 X 32 = 2944
92 X 42 = 3864
136 X 32 = 4352
W3sicHJvYmxlbV9pZCI6IjM2OTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlZThcdWQxNGNcdWM3NzRcdWIxMDgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDU2ZFx1YWQ2Y1x1Yjk3YyBcdWM2YjRcdWM2MDFcdWQ1NThcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Y2VlOFx1ZDE0Y1x1Yzc3NFx1YjEwOCBcdWJjMTVcdWMyYTRcdWI5N2MgXHViY2Y0XHVhZDAwXHVkNTYwIFx1YzhmY1x1Y2MyOFx1YzdhNVx1Yzc0NCBcdWFjNzRcdWMxMjRcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVkNTZkXHVhZDZjXHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWM5YzBcdWM1ZWRcdWM3NDAgXHVjOWM0XHVkNzU5XHVjOWM0IFx1YjU0NVx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YjJlOFx1YjJlOFx1ZDU1YyBcdWI1NDVcdWM3NDQgXHViOWNjXHViNGRjXHViMjk0IFx1YmU0NFx1YzZhOVx1Yzc3NCBcdWI5ZTRcdWM2YjAgXHViZTQ0XHVjMmY4XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWQ1NDRcdWM2OTQgXHVjNzc0XHVjMGMxXHVjNzNjXHViODVjIFx1YzhmY1x1Y2MyOFx1YzdhNVx1Yzc0NCBcdWQwNmNcdWFjOGMgXHViOWNjXHViNGU0XHVjOWMwIFx1YzU0YVx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2VlOFx1ZDE0Y1x1Yzc3NFx1YjEwOFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWIyOTQgXHVhZTM4XHVjNzc0IDQwXHViYmY4XHVkMTMwIFx1YjEwOFx1YmU0NCA4XHViYmY4XHVkMTMwXHVjNzc0XHViMmU0LiBcdWQ1NWMgXHVjZWU4XHVkMTRjXHVjNzc0XHViMTA4XHViOTdjIFx1YjJlNFx1Yjk3OCBcdWNlZThcdWQxNGNcdWM3NzRcdWIxMDggXHVjNzA0XHVjNWQwIFx1YzMxM1x1Yzc0NCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWNkNWNcdWIzMDAgNVx1YWMxY1x1YWU0Y1x1YzljMCBcdWMzMTNcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTVjIFx1ZDU4OVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjZWU4XHVkMTRjXHVjNzc0XHViMTA4IFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWFjZjVcdWFjMDRcdWM3NzQgNFx1YmJmOFx1ZDEzMCBcdWQ1NDRcdWM2OTRcdWQ1NThcdWIyZTQuIFx1YjYxMCwgXHVkNTg5XHVhY2ZjIFx1ZDU4OSBcdWMwYWNcdWM3NzRcdWM1ZDBcdWIyOTQgXHVhY2Y1XHVhYzA0XHVjNzc0IDJcdWJiZjhcdWQxMzBcdWFjMDAgXHVkNTQ0XHVjNjk0XHVkNTU4XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjZWU4XHVkMTRjXHVjNzc0XHViMTA4XHViMjk0IFx1YWMxOVx1Yzc0MCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHViMTkzXHVjNWVjXHVjODM4XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOGZjXHVjYzI4XHVjN2E1XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjNmQwXHVkNTU4XHViMjk0IFx1YzIxOFx1YzZhOSBcdWFjMDBcdWIyYTUgXHVjZWU4XHVkMTRjXHVjNzc0XHViMTA4XHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFjMDBcdWM3YTUgXHVjODhiXHVjNzQwIFx1YzhmY1x1Y2MyOFx1YzdhNVx1Yzc1OCBcdWQwNmNcdWFlMzBcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YmEzY1x1YzgwMCwgXHVjOGZjXHVjYzI4XHVjN2E1XHVjNzU4IFx1YmE3NFx1YzgwMVx1Yzc3NCBcdWM3OTFcdWM1NDRcdWM1N2MgXHVkNTU4XHViYTcwLCBcdWI0MThcdWIzYzRcdWI4NWQgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVhY2ZjIFx1YWMwMFx1YWU0Y1x1YzZjY1x1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjZDFkIFx1Y2VlOFx1ZDE0Y1x1Yzc3NFx1YjEwOCBcdWJjMTVcdWMyYTRcdWFjMDAgXHVjMzEzXHVjNzc4IFx1YWM4M1x1Yzc3NCA4XHVhYzFjIFx1Yzc4OFx1YjI5NCBcdWQ2MTVcdWQwZGNcdWI5N2MgXHViY2Y0XHVhZDAwXHVkNTU4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM4OGJcdWM3NDAgXHVjOGZjXHVjYzI4XHVjN2E1XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCA5MiAmdGltZXM7IDQyID0gMzg2NFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jb250YWluZXIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjI5cHg7IG9wYWNpdHk6MC45OyB3aWR0aDo0NjhweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1Y2Q1Y1x1YjMwMCAxMDBcdWFjMWNcdWM3NzRcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWM4ZmNcdWNjMjhcdWM3YTVcdWM3NTggXHVjMjE4XHVjNmE5IFx1YWMwMFx1YjJhNSBcdWNlZThcdWQxNGNcdWM3NzRcdWIxMDggXHVjMjE4IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBuXHVjNzQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWJhNzAsIDEwPHN1cD4xMjxcL3N1cD5cdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWFjMDBcdWM3YTUgXHVjODhiXHVjNzQwIFx1YzhmY1x1Y2MyOFx1YzdhNVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM2NDAgXHViMTA4XHViZTQ0XHViOTdjIChcdWFlMzhcdWM3NzQgJmdlOyBcdWIxMDhcdWJlNDQpXHVjNjQwIFx1YmE3NFx1YzgwMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWM4MTVcdWIyZjVcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHViMTEzXHVjNzc0XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVhYzgzXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3MCwgXHViMTEzXHVjNzc0XHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWFjODNcdWIzYzQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVhZTM4XHVjNzc0IC0gXHViMTA4XHViZTQ0XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVhYzgzXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHVjODFjIFx1Y2Q5Y1x1YjgyNSBcdWQ2MTVcdWMyZGRcdWM3NDQgXHVjYzM4XHVhY2UwXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM2OTMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb250YWluZXJzIiwiZGVzY3JpcHRpb24iOiI8cD5BdCBhIGNvbnRhaW5lciB0ZXJtaW5hbCwgY29udGFpbmVycyBhcnJpdmUgZnJvbSB0aGUgaGludGVybGFuZCwgb25lIGJ5IG9uZSwgYnkgcmFpbCwgYnkgcm9hZCwgb3IgYnkgc21hbGwgc2hpcHMuIFRoZSBjb250YWluZXJzIGFyZSBwaWxlZCB1cCBhcyB0aGV5IGFycml2ZS4gVGhlbiB0aGUgaHVnZSBjYXJnbyBzaGlwcyBhcnJpdmUsIGVhY2ggb25lIGNhcGFibGUgb2YgY2FycnlpbmcgdGhvdXNhbmRzIG9mIGNvbnRhaW5lcnMuIFRoZSBjb250YWluZXJzIGFyZSBsb2FkZWQgaW50byB0aGUgc2hpcHMgdGhhdCB3aWxsIGJyaW5nIHRoZW0gdG8gZmFyIGF3YXkgc2hvcmVzLiBPciB0aGUgb3RoZXIgd2F5IHJvdW5kLCBjb250YWluZXJzIGFyZSBicm91Z2h0IGluIG92ZXIgc2VhLCBwaWxlZCB1cCwgYW5kIHRyYW5zcG9ydGVkIHRvIHRoZSBoaW50ZXJsYW5kIG9uZSBieSBvbmUuIEFueXdheSwgYSBodWdlIHBhcmtpbmcgbG90IGlzIG5lZWRlZCwgdG8gc3RvcmUgdGhlIGNvbnRhaW5lcnMgd2FpdGluZyBmb3IgZnVydGhlciB0cmFuc3BvcnRhdGlvbi48XC9wPlxyXG5cclxuPHA+QnVpbGRpbmcgdGhlIG5ldyBjb250YWluZXIgdGVybWluYWwgYXQgdGhlIG1vdXRoIG9mIHRoZSByaXZlciB3YXMgYSBnb29kIGNob2ljZS4gQnV0IHRoZXJlIGFyZSBkaXNhZHZhbnRhZ2VzIGFzIHdlbGwuIFRoZSBncm91bmQgaXMgdmVyeSBtdWRkeSwgYW5kIGJ1aWxkaW5nIG9uIFx1ZmIwMXJtIGdyb3VuZCB3b3VsZCBoYXZlIGJlZW4gc3Vic3RhbnRpYWxseSBjaGVhcGVyLiBJdCB3aWxsIGJlIGltcG9ydGFudCB0byBidWlsZCB0aGUgcGFya2luZyBsb3Qgbm90IGxhcmdlciB0aGFuIG5lY2Vzc2FyeS48XC9wPlxyXG5cclxuPHA+QSBjb250YWluZXIgaXMgNDAgZmVldCBsb25nIGFuZCA4IGZlZXQgd2lkZS4gQ29udGFpbmVycyBhcmUgc3RhY2tlZCwgYnV0IGEgc3RhY2sgd2lsbCBiZSBhdCBtb3N0IFx1ZmIwMXZlIGNvbnRhaW5lcnMgaGlnaC4gVGhlIHN0YWNrcyBhcmUgb3JnYW5pemVkIGluIHJvd3MuIE5leHQgdG8gYSBjb250YWluZXIgc3RhY2ssIGFuZCBiZXR3ZWVuIHR3byBjb250YWluZXIgc3RhY2tzIChhbG9uZyB0aGUgbG9uZyBzaWRlIG9mIHRoZSBjb250YWluZXJzKSBhIHNwYWNlIG9mIDIgZmVldCBpcyBuZWVkZWQgZm9yIGNhdGNoaW5nIHRoZSBjb250YWluZXJzLiBOZXh0IHRvIGEgcm93IG9mIHN0YWNrcywgYW5kIGJldHdlZW4gdHdvIHN0YWNrcyAoYWxvbmcgdGhlIHNob3J0IHNpZGUgb2YgdGhlIGNvbnRhaW5lcnMpIGEgc3BhY2Ugb2YgNCBmZWV0IGlzIG5lZWRlZCBmb3IgdGhlIGNyYW5lIHRoYXQgbGlmdHMgdGhlIGNvbnRhaW5lcnMuIEFsbCBjb250YWluZXJzIGFyZSBwbGFjZWQgaW4gdGhlIHNhbWUgZGlyZWN0aW9uLCBhcyB0aGUgY3JhbmVzIGNhbiBub3QgbWFrZSB0dXJucyBvbiB0aGUgcGFya2luZyBsb3QuPFwvcD5cclxuXHJcbjxwPlRoZSBwYXJraW5nIGxvdCBzaG91bGQgYmUgcmVjdGFuZ3VsYXIuIEdpdmVuIHRoZSByZXF1aXJlZCBjYXBhY2l0eSBvZiB0aGUgcGFya2luZyBsb3QsIHdoYXQgd2lsbCBiZSB0aGUgYmVzdCBkaW1lbnNpb24gZm9yIHRoZSBwYXJraW5nIGxvdD8gSW4gdGhlIFx1ZmIwMXJzdCBwbGFjZSB0aGUgYXJlYSBzaG91bGQgYmUgbWluaW1hbC4gVGhlIHNlY29uZCBjb25kaXRpb24gaXMgdGhhdCB0aGUgcGFya2luZyBsb3Qgc2hvdWxkIGJlIGFzIHNxdWFyZSBhcyBwb3NzaWJsZS48XC9wPlxyXG5cclxuPHA+QmVsb3cgeW91IHNlZSBhIHBsYW4gZm9yIGEgcGFya2luZyBsb3Qgd2l0aCBhIGNhcGFjaXR5IG9mIDggc3RhY2tzLiBUd28gcm93cyBvZiBmb3VyIGNvbnRhaW5lcnMgZWFjaCB0dXJucyBvdXQgdG8gYmUgdGhlIGJlc3Qgc29sdXRpb24gaGVyZSwgd2l0aCBhIHRvdGFsIGFyZWEgb2YgOTIgJnRpbWVzOyA0MiA9IDM4NjQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY29udGFpbmVyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIyOXB4OyB3aWR0aDo0NjhweFwiIFwvPjxcL3A+XHJcblxyXG48cD5BIHBhcmtpbmcgbG90IHdpdGggOCBjb250YWluZXIgc3RhY2tzLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBcdWZiMDFyc3QgbGluZSBvbmUgcG9zaXRpdmUgbnVtYmVyOiB0aGUgbnVtYmVyIG9mIHRlc3RjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3RjYXNlOjxcL3A+XHJcblxyXG48cD5BIHNpbmdsZSBwb3NpdGl2ZSBpbnRlZ2VyIG4gKG4gJmxlOyAxMDxzdXA+MTI8XC9zdXA+KSBvbiBhIHNpbmdsZSBsaW5lOiB0aGUgcmVxdWlyZWQgY2FwYWNpdHkgKG51bWJlciBvZiBjb250YWluZXJzKSBmb3IgdGhlIHBhcmtpbmcgbG90LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlBlciB0ZXN0Y2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5BIHNpbmdsZSBsaW5lLCBjb250YWluaW5nIHRoZSBsZW5ndGgsIHdpZHRoIChsZW5ndGggJmdlOyB3aWR0aCkgYW5kIGFyZWEgb2YgdGhlIG9wdGltYWwgc29sdXRpb24uIFRoZSBvcHRpbWFsIHNvbHV0aW9uIGhhcyB0aGUgbGVhc3QgcG9zc2libGUgYXJlYSwgYW5kIGlmIHRoZXJlIGFyZSBtdWx0aXBsZSBzb2x1dGlvbnMgaGF2aW5nIHRoZSBzYW1lIGFyZWEsIHRoZSBkaWZmZXJlbmNlIGxlbmd0aCAmbWludXM7IHdpZHRoIHNob3VsZCBiZSBtaW5pbWFsLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlVzZSB0aGUgc2FtcGxlIGZvcm1hdC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2007 C번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: myungwoo