시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 134 26 21 20.192%

문제

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

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

컨테이너의 크기는 길이 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+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzY5MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNvbnRhaW5lcnMiLCJkZXNjcmlwdGlvbiI6IjxwPkF0IGEgY29udGFpbmVyIHRlcm1pbmFsLCBjb250YWluZXJzIGFycml2ZSBmcm9tIHRoZSBoaW50ZXJsYW5kLCBvbmUgYnkgb25lLCBieSByYWlsLCBieSByb2FkLCBvciBieSBzbWFsbCBzaGlwcy4gVGhlIGNvbnRhaW5lcnMgYXJlIHBpbGVkIHVwIGFzIHRoZXkgYXJyaXZlLiBUaGVuIHRoZSBodWdlIGNhcmdvIHNoaXBzIGFycml2ZSwgZWFjaCBvbmUgY2FwYWJsZSBvZiBjYXJyeWluZyB0aG91c2FuZHMgb2YgY29udGFpbmVycy4gVGhlIGNvbnRhaW5lcnMgYXJlIGxvYWRlZCBpbnRvIHRoZSBzaGlwcyB0aGF0IHdpbGwgYnJpbmcgdGhlbSB0byBmYXIgYXdheSBzaG9yZXMuIE9yIHRoZSBvdGhlciB3YXkgcm91bmQsIGNvbnRhaW5lcnMgYXJlIGJyb3VnaHQgaW4gb3ZlciBzZWEsIHBpbGVkIHVwLCBhbmQgdHJhbnNwb3J0ZWQgdG8gdGhlIGhpbnRlcmxhbmQgb25lIGJ5IG9uZS4gQW55d2F5LCBhIGh1Z2UgcGFya2luZyBsb3QgaXMgbmVlZGVkLCB0byBzdG9yZSB0aGUgY29udGFpbmVycyB3YWl0aW5nIGZvciBmdXJ0aGVyIHRyYW5zcG9ydGF0aW9uLjxcL3A+XHJcblxyXG48cD5CdWlsZGluZyB0aGUgbmV3IGNvbnRhaW5lciB0ZXJtaW5hbCBhdCB0aGUgbW91dGggb2YgdGhlIHJpdmVyIHdhcyBhIGdvb2QgY2hvaWNlLiBCdXQgdGhlcmUgYXJlIGRpc2FkdmFudGFnZXMgYXMgd2VsbC4gVGhlIGdyb3VuZCBpcyB2ZXJ5IG11ZGR5LCBhbmQgYnVpbGRpbmcgb24gXHVmYjAxcm0gZ3JvdW5kIHdvdWxkIGhhdmUgYmVlbiBzdWJzdGFudGlhbGx5IGNoZWFwZXIuIEl0IHdpbGwgYmUgaW1wb3J0YW50IHRvIGJ1aWxkIHRoZSBwYXJraW5nIGxvdCBub3QgbGFyZ2VyIHRoYW4gbmVjZXNzYXJ5LjxcL3A+XHJcblxyXG48cD5BIGNvbnRhaW5lciBpcyA0MCBmZWV0IGxvbmcgYW5kIDggZmVldCB3aWRlLiBDb250YWluZXJzIGFyZSBzdGFja2VkLCBidXQgYSBzdGFjayB3aWxsIGJlIGF0IG1vc3QgXHVmYjAxdmUgY29udGFpbmVycyBoaWdoLiBUaGUgc3RhY2tzIGFyZSBvcmdhbml6ZWQgaW4gcm93cy4gTmV4dCB0byBhIGNvbnRhaW5lciBzdGFjaywgYW5kIGJldHdlZW4gdHdvIGNvbnRhaW5lciBzdGFja3MgKGFsb25nIHRoZSBsb25nIHNpZGUgb2YgdGhlIGNvbnRhaW5lcnMpIGEgc3BhY2Ugb2YgMiBmZWV0IGlzIG5lZWRlZCBmb3IgY2F0Y2hpbmcgdGhlIGNvbnRhaW5lcnMuIE5leHQgdG8gYSByb3cgb2Ygc3RhY2tzLCBhbmQgYmV0d2VlbiB0d28gc3RhY2tzIChhbG9uZyB0aGUgc2hvcnQgc2lkZSBvZiB0aGUgY29udGFpbmVycykgYSBzcGFjZSBvZiA0IGZlZXQgaXMgbmVlZGVkIGZvciB0aGUgY3JhbmUgdGhhdCBsaWZ0cyB0aGUgY29udGFpbmVycy4gQWxsIGNvbnRhaW5lcnMgYXJlIHBsYWNlZCBpbiB0aGUgc2FtZSBkaXJlY3Rpb24sIGFzIHRoZSBjcmFuZXMgY2FuIG5vdCBtYWtlIHR1cm5zIG9uIHRoZSBwYXJraW5nIGxvdC48XC9wPlxyXG5cclxuPHA+VGhlIHBhcmtpbmcgbG90IHNob3VsZCBiZSByZWN0YW5ndWxhci4gR2l2ZW4gdGhlIHJlcXVpcmVkIGNhcGFjaXR5IG9mIHRoZSBwYXJraW5nIGxvdCwgd2hhdCB3aWxsIGJlIHRoZSBiZXN0IGRpbWVuc2lvbiBmb3IgdGhlIHBhcmtpbmcgbG90PyBJbiB0aGUgXHVmYjAxcnN0IHBsYWNlIHRoZSBhcmVhIHNob3VsZCBiZSBtaW5pbWFsLiBUaGUgc2Vjb25kIGNvbmRpdGlvbiBpcyB0aGF0IHRoZSBwYXJraW5nIGxvdCBzaG91bGQgYmUgYXMgc3F1YXJlIGFzIHBvc3NpYmxlLjxcL3A+XHJcblxyXG48cD5CZWxvdyB5b3Ugc2VlIGEgcGxhbiBmb3IgYSBwYXJraW5nIGxvdCB3aXRoIGEgY2FwYWNpdHkgb2YgOCBzdGFja3MuIFR3byByb3dzIG9mIGZvdXIgY29udGFpbmVycyBlYWNoIHR1cm5zIG91dCB0byBiZSB0aGUgYmVzdCBzb2x1dGlvbiBoZXJlLCB3aXRoIGEgdG90YWwgYXJlYSBvZiA5MiAmdGltZXM7IDQyID0gMzg2NC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jb250YWluZXIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjI5cHg7IHdpZHRoOjQ2OHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkEgcGFya2luZyBsb3Qgd2l0aCA4IGNvbnRhaW5lciBzdGFja3MuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIFx1ZmIwMXJzdCBsaW5lIG9uZSBwb3NpdGl2ZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdGNhc2VzLCBhdCBtb3N0IDEwMC4gQWZ0ZXIgdGhhdCBwZXIgdGVzdGNhc2U6PFwvcD5cclxuXHJcbjxwPkEgc2luZ2xlIHBvc2l0aXZlIGludGVnZXIgbiAobiAmbGU7IDEwPHN1cD4xMjxcL3N1cD4pIG9uIGEgc2luZ2xlIGxpbmU6IHRoZSByZXF1aXJlZCBjYXBhY2l0eSAobnVtYmVyIG9mIGNvbnRhaW5lcnMpIGZvciB0aGUgcGFya2luZyBsb3QuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3RjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkEgc2luZ2xlIGxpbmUsIGNvbnRhaW5pbmcgdGhlIGxlbmd0aCwgd2lkdGggKGxlbmd0aCAmZ2U7IHdpZHRoKSBhbmQgYXJlYSBvZiB0aGUgb3B0aW1hbCBzb2x1dGlvbi4gVGhlIG9wdGltYWwgc29sdXRpb24gaGFzIHRoZSBsZWFzdCBwb3NzaWJsZSBhcmVhLCBhbmQgaWYgdGhlcmUgYXJlIG11bHRpcGxlIHNvbHV0aW9ucyBoYXZpbmcgdGhlIHNhbWUgYXJlYSwgdGhlIGRpZmZlcmVuY2UgbGVuZ3RoICZtaW51czsgd2lkdGggc2hvdWxkIGJlIG1pbmltYWwuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VXNlIHRoZSBzYW1wbGUgZm9ybWF0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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