시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1829 1032 893 57.987%

문제

상근이는 변의 길이가 1인 정사각형 n개를 가지고 있다. 이 정사각형을 이용해서 만들 수 있는 직사각형의 개수는 총 몇 개일까?

두 직사각형 A와 B가 있을 때, A를 이동, 회전시켜서 B를 만들 수 없으면, 두 직사각형은 다르다고 한다. 직사각형을 만들 때, 정사각형을 변형시키거나, 한 정사각형 위에 다른 정사각형을 놓을 수 없다. 또, 직사각형은 정사각형으로 꽉 차있어야 한다.

입력

첫째 줄에 n (1 ≤ n ≤ 10,000)이 주어진다.

출력

만들 수 있는 직사각형의 개수를 출력한다.

예제 입력 1

6

예제 출력 1

8

힌트

W3sicHJvYmxlbV9pZCI6IjgzMjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHViOWNjXHViNGRjXHViMjk0IFx1YmMyOVx1YmM5NSIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YmNjMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgMVx1Yzc3OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgblx1YWMxY1x1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1Y2QxZCBcdWJhODcgXHVhYzFjXHVjNzdjXHVhZTRjPzxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IEFcdWM2NDAgQlx1YWMwMCBcdWM3ODhcdWM3NDQgXHViNTRjLCBBXHViOTdjIFx1Yzc3NFx1YjNkOSwgXHVkNjhjXHVjODA0XHVjMmRjXHVjZjFjXHVjMTFjIEJcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM1YzZcdWM3M2NcdWJhNzQsIFx1YjQ1MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDAgXHViMmU0XHViOTc0XHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YjljY1x1YjRlNCBcdWI1NGMsIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWJjYzBcdWQ2MTVcdWMyZGNcdWQwYTRcdWFjNzBcdWIwOTgsIFx1ZDU1YyBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVjNzA0XHVjNWQwIFx1YjJlNFx1Yjk3OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHViMTkzXHVjNzQ0IFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YjYxMCwgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQwIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWFmNDkgXHVjYzI4XHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgbiAoMSAmbGU7IG4gJmxlOyAxMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9wcm8xLmdpZlwiIHN0eWxlPVwiaGVpZ2h0OjEyMnB4OyB3aWR0aDoxNTdweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiODMyMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJlY3RhbmdsZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkJ5dGVtYW4gaGFzIGEgY29sbGVjdGlvbiBvZiBuIHNxdWFyZXMgd2l0aCBzaWRlIDEuIEhvdyBtYW55IGRpZmZlcmVudCByZWN0YW5nbGVzIGNhbiBoZSBmb3JtIHVzaW5nIHRoZXNlIHNxdWFyZXM/PFwvcD5cclxuXHJcbjxwPlR3byByZWN0YW5nbGVzIGFyZSBjb25zaWRlcmVkIGRpZmZlcmVudCBpZiBub25lIG9mIHRoZW0gY2FuIGJlIHJvdGF0ZWQgYW5kIG1vdmVkIHRvIG9idGFpbiB0aGUgc2Vjb25kIG9uZS4gRHVyaW5nIHJlY3RhbmdsZSBjb25zdHJ1Y3Rpb24sIEJ5dGVtYW4gY2FuIG5laXRoZXIgZGVmb3JtIHRoZSBzcXVhcmVzIG5vciBwdXQgYW55IHNxdWFyZXMgdXBvbiBhbnkgb3RoZXIgb25lcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIHRoZSBzdGFuZGFyZCBpbnB1dCBjb250YWlucyBvbmUgaW50ZWdlciBuICgxICZsZTsgbiAmbGU7IDEwIDAwMCkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2YgdGhlIHN0YW5kYXJkIG91dHB1dCBzaG91bGQgY29udGFpbiBhIHNpbmdsZSBpbnRlZ2VyIGVxdWFsIHRvIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHJlY3RhbmdsZXMgdGhhdCBCeXRlbWFuIGNhbiBmb3JtIHVzaW5nIGhpcyBzcXVhcmVzLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9wcm8xLmdpZlwiIHN0eWxlPVwiaGVpZ2h0OjEyMnB4OyB3aWR0aDoxNTdweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > Algorithmic Engagements > PA 2009 0-1번