시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 92 22 17 24.638%

문제

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

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

컨테이너의 크기는 길이 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+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1Y2Q1Y1x1YjMwMCAxMDBcdWFjMWNcdWM3NzRcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWM4ZmNcdWNjMjhcdWM3YTVcdWM3NTggXHVjMjE4XHVjNmE5IFx1YWMwMFx1YjJhNSBcdWNlZThcdWQxNGNcdWM3NzRcdWIxMDggXHVjMjE4IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBuXHVjNzQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWJhNzAsIDEwPHN1cD4xMjxcL3N1cD5cdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWFjMDBcdWM3YTUgXHVjODhiXHVjNzQwIFx1YzhmY1x1Y2MyOFx1YzdhNVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM2NDAgXHViMTA4XHViZTQ0XHViOTdjIChcdWFlMzhcdWM3NzQgJmdlOyBcdWIxMDhcdWJlNDQpXHVjNjQwIFx1YmE3NFx1YzgwMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWM4MTVcdWIyZjVcdWM3NzQgXHVjNWVjXHViN2VjXHVhYzAwXHVjOWMwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWIxMTNcdWM3NzRcdWFjMDAgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWFjODNcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViYTcwLCBcdWIxMTNcdWM3NzRcdWFjMDAgXHVhYzE5XHVjNzQwIFx1YWM4M1x1YjNjNCBcdWM1ZWNcdWI3ZWNcdWFjMDBcdWM5YzBcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YWUzOFx1Yzc3NCAtIFx1YjEwOFx1YmU0NFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YWM4M1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1YzgxYyBcdWNkOWNcdWI4MjUgXHVkNjE1XHVjMmRkXHVjNzQ0IFx1Y2MzOFx1YWNlMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNjkzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ29udGFpbmVycyIsImRlc2NyaXB0aW9uIjoiPHA+QXQgYSBjb250YWluZXIgdGVybWluYWwsIGNvbnRhaW5lcnMgYXJyaXZlIGZyb20gdGhlIGhpbnRlcmxhbmQsIG9uZSBieSBvbmUsIGJ5IHJhaWwsIGJ5IHJvYWQsIG9yIGJ5IHNtYWxsIHNoaXBzLiBUaGUgY29udGFpbmVycyBhcmUgcGlsZWQgdXAgYXMgdGhleSBhcnJpdmUuIFRoZW4gdGhlIGh1Z2UgY2FyZ28gc2hpcHMgYXJyaXZlLCBlYWNoIG9uZSBjYXBhYmxlIG9mIGNhcnJ5aW5nIHRob3VzYW5kcyBvZiBjb250YWluZXJzLiBUaGUgY29udGFpbmVycyBhcmUgbG9hZGVkIGludG8gdGhlIHNoaXBzIHRoYXQgd2lsbCBicmluZyB0aGVtIHRvIGZhciBhd2F5IHNob3Jlcy4gT3IgdGhlIG90aGVyIHdheSByb3VuZCwgY29udGFpbmVycyBhcmUgYnJvdWdodCBpbiBvdmVyIHNlYSwgcGlsZWQgdXAsIGFuZCB0cmFuc3BvcnRlZCB0byB0aGUgaGludGVybGFuZCBvbmUgYnkgb25lLiBBbnl3YXksIGEgaHVnZSBwYXJraW5nIGxvdCBpcyBuZWVkZWQsIHRvIHN0b3JlIHRoZSBjb250YWluZXJzIHdhaXRpbmcgZm9yIGZ1cnRoZXIgdHJhbnNwb3J0YXRpb24uPFwvcD5cclxuXHJcbjxwPkJ1aWxkaW5nIHRoZSBuZXcgY29udGFpbmVyIHRlcm1pbmFsIGF0IHRoZSBtb3V0aCBvZiB0aGUgcml2ZXIgd2FzIGEgZ29vZCBjaG9pY2UuIEJ1dCB0aGVyZSBhcmUgZGlzYWR2YW50YWdlcyBhcyB3ZWxsLiBUaGUgZ3JvdW5kIGlzIHZlcnkgbXVkZHksIGFuZCBidWlsZGluZyBvbiBcdWZiMDFybSBncm91bmQgd291bGQgaGF2ZSBiZWVuIHN1YnN0YW50aWFsbHkgY2hlYXBlci4gSXQgd2lsbCBiZSBpbXBvcnRhbnQgdG8gYnVpbGQgdGhlIHBhcmtpbmcgbG90IG5vdCBsYXJnZXIgdGhhbiBuZWNlc3NhcnkuPFwvcD5cclxuXHJcbjxwPkEgY29udGFpbmVyIGlzIDQwIGZlZXQgbG9uZyBhbmQgOCBmZWV0IHdpZGUuIENvbnRhaW5lcnMgYXJlIHN0YWNrZWQsIGJ1dCBhIHN0YWNrIHdpbGwgYmUgYXQgbW9zdCBcdWZiMDF2ZSBjb250YWluZXJzIGhpZ2guIFRoZSBzdGFja3MgYXJlIG9yZ2FuaXplZCBpbiByb3dzLiBOZXh0IHRvIGEgY29udGFpbmVyIHN0YWNrLCBhbmQgYmV0d2VlbiB0d28gY29udGFpbmVyIHN0YWNrcyAoYWxvbmcgdGhlIGxvbmcgc2lkZSBvZiB0aGUgY29udGFpbmVycykgYSBzcGFjZSBvZiAyIGZlZXQgaXMgbmVlZGVkIGZvciBjYXRjaGluZyB0aGUgY29udGFpbmVycy4gTmV4dCB0byBhIHJvdyBvZiBzdGFja3MsIGFuZCBiZXR3ZWVuIHR3byBzdGFja3MgKGFsb25nIHRoZSBzaG9ydCBzaWRlIG9mIHRoZSBjb250YWluZXJzKSBhIHNwYWNlIG9mIDQgZmVldCBpcyBuZWVkZWQgZm9yIHRoZSBjcmFuZSB0aGF0IGxpZnRzIHRoZSBjb250YWluZXJzLiBBbGwgY29udGFpbmVycyBhcmUgcGxhY2VkIGluIHRoZSBzYW1lIGRpcmVjdGlvbiwgYXMgdGhlIGNyYW5lcyBjYW4gbm90IG1ha2UgdHVybnMgb24gdGhlIHBhcmtpbmcgbG90LjxcL3A+XHJcblxyXG48cD5UaGUgcGFya2luZyBsb3Qgc2hvdWxkIGJlIHJlY3Rhbmd1bGFyLiBHaXZlbiB0aGUgcmVxdWlyZWQgY2FwYWNpdHkgb2YgdGhlIHBhcmtpbmcgbG90LCB3aGF0IHdpbGwgYmUgdGhlIGJlc3QgZGltZW5zaW9uIGZvciB0aGUgcGFya2luZyBsb3Q/IEluIHRoZSBcdWZiMDFyc3QgcGxhY2UgdGhlIGFyZWEgc2hvdWxkIGJlIG1pbmltYWwuIFRoZSBzZWNvbmQgY29uZGl0aW9uIGlzIHRoYXQgdGhlIHBhcmtpbmcgbG90IHNob3VsZCBiZSBhcyBzcXVhcmUgYXMgcG9zc2libGUuPFwvcD5cclxuXHJcbjxwPkJlbG93IHlvdSBzZWUgYSBwbGFuIGZvciBhIHBhcmtpbmcgbG90IHdpdGggYSBjYXBhY2l0eSBvZiA4IHN0YWNrcy4gVHdvIHJvd3Mgb2YgZm91ciBjb250YWluZXJzIGVhY2ggdHVybnMgb3V0IHRvIGJlIHRoZSBiZXN0IHNvbHV0aW9uIGhlcmUsIHdpdGggYSB0b3RhbCBhcmVhIG9mIDkyICZ0aW1lczsgNDIgPSAzODY0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2NvbnRhaW5lci5wbmdcIiBzdHlsZT1cImhlaWdodDoyMjlweDsgd2lkdGg6NDY4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+QSBwYXJraW5nIGxvdCB3aXRoIDggY29udGFpbmVyIHN0YWNrcy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgXHVmYjAxcnN0IGxpbmUgb25lIHBvc2l0aXZlIG51bWJlcjogdGhlIG51bWJlciBvZiB0ZXN0Y2FzZXMsIGF0IG1vc3QgMTAwLiBBZnRlciB0aGF0IHBlciB0ZXN0Y2FzZTo8XC9wPlxyXG5cclxuPHA+QSBzaW5nbGUgcG9zaXRpdmUgaW50ZWdlciBuIChuICZsZTsgMTA8c3VwPjEyPFwvc3VwPikgb24gYSBzaW5nbGUgbGluZTogdGhlIHJlcXVpcmVkIGNhcGFjaXR5IChudW1iZXIgb2YgY29udGFpbmVycykgZm9yIHRoZSBwYXJraW5nIGxvdC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QZXIgdGVzdGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+QSBzaW5nbGUgbGluZSwgY29udGFpbmluZyB0aGUgbGVuZ3RoLCB3aWR0aCAobGVuZ3RoICZnZTsgd2lkdGgpIGFuZCBhcmVhIG9mIHRoZSBvcHRpbWFsIHNvbHV0aW9uLiBUaGUgb3B0aW1hbCBzb2x1dGlvbiBoYXMgdGhlIGxlYXN0IHBvc3NpYmxlIGFyZWEsIGFuZCBpZiB0aGVyZSBhcmUgbXVsdGlwbGUgc29sdXRpb25zIGhhdmluZyB0aGUgc2FtZSBhcmVhLCB0aGUgZGlmZmVyZW5jZSBsZW5ndGggJm1pbnVzOyB3aWR0aCBzaG91bGQgYmUgbWluaW1hbC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Vc2UgdGhlIHNhbXBsZSBmb3JtYXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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