시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB417695921.612%

문제

재현이는 마인크래프트를 너무 많이 한 나머지, 우리가 사는 지구 또한 직육면체 모양이어야 한다고 생각하게 되었다. 재현이는 자신이 가진 군단을 동원하여, 지구를 각 변의 길이가 ℓx × ℓy × ℓz인 직육면체로 만드는 대공사를 했다. 이 공사로 인해 새로운 모양의 지구 표면 위에서의 위치는 깔끔하게 3차원 데카르트 좌표계로 표현되게 되었고, 재현이는 크게 만족해했다. 또한, 재현이는 그리니치 천문대를 없애고, 자신의 집을 지구의 꼭짓점 (0, 0, 0)에 지었다.

한편, 이번 공사로 인해 집이 강제로 (x, y, z)에 옮겨진 승원이는 물리를 공부하던 도중, 물리 책에서 재현이의 집이 지구 좌표계의 기준으로 소개되고 있는 것을 발견했다. 자신의 성스러운 물리 책에서는 재현이의 이름조차 보기 싫었던 승원이는 페이스북에서 지구가 다시 둥글어져야 한다고 주장하기 시작했다.

페이스북을 통해 이 사실을 알게 된 재현이는 승원이를 체포하기 위해, 승원이에게 가기 위한 최단경로의 길이가 얼마인지 궁금해하게 되었다. 재현이를 도와 승원이가 다시는 허튼 수작을 부리지 못하도록 만들자.

만약 ℓx = 1, ℓ= 2, ℓ= 1, x = 1, y = 2, z = 1이라면, (0, 0, 0)에 있는 재현이가 (1, 2, 1)에 있는 승원이에게 가기 위한 최단경로는 (0, 0, 0)에서 (1, 1, 0)을 거쳐, (1, 2, 1)로 가는 경로이다. 이 최단경로의 길이는 √8 이다.

입력

각 입력 파일은 여러 개의 테스트 케이스를 포함하며, 각각은 6개의 정수 ℓx, ℓy, ℓz, x, y, z (단, 1 ≤ ℓx, ℓy, ℓz ≤ 1000) 으로 이루어진다. 승원이의 위치 (x,y,z)는 항상 직육면체 지구의 6개의 면들 중 하나 위에 있음이 보장된다. 또한, 파일의 마지막 줄은 ℓx = ℓy = ℓz = x = y = z = 0 인 경우로 되어 있으며, 이에 대해서는 답을 출력하지 않아야 한다.

출력

각각의 테스트 케이스에 대해, 한 줄에 최단경로의 길이의 제곱을 나타내는 양의 정수를 출력하시오. (주의 : 최단경로의 길이의 제곱은 항상 정수이므로, 답은 근사치가 아닌 정확한 값으로 출력되어야 한다.)

예제 입력 1

1 1 2 1 1 2
1 1 1 1 1 1
0 0 0 0 0 0

예제 출력 1

8
5
W3sicHJvYmxlbV9pZCI6Ijc2ODciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5YzBcdWFkNmMgXHVjOWMxXHVjNzIxXHViYTc0XHVjY2I0XHVjMTI0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3YWNcdWQ2MDRcdWM3NzRcdWIyOTQgXHViOWM4XHVjNzc4XHVkMDZjXHViNzk4XHVkNTA0XHVkMmI4XHViOTdjIFx1YjEwOFx1YmIzNCBcdWI5Y2VcdWM3NzQgXHVkNTVjIFx1YjA5OFx1YmEzOFx1YzljMCwgXHVjNmIwXHViOWFjXHVhYzAwIFx1YzBhY1x1YjI5NCBcdWM5YzBcdWFkNmMgXHViNjEwXHVkNTVjIFx1YzljMVx1YzcyMVx1YmE3NFx1Y2NiNCBcdWJhYThcdWM1OTFcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU1OFx1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuIFx1YzdhY1x1ZDYwNFx1Yzc3NFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVhYzAwXHVjOWM0IFx1YWQ3MFx1YjJlOFx1Yzc0NCBcdWIzZDlcdWM2ZDBcdWQ1NThcdWM1ZWMsIFx1YzljMFx1YWQ2Y1x1Yjk3YyBcdWFjMDEgXHViY2MwXHVjNzU4Jm5ic3A7XHVhZTM4XHVjNzc0XHVhYzAwIFx1MjExMzxzdWI+eDxcL3N1Yj4mbmJzcDsmdGltZXM7IFx1MjExMzxzdWI+eTxcL3N1Yj4mbmJzcDsmdGltZXM7IFx1MjExMzxzdWI+ejxcL3N1Yj5cdWM3NzgmbmJzcDtcdWM5YzFcdWM3MjFcdWJhNzRcdWNjYjRcdWI4NWMgXHViOWNjXHViNGRjXHViMjk0IFx1YjMwMFx1YWNmNVx1YzBhY1x1Yjk3YyBcdWQ1ODhcdWIyZTQuIFx1Yzc3NCBcdWFjZjVcdWMwYWNcdWI4NWMgXHVjNzc4XHVkNTc0IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWJhYThcdWM1OTFcdWM3NTggXHVjOWMwXHVhZDZjIFx1ZDQ1Y1x1YmE3NCBcdWM3MDRcdWM1ZDBcdWMxMWNcdWM3NTggXHVjNzA0XHVjZTU4XHViMjk0IFx1YWU1NFx1YjA1NFx1ZDU1OFx1YWM4YyAzXHVjYzI4XHVjNmQwIFx1YjM3MFx1Y2U3NFx1Yjk3NFx1ZDJiOCBcdWM4OGNcdWQ0NWNcdWFjYzRcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDE4XHVhYzhjIFx1YjQxOFx1YzVjOFx1YWNlMCwgXHVjN2FjXHVkNjA0XHVjNzc0XHViMjk0IFx1ZDA2Y1x1YWM4YyBcdWI5Y2NcdWM4NzFcdWQ1NzRcdWQ1ODhcdWIyZTQuJm5ic3A7XHViNjEwXHVkNTVjLCBcdWM3YWNcdWQ2MDRcdWM3NzRcdWIyOTQgXHVhZGY4XHViOWFjXHViMmM4XHVjZTU4IFx1Y2M5Y1x1YmIzOFx1YjMwMFx1Yjk3YyBcdWM1YzZcdWM1NjBcdWFjZTAsIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWM5ZDFcdWM3NDQgXHVjOWMwXHVhZDZjXHVjNzU4IFx1YWYyZFx1YzlkM1x1YzgxMCAoMCwgMCwgMClcdWM1ZDAgXHVjOWMwXHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NWNcdWQzYjgsIFx1Yzc3NFx1YmM4OCBcdWFjZjVcdWMwYWNcdWI4NWMgXHVjNzc4XHVkNTc0IFx1YzlkMVx1Yzc3NCBcdWFjMTVcdWM4MWNcdWI4NWMgKHgsIHksIHopXHVjNWQwIFx1YzYyZVx1YWNhOFx1YzljNCBcdWMyYjlcdWM2ZDBcdWM3NzRcdWIyOTQgXHViYjNjXHViOWFjXHViOTdjIFx1YWNmNVx1YmQ4MFx1ZDU1OFx1YjM1OCBcdWIzYzRcdWM5MTEsIFx1YmIzY1x1YjlhYyBcdWNjNDVcdWM1ZDBcdWMxMWMgXHVjN2FjXHVkNjA0XHVjNzc0XHVjNzU4IFx1YzlkMVx1Yzc3NCBcdWM5YzBcdWFkNmMgXHVjODhjXHVkNDVjXHVhY2M0XHVjNzU4IFx1YWUzMFx1YzkwMFx1YzczY1x1Yjg1YyBcdWMxOGNcdWFjMWNcdWI0MThcdWFjZTAgXHVjNzg4XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWJjMWNcdWFjYWNcdWQ1ODhcdWIyZTQuIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWMxMzFcdWMyYTRcdWI3ZWNcdWM2YjQgXHViYjNjXHViOWFjIFx1Y2M0NVx1YzVkMFx1YzExY1x1YjI5NCBcdWM3YWNcdWQ2MDRcdWM3NzRcdWM3NTggXHVjNzc0XHViOTg0XHVjODcwXHVjYzI4IFx1YmNmNFx1YWUzMCBcdWMyZWJcdWM1YzhcdWIzNTggXHVjMmI5XHVjNmQwXHVjNzc0XHViMjk0IFx1ZDM5OFx1Yzc3NFx1YzJhNFx1YmQ4MVx1YzVkMFx1YzExYyBcdWM5YzBcdWFkNmNcdWFjMDAgXHViMmU0XHVjMmRjIFx1YjQ2NVx1YWUwMFx1YzViNFx1YzgzOFx1YzU3YyBcdWQ1NWNcdWIyZTRcdWFjZTAgXHVjOGZjXHVjN2E1XHVkNTU4XHVhZTMwIFx1YzJkY1x1Yzc5MVx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMzk4XHVjNzc0XHVjMmE0XHViZDgxXHVjNzQ0IFx1ZDFiNVx1ZDU3NCBcdWM3NzQgXHVjMGFjXHVjMmU0XHVjNzQ0IFx1YzU0Y1x1YWM4YyBcdWI0MWMgXHVjN2FjXHVkNjA0XHVjNzc0XHViMjk0IFx1YzJiOVx1YzZkMFx1Yzc3NFx1Yjk3YyBcdWNjYjRcdWQzZWNcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0LCBcdWMyYjlcdWM2ZDBcdWM3NzRcdWM1ZDBcdWFjOGMgXHVhYzAwXHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWNkNWNcdWIyZThcdWFjYmRcdWI4NWNcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIFx1YzViY1x1YjljOFx1Yzc3OFx1YzljMCBcdWFkODFcdWFlMDhcdWQ1NzRcdWQ1NThcdWFjOGMgXHViNDE4XHVjNWM4XHViMmU0LiBcdWM3YWNcdWQ2MDRcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwIFx1YzJiOVx1YzZkMFx1Yzc3NFx1YWMwMCBcdWIyZTRcdWMyZGNcdWIyOTQgXHVkNWM4XHVkMmJjIFx1YzIxOFx1Yzc5MVx1Yzc0NCBcdWJkODBcdWI5YWNcdWM5YzAgXHViYWJiXHVkNTU4XHViM2M0XHViODVkIFx1YjljY1x1YjRlNFx1Yzc5MC48XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkIFx1MjExMzxzdWI+eDxcL3N1Yj4mbmJzcDs9IDEsIFx1MjExMzxzdWI+eSZuYnNwOzxcL3N1Yj49IDIsIFx1MjExMzxzdWI+eiZuYnNwOzxcL3N1Yj49IDEsIHggPSAxLCB5ID0gMiwgeiA9IDFcdWM3NzRcdWI3N2NcdWJhNzQsICgwLCAwLCAwKVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjN2FjXHVkNjA0XHVjNzc0XHVhYzAwICgxLCAyLCAxKVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMmI5XHVjNmQwXHVjNzc0XHVjNWQwXHVhYzhjIFx1YWMwMFx1YWUzMCBcdWM3MDRcdWQ1NWMgXHVjZDVjXHViMmU4XHVhY2JkXHViODVjXHViMjk0ICgwLCAwLCAwKVx1YzVkMFx1YzExYyAoMSwgMSwgMClcdWM3NDQgXHVhYzcwXHVjY2QwLCAoMSwgMiwgMSlcdWI4NWMgXHVhYzAwXHViMjk0IFx1YWNiZFx1Yjg1Y1x1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1Y2Q1Y1x1YjJlOFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQmbmJzcDsmcmFkaWM7OCBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWFjMDEgXHVjNzg1XHViODI1IFx1ZDMwY1x1Yzc3Y1x1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTU4XHViYTcwLCBcdWFjMDFcdWFjMDFcdWM3NDAgNlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggXHUyMTEzPHN1Yj54PFwvc3ViPiwgXHUyMTEzPHN1Yj55PFwvc3ViPiwgXHUyMTEzPHN1Yj56PFwvc3ViPiwgeCwgeSwgeiZuYnNwOyhcdWIyZTgsJm5ic3A7MSAmbGU7IFx1MjExMzxzdWI+eDxcL3N1Yj4sJm5ic3A7XHUyMTEzPHN1Yj55PFwvc3ViPiwmbmJzcDtcdTIxMTM8c3ViPno8XC9zdWI+Jm5ic3A7JmxlOyAxMDAwKSBcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwO1x1YzJiOVx1YzZkMFx1Yzc3NFx1Yzc1OCBcdWM3MDRcdWNlNTggKHgseSx6KVx1YjI5NCBcdWQ1NmRcdWMwYzEgXHVjOWMxXHVjNzIxXHViYTc0XHVjY2I0IFx1YzljMFx1YWQ2Y1x1Yzc1OCA2XHVhYzFjXHVjNzU4IFx1YmE3NFx1YjRlNCBcdWM5MTEgXHVkNTU4XHViMDk4IFx1YzcwNFx1YzVkMCBcdWM3ODhcdWM3NGNcdWM3NzQgXHViY2Y0XHVjN2E1XHViNDFjXHViMmU0LiBcdWI2MTBcdWQ1NWMsIFx1ZDMwY1x1Yzc3Y1x1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNzQwIFx1MjExMzxzdWI+eDxcL3N1Yj4mbmJzcDs9IFx1MjExMzxzdWI+eTxcL3N1Yj4mbmJzcDs9IFx1MjExMzxzdWI+ejxcL3N1Yj4mbmJzcDs9IHggPSB5ID0geiA9IDAgXHVjNzc4IFx1YWNiZFx1YzZiMFx1Yjg1YyBcdWI0MThcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWM3NzRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjXHViMjk0IFx1YjJmNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQsIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVjZDVjXHViMmU4XHVhY2JkXHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWM4MWNcdWFjZjFcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjMmRjXHVjNjI0LiAoXHVjOGZjXHVjNzU4IDogXHVjZDVjXHViMmU4XHVhY2JkXHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWM4MWNcdWFjZjFcdWM3NDAgXHVkNTZkXHVjMGMxIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YmJjMFx1Yjg1YywgXHViMmY1XHVjNzQwIFx1YWRmY1x1YzBhY1x1Y2U1OFx1YWMwMCBcdWM1NDRcdWIyY2MgXHVjODE1XHVkNjU1XHVkNTVjIFx1YWMxMlx1YzczY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0Lik8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI3Njg3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQm94IHdhbGtpbmciLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgZ2l2ZW4gYSB0aHJlZS1kaW1lbnNpb25hbCBib3ggb2YgaW50ZWdyYWwgZGltZW5zaW9ucyBcdTIxMTM8c3ViPng8XC9zdWI+ICZ0aW1lczsgXHUyMTEzPHN1Yj55PFwvc3ViPiAmdGltZXM7IFx1MjExMzxzdWI+ejxcL3N1Yj4gVGhlIGVkZ2VzIG9mIHRoZSBib3ggYXJlIGF4aXNhbGlnbmVkLCBhbmQgb25lIGNvcm5lciBvZiB0aGUgYm94IGlzIGxvY2F0ZWQgYXQgcG9zaXRpb24gKDAsIDAsIDApLiBHaXZlbiB0aGUgY29vcmRpbmF0ZXMgKHgsIHksIHopIG9mIHNvbWUgYXJiaXRyYXJ5IHBvc2l0aW9uIG9uIHRoZSBzdXJmYWNlIG9mIHRoZSBib3gsIHlvdXIgZ29hbCBpcyB0byByZXR1cm4gdGhlIHNxdWFyZSBvZiB0aGUgbGVuZ3RoIG9mIHRoZSBzaG9ydGVzdCBwYXRoIGFsb25nIHRoZSBib3gmcnNxdW87cyBzdXJmYWNlIGZyb20gKDAsIDAsIDApIHRvICh4LCB5LCB6KS48XC9wPlxyXG5cclxuPHA+SWYgXHUyMTEzPHN1Yj54PFwvc3ViPiA9IDEsIFx1MjExMzxzdWI+eTxcL3N1Yj4gPSAyLCBhbmQgXHUyMTEzPHN1Yj56PFwvc3ViPiA9IDEsIHRoZW4gdGhlIHNob3J0ZXN0IHBhdGggZnJvbSAoMCwgMCwgMCkgdG8gKDEsIDIsIDEpIGlzIGZvdW5kIGJ5IHdhbGtpbmcgZnJvbSAoMCwgMCwgMCkgdG8gKDEsIDEsIDApLCBmb2xsb3dlZCBieSB3YWxraW5nIGZyb20gKDEsIDEsIDApIHRvICgxLCAyLCAxKS4gVGhlIHRvdGFsIHBhdGggbGVuZ3RoIGlzICZyYWRpYzs4PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgdGVzdCBmaWxlIHdpbGwgY29udGFpbiBtdWx0aXBsZSB0ZXN0IGNhc2VzLCBlYWNoIG9mIHdoaWNoIGNvbnNpc3RzIG9mIHNpeCBpbnRlZ2VycyBcdTIxMTM8c3ViPng8XC9zdWI+LCBcdTIxMTM8c3ViPnk8XC9zdWI+LCBcdTIxMTM8c3ViPno8XC9zdWI+LCB4LCB5LCB6IHdoZXJlIDEgJmxlOyBcdTIxMTM8c3ViPng8XC9zdWI+LCZuYnNwO1x1MjExMzxzdWI+eTxcL3N1Yj4sJm5ic3A7XHUyMTEzPHN1Yj56PFwvc3ViPiAmbGU7IDEwMDAuIE5vdGUgdGhhdCB0aGUgYm94IG1heSBoYXZlIHplcm8gdm9sdW1lLCBidXQgdGhlIHBvaW50ICh4LCB5LCB6KSBpcyBhbHdheXMgZ3VhcmFudGVlZCB0byBiZSBvbiBvbmUgb2YgdGhlIHNpeCBzaWRlcyBvZiB0aGUgYm94LiBUaGUgZW5kLW9mLWZpbGUgaXMgbWFya2VkIGJ5IGEgdGVzdCBjYXNlIHdpdGggXHUyMTEzPHN1Yj54PFwvc3ViPiA9IFx1MjExMzxzdWI+eTxcL3N1Yj4gPSBcdTIxMTM8c3ViPno8XC9zdWI+ID0geCA9IHkgPSB6ID0gMCBhbmQgc2hvdWxkIG5vdCBiZSBwcm9jZXNzZWQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCB3cml0ZSBhIHNpbmdsZSBsaW5lIHdpdGggYSBwb3NpdGl2ZSBpbnRlZ2VyIGluZGljYXRpbmcgdGhlIHNxdWFyZSBvZiB0aGUgc2hvcnRlc3QgcGF0aCBsZW5ndGguIChOb3RlOiBUaGUgc3F1YXJlIG9mIHRoZSBwYXRoIGxlbmd0aCBpcyBhbHdheXMgYW4gaW50ZWdlcjsgdGh1cywgeW91ciBhbnN3ZXIgaXMgZXhhY3QsIG5vdCBhcHByb3hpbWF0ZS4pPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

University > Stanford Local ACM Programming Contest > SLPC 2005 5번

  • 문제를 번역한 사람: veydpz